//C- -*- C++ -*- //C- ------------------------------------------------------------------- //C- DjVuLibre-3.5 //C- Copyright (c) 2002 Leon Bottou and Yann Le Cun. //C- Copyright (c) 2001 AT&T //C- //C- This software is subject to, and may be distributed under, the //C- GNU General Public License, either Version 2 of the license, //C- or (at your option) any later version. The license should have //C- accompanied the software or you may obtain a copy of the license //C- from the Free Software Foundation at http://www.fsf.org . //C- //C- This program is distributed in the hope that it will be useful, //C- but WITHOUT ANY WARRANTY; without even the implied warranty of //C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //C- GNU General Public License for more details. //C- //C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from //C- Lizardtech Software. Lizardtech Software has authorized us to //C- replace the original DjVu(r) Reference Library notice by the following //C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu): //C- //C- ------------------------------------------------------------------ //C- | DjVu (r) Reference Library (v. 3.5) //C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved. //C- | The DjVu Reference Library is protected by U.S. Pat. No. //C- | 6,058,214 and patents pending. //C- | //C- | This software is subject to, and may be distributed under, the //C- | GNU General Public License, either Version 2 of the license, //C- | or (at your option) any later version. The license should have //C- | accompanied the software or you may obtain a copy of the license //C- | from the Free Software Foundation at http://www.fsf.org . //C- | //C- | The computer code originally released by LizardTech under this //C- | license and unmodified by other parties is deemed "the LIZARDTECH //C- | ORIGINAL CODE." Subject to any third party intellectual property //C- | claims, LizardTech grants recipient a worldwide, royalty-free, //C- | non-exclusive license to make, use, sell, or otherwise dispose of //C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the //C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU //C- | General Public License. This grant only confers the right to //C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to //C- | the extent such infringement is reasonably necessary to enable //C- | recipient to make, have made, practice, sell, or otherwise dispose //C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to //C- | any greater extent that may be necessary to utilize further //C- | modifications or combinations. //C- | //C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY //C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED //C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF //C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. //C- +------------------------------------------------------------------ #ifdef HAVE_CONFIG_H # include "config.h" #endif #if NEED_GNUG_PRAGMAS # pragma implementation #endif #include "GContainer.h" #ifdef HAVE_NAMESPACES namespace DJVU { # ifdef NOT_DEFINED // Just to fool emacs c++ mode } #endif #endif // ------------------------------------------------------------ // DYNAMIC ARRAYS // ------------------------------------------------------------ GArrayBase::GArrayBase(const GArrayBase &ref) : traits(ref.traits), data(0), minlo(ref.minlo), maxhi(ref.maxhi), lobound(ref.lobound), hibound(ref.hibound) { if (maxhi >= minlo) data = ::operator new(traits.size * (maxhi - minlo + 1)); if (hibound >= lobound) traits.copy(traits.lea(data, lobound-minlo), traits.lea(ref.data, lobound-minlo), hibound - lobound + 1, 0); } GArrayBase::GArrayBase(const GCONT Traits &traits) : traits(traits), data(0), minlo(0), maxhi(-1), lobound(0), hibound(-1) { } GArrayBase::GArrayBase(const GCONT Traits &traits, int lobound, int hibound) : traits(traits), data(0), minlo(0), maxhi(-1), lobound(0), hibound(-1) { resize(lobound, hibound); } GArrayBase::~GArrayBase() { G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH; } GArrayBase & GArrayBase::operator= (const GArrayBase &ga) { if (this == &ga) return *this; empty(); if (ga.hibound >= ga.lobound) { resize(ga.lobound, ga.hibound); traits.copy( traits.lea(data, lobound-minlo), traits.lea(ga.data, ga.lobound-ga.minlo), hibound - lobound + 1, 0 ); } return *this; } void GArrayBase::steal(GArrayBase &ga) { if (this != &ga) { empty(); lobound = ga.lobound; hibound = ga.hibound; minlo = ga.minlo; maxhi = ga.maxhi; data = ga.data; ga.data = 0; ga.lobound = ga.minlo = 0; ga.hibound = ga.maxhi = -1; } } void GArrayBase::empty() { resize(0, -1); } void GArrayBase::touch(int n) { int nlo = (nhibound ? n : hibound); if (hibound < lobound) nlo = nhi = n; resize(nlo, nhi); } void GArrayBase::resize(int lo, int hi) { // Validation int nsize = hi - lo + 1; if (nsize < 0) G_THROW( ERR_MSG("GContainer.bad_args") ); // Destruction if (nsize == 0) { if (hibound >= lobound) traits.fini( traits.lea(data, lobound-minlo), hibound-lobound+1 ); if (data) ::operator delete (data); data = 0; lobound = minlo = 0; hibound = maxhi = -1; return; } // Simple extension if (lo >= minlo && hi <= maxhi) { if (lobound > lo) traits.init( traits.lea(data,lo-minlo), lobound-lo ); else if (lo > lobound) traits.fini( traits.lea(data,lobound-minlo), lo-lobound ); if (hi > hibound) traits.init( traits.lea(data,hibound-minlo+1), hi-hibound ); else if (hibound > hi) traits.fini( traits.lea(data,hi-minlo+1), hibound-hi ); lobound = lo; hibound = hi; return; } // General case int nminlo = minlo; int nmaxhi = maxhi; if (nminlo > nmaxhi) nminlo = nmaxhi = lo; while (nminlo > lo) { int incr = nmaxhi - nminlo; nminlo -= (incr < 8 ? 8 : (incr > 32768 ? 32768 : incr)); } while (nmaxhi < hi) { int incr = nmaxhi - nminlo; nmaxhi += (incr < 8 ? 8 : (incr > 32768 ? 32768 : incr)); } // allocate and move int beg = lo; int end = hi; int bytesize = traits.size * (nmaxhi-nminlo+1); void *ndata = ::operator new(bytesize); #if GCONTAINER_ZERO_FILL memset(ndata, 0, bytesize); // slower but cleaner #endif G_TRY { if (lo < lobound) { traits.init( traits.lea(ndata,lo-nminlo), lobound-lo ); beg=lobound; } else if (lobound < lo) { traits.fini( traits.lea(data,lobound-minlo), lo-lobound); } if (hibound < hi) { traits.init( traits.lea(ndata,hibound-nminlo+1), hi-hibound ); end=hibound; } else if (hi < hibound) { traits.fini( traits.lea(data, hi-minlo+1), hibound-hi ); } if (end >= beg) { traits.copy( traits.lea(ndata, beg-nminlo), traits.lea(data, beg-minlo), end-beg+1, 1 ); } } G_CATCH_ALL { if (ndata) ::operator delete(ndata); G_RETHROW; } G_ENDCATCH; // free and replace if (data) ::operator delete(data); data = ndata; minlo = nminlo; maxhi = nmaxhi; lobound = lo; hibound = hi; } void GArrayBase::shift(int disp) { lobound += disp; hibound += disp; minlo += disp; maxhi += disp; } void GArrayBase::del(int n, int howmany) { if (howmany < 0) G_THROW( ERR_MSG("GContainer.bad_howmany") ); if (howmany == 0) return; if ( n < lobound || n+(int)howmany-1 > hibound) G_THROW( ERR_MSG("GContainer.bad_sub2") ); traits.fini( traits.lea(data, n-minlo), howmany ); if ( n+howmany-1 < hibound) traits.copy( traits.lea(data, n-minlo), traits.lea(data, n-minlo+howmany), hibound - (n+howmany-1), 1 ); hibound = hibound - howmany; } static inline void * nextptr(void *p, int elsize) { return (void*)(((char*)p) + elsize); } static inline void * prevptr(void *p, int elsize) { return (void*)(((char*)p) - elsize); } void GArrayBase::ins(int n, const void *src, int howmany) { if (howmany < 0) G_THROW( ERR_MSG("GContainer.bad_howmany") ); if (howmany == 0) return; // Make enough room if (hibound+howmany > maxhi) { int nmaxhi = maxhi; while (nmaxhi < hibound+howmany) nmaxhi += (nmaxhi < 8 ? 8 : (nmaxhi > 32768 ? 32768 : nmaxhi)); int bytesize = traits.size * (nmaxhi-minlo+1); void *ndata = ::operator new (bytesize); #if GCONTAINER_ZERO_FILL memset(ndata, 0, bytesize); #endif G_TRY { if (hibound >= lobound) traits.copy( traits.lea(ndata, lobound-minlo), traits.lea(data, lobound-minlo), hibound-lobound+1, 1 ); } G_CATCH_ALL { if (ndata) ::operator delete (ndata); G_RETHROW; } G_ENDCATCH; if (data) ::operator delete(data); data = ndata; maxhi = nmaxhi; } // Shift data int elsize = traits.size; void *pdst = traits.lea(data, hibound+howmany-minlo); void *psrc = traits.lea(data, hibound-minlo); void *pend = traits.lea(data, n-minlo); while ((char*)psrc >= (char*)pend) { traits.copy( pdst, psrc, 1, 1 ); pdst = prevptr(pdst, elsize); psrc = prevptr(psrc, elsize); } hibound += howmany; // Initialize new data if (! src) { traits.init( traits.lea(data, n-minlo), howmany ); hibound += howmany; return; } // Initialize new data with copy constructor pdst = traits.lea(data, n-minlo); pend = traits.lea(data, n+howmany-minlo); while ((char*)pdst < (char*)pend) { traits.copy( pdst, src, 1, 0); pdst = nextptr(pdst, elsize); } } // ------------------------------------------------------------ // GPOSITION // ------------------------------------------------------------ void GPosition::throw_invalid(void *c) const { if (c != cont) G_THROW( ERR_MSG("GContainer.bad_pos_cont") ); else if (! ptr) G_THROW( ERR_MSG("GContainer.bad_pos_null") ); else G_THROW( ERR_MSG("GContainer.bad_pos") ); } // ------------------------------------------------------------ // DOUBLY LINKED LISTS // ------------------------------------------------------------ GListBase::GListBase(const Traits& traits) : traits(traits) { nelem = 0; head.next = head.prev = 0; } GListBase::GListBase(const GListBase &ref) : traits(ref.traits) { nelem = 0; head.next = head.prev = 0; GListBase::operator= (ref); } GListBase::~GListBase() { G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH; } void GListBase::append(Node *n) { // Link n->next = 0; n->prev = head.prev; head.prev = n; if (n->prev) n->prev->next = n; else head.next = n; // Finish nelem += 1; } void GListBase::prepend(Node *n) { // Link n->next = head.next; n->prev = 0; head.next = n; if (n->next) n->next->prev = n; else head.prev = n; // Finish nelem += 1; } void GListBase::insert_after(GPosition pos, Node *n) { // Prepare if (pos.ptr) { if (pos.cont != (void*)this) pos.throw_invalid((void*)this); Node *p = pos.ptr; n->prev = p; n->next = p->next; } else { n->prev = 0; n->next = head.next; } // Link if (n->prev) n->prev->next = n; else head.next = n; if (n->next) n->next->prev = n; else head.prev = n; // Finish nelem += 1; } void GListBase::insert_before(GPosition pos, Node *n) { // Prepare if (pos.ptr) { if (pos.cont != (void*)this) pos.throw_invalid((void*)this); Node *p = pos.ptr; n->prev = p->prev; n->next = p; } else { n->prev = head.prev; n->next = 0; } // Link if (n->prev) n->prev->next = n; else head.next = n; if (n->next) n->next->prev = n; else head.prev = n; // Finish nelem += 1; } void GListBase::insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos) { // Check if (!frompos.ptr || frompos.cont != (void*)&fromlist) frompos.throw_invalid((void*)&fromlist); if (pos.ptr && pos.cont != (void*)this) pos.throw_invalid((void*)this); // Update frompos Node *n = frompos.ptr; frompos.ptr = n->next; if (pos.ptr == n) return; // Unlink if (n->next) n->next->prev = n->prev; else fromlist.head.prev = n->prev; if (n->prev) n->prev->next = n->next; else fromlist.head.next = n->next; fromlist.nelem -= 1; // Prepare insertion if (pos.ptr) { Node *p = pos.ptr; n->prev = p->prev; n->next = p; } else { n->prev = head.prev; n->next = 0; } // Link if (n->prev) n->prev->next = n; else head.next = n; if (n->next) n->next->prev = n; else head.prev = n; nelem += 1; } void GListBase::del(GPosition &pos) { // Check if (!pos.ptr || pos.cont != (void*)this) return; // Unlink Node *n = pos.ptr; if (n->next) n->next->prev = n->prev; else head.prev = n->prev; if (n->prev) n->prev->next = n->next; else head.next = n->next; // Finish nelem -= 1; traits.fini( (void*)n, 1); operator delete ( (void*)n ); pos.ptr = 0; } GPosition GListBase::nth(unsigned int n) const { Node *p = 0; if ((int)n < nelem) for (p=head.next; p; p=p->next) if ( n-- == 0) break; return GPosition(p, (void*)this); } void GListBase::empty() { Node *n=head.next; while (n) { Node *p = n->next; traits.fini( (void*)n, 1 ); operator delete ( (void*)n ); n = p; } head.next = head.prev = 0; nelem = 0; } GListBase & GListBase::operator= (const GListBase & ref) { if (this == &ref) return *this; empty(); for(Node *n = ref.head.next; n; n=n->next) { Node *m = (Node*) operator new (traits.size); traits.copy( (void*)m, (void*)n, 1, 0); append(m); } return *this; } // ------------------------------------------------------------ // ASSOCIATIVE MAPS // ------------------------------------------------------------ GSetBase::GSetBase(const Traits &traits) : traits(traits), nelems(0), nbuckets(0), gtable(table), first(0) { rehash(17); } GSetBase::GSetBase(const GSetBase &ref) : traits(ref.traits), nelems(0), nbuckets(0), gtable(table), first(0) { GSetBase::operator= (ref); } GSetBase::~GSetBase() { G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH; // delete [] table; } GCONT HNode * GSetBase::hashnode(unsigned int hashcode) const { int bucket = hashcode % nbuckets; return table[bucket]; } GCONT HNode * GSetBase::installnode(HNode *n) { // Rehash if table is more than 60% full if (nelems*3 > nbuckets*2) rehash( 2*nbuckets - 1 ); // Create and insert insertnode(n); return n; } void GSetBase::insertnode(HNode *n) { int bucket = n->hashcode % nbuckets; n->prev = n->hprev = table[bucket]; if (n->prev) { // bucket was not empty n->next = n->prev->next; n->prev->next = n; if (n->next) n->next->prev = n; } else { // bucket was empty. n->next = first; first = n; if (n->next) n->next->prev = n; } // finish table[bucket] = n; nelems += 1; } void GSetBase::deletenode(GCONT HNode *n) { if (n == 0) return; int bucket = n->hashcode % nbuckets; // Regular links if (n->next) n->next->prev = n->prev; if (n->prev) n->prev->next = n->next; else first = (HNode*)(n->next); // HPrev links if (table[bucket] == n) table[bucket] = n->hprev; else ((HNode*)(n->next))->hprev = n->hprev; // Delete entry traits.fini( (void*)n, 1 ); operator delete ( (void*)n ); nelems -= 1; } void GSetBase::rehash(int newbuckets) { // Save chain of nodes Node *n = first; // Simulate an empty map nelems = 0; first = 0; // Allocate a new empty bucket table gtable.resize(0); nbuckets = newbuckets; gtable.resize(nbuckets); gtable.clear(); // Insert saved nodes while (n) { Node *p = n->next; insertnode((HNode*)n); n = p; } } GSetBase& GSetBase::operator=(const GSetBase &ref) { if (this == &ref) return *this; empty(); rehash(ref.nbuckets); for (Node *n = ref.first; n; n=n->next) { HNode *m = (HNode*) operator new (traits.size); traits.copy( (void*)m, (void*)n, 1, 0); insertnode(m); } return *this; } GPosition GSetBase::firstpos() const { return GPosition(first, (void*)this); } void GSetBase::del(GPosition &pos) { if (pos.ptr && pos.cont==(void*)this) { deletenode((HNode*)pos.ptr); pos.ptr = 0; } } void GSetBase::empty() { HNode *n = first; while (n) { HNode *p = (HNode*)(n->next); traits.fini( (void*)n, 1 ); operator delete ( (void*)n ); n = p; } first = 0; nelems = 0; gtable.clear(); // for (int i=0; i