diff options
Diffstat (limited to 'kviewshell/plugins/djvu/libdjvu/GContainer.cpp')
| -rw-r--r-- | kviewshell/plugins/djvu/libdjvu/GContainer.cpp | 802 |
1 files changed, 802 insertions, 0 deletions
diff --git a/kviewshell/plugins/djvu/libdjvu/GContainer.cpp b/kviewshell/plugins/djvu/libdjvu/GContainer.cpp new file mode 100644 index 00000000..2019439c --- /dev/null +++ b/kviewshell/plugins/djvu/libdjvu/GContainer.cpp @@ -0,0 +1,802 @@ +//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, Version 2. 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 +//C- distributed by Lizardtech Software. On July 19th 2002, Lizardtech +//C- Software authorized us to replace the original DjVu(r) Reference +//C- Library notice by the following text (see doc/lizard2002.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, Version 2. 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- +------------------------------------------------------------------ +// +// $Id: GContainer.cpp,v 1.12 2003/11/07 22:08:21 leonb Exp $ +// $Name: release_3_5_15 $ + +#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), + gdata(data,0,1), + minlo(ref.minlo), maxhi(ref.maxhi), + lobound(ref.lobound), hibound(ref.hibound) +{ + if (maxhi >= minlo) + gdata.resize(traits.size * (maxhi - minlo + 1),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), + gdata(data,0,1), + minlo(0), maxhi(-1), + lobound(0), hibound(-1) +{ +} + + +GArrayBase::GArrayBase(const GCONT Traits &traits, int lobound, int hibound) + : traits(traits), + gdata(data,0,1), + 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 = (n<lobound ? n : lobound); + int nhi = (n>hibound ? 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) + gdata.resize(0,1); + 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; + GPBufferBase gndata(ndata,bytesize,1); +#if GCONTAINER_ZERO_FILL + memset(ndata, 0, bytesize); // slower but cleaner +#endif + 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 ); } + // free and replace + void *tmp=data; + data=ndata; + ndata=tmp; + 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); + GPBufferBase gndata(ndata,bytesize,1); + memset(ndata, 0, bytesize); // slower but cleaner + if (hibound >= lobound) + traits.copy( traits.lea(ndata, lobound-minlo), + traits.lea(data, lobound-minlo), + hibound-lobound+1, 1 ); + maxhi = nmaxhi; + void *tmp=data; + data = ndata; + ndata=tmp; + } + // 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); +} + +#include <stdio.h> +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 +// delete [] table; + gtable.resize(0); + nbuckets = newbuckets; + typedef HNode *HNodePtr; +// table = new HNodePtr[nbuckets]; + gtable.resize(nbuckets); + gtable.clear(); +// for (int i=0; i<nbuckets; i++) +// table[i] = 0; + // 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<nbuckets; i++) +// table[i] = 0; +} + + +#ifdef HAVE_NAMESPACES +} +# ifndef NOT_USING_DJVU_NAMESPACE +using namespace DJVU; +# endif +#endif + |