source: trunk/libdjvu/GContainer.cpp @ 426

Last change on this file since 426 was 280, checked in by rbri, 12 years ago

DJVU plugin: djvulibre updated to version 3.5.22

File size: 17.4 KB
Line 
1//C-  -*- C++ -*-
2//C- -------------------------------------------------------------------
3//C- DjVuLibre-3.5
4//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
5//C- Copyright (c) 2001  AT&T
6//C-
7//C- This software is subject to, and may be distributed under, the
8//C- GNU General Public License, either Version 2 of the license,
9//C- or (at your option) any later version. The license should have
10//C- accompanied the software or you may obtain a copy of the license
11//C- from the Free Software Foundation at http://www.fsf.org .
12//C-
13//C- This program is distributed in the hope that it will be useful,
14//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16//C- GNU General Public License for more details.
17//C-
18//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19//C- Lizardtech Software.  Lizardtech Software has authorized us to
20//C- replace the original DjVu(r) Reference Library notice by the following
21//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22//C-
23//C-  ------------------------------------------------------------------
24//C- | DjVu (r) Reference Library (v. 3.5)
25//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26//C- | The DjVu Reference Library is protected by U.S. Pat. No.
27//C- | 6,058,214 and patents pending.
28//C- |
29//C- | This software is subject to, and may be distributed under, the
30//C- | GNU General Public License, either Version 2 of the license,
31//C- | or (at your option) any later version. The license should have
32//C- | accompanied the software or you may obtain a copy of the license
33//C- | from the Free Software Foundation at http://www.fsf.org .
34//C- |
35//C- | The computer code originally released by LizardTech under this
36//C- | license and unmodified by other parties is deemed "the LIZARDTECH
37//C- | ORIGINAL CODE."  Subject to any third party intellectual property
38//C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39//C- | non-exclusive license to make, use, sell, or otherwise dispose of
40//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42//C- | General Public License.   This grant only confers the right to
43//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44//C- | the extent such infringement is reasonably necessary to enable
45//C- | recipient to make, have made, practice, sell, or otherwise dispose
46//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47//C- | any greater extent that may be necessary to utilize further
48//C- | modifications or combinations.
49//C- |
50//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54//C- +------------------------------------------------------------------
55//
56// $Id: GContainer.cpp,v 1.15 2007/03/25 20:48:31 leonb Exp $
57// $Name: release_3_5_22 $
58
59#ifdef HAVE_CONFIG_H
60# include "config.h"
61#endif
62#if NEED_GNUG_PRAGMAS
63# pragma implementation
64#endif
65
66#include "GContainer.h"
67
68
69#ifdef HAVE_NAMESPACES
70namespace DJVU {
71# ifdef NOT_DEFINED // Just to fool emacs c++ mode
72}
73#endif
74#endif
75
76
77// ------------------------------------------------------------
78// DYNAMIC ARRAYS
79// ------------------------------------------------------------
80
81
82GArrayBase::GArrayBase(const GArrayBase &ref)
83  : traits(ref.traits), data(0),
84    minlo(ref.minlo), maxhi(ref.maxhi),
85    lobound(ref.lobound), hibound(ref.hibound)
86{
87  if (maxhi >= minlo)
88    data = ::operator new(traits.size * (maxhi - minlo + 1));
89  if (hibound >= lobound)
90    traits.copy(traits.lea(data, lobound-minlo), 
91                traits.lea(ref.data, lobound-minlo),
92                hibound - lobound + 1, 0);
93}
94
95
96GArrayBase::GArrayBase(const GCONT Traits &traits)
97  : traits(traits), data(0),
98    minlo(0), maxhi(-1),
99    lobound(0), hibound(-1)
100{
101}
102
103
104GArrayBase::GArrayBase(const GCONT Traits &traits, int lobound, int hibound)
105  : traits(traits), data(0),
106    minlo(0), maxhi(-1),
107    lobound(0), hibound(-1)
108{
109  resize(lobound, hibound);
110}
111
112
113GArrayBase::~GArrayBase()
114{
115  G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH;
116}
117
118
119GArrayBase &
120GArrayBase::operator= (const GArrayBase &ga)
121{
122  if (this == &ga)
123    return *this;
124  empty();
125  if (ga.hibound >= ga.lobound)
126    {
127      resize(ga.lobound, ga.hibound);
128      traits.copy( traits.lea(data, lobound-minlo),
129                   traits.lea(ga.data, ga.lobound-ga.minlo),
130                   hibound - lobound + 1, 0 );
131    }
132  return *this;
133}
134
135
136void
137GArrayBase::steal(GArrayBase &ga)
138{
139  if (this != &ga)
140    {
141      empty();
142      lobound = ga.lobound;
143      hibound = ga.hibound;
144      minlo = ga.minlo;
145      maxhi = ga.maxhi;
146      data = ga.data;
147      ga.data = 0;
148      ga.lobound = ga.minlo = 0;
149      ga.hibound = ga.maxhi = -1;
150    }
151}
152
153
154void 
155GArrayBase::empty()
156{
157  resize(0, -1);
158}
159
160
161void 
162GArrayBase::touch(int n)
163{
164  int nlo = (n<lobound ? n : lobound);
165  int nhi = (n>hibound ? n : hibound);
166  if (hibound < lobound)
167    nlo = nhi = n;
168  resize(nlo, nhi);
169}
170
171
172void 
173GArrayBase::resize(int lo, int hi)
174{
175  // Validation
176  int nsize = hi - lo + 1;
177  if (nsize < 0)
178    G_THROW( ERR_MSG("GContainer.bad_args") );
179  // Destruction
180  if (nsize == 0)
181    {
182      if (hibound >= lobound)
183        traits.fini( traits.lea(data, lobound-minlo), hibound-lobound+1 );
184      if (data)
185        ::operator delete (data);
186      data = 0;
187      lobound = minlo = 0;
188      hibound = maxhi = -1;
189      return;
190    }
191  // Simple extension
192  if (lo >= minlo && hi <= maxhi)
193    {
194      if (lobound > lo)
195        traits.init( traits.lea(data,lo-minlo), lobound-lo );
196      else if (lo > lobound)
197        traits.fini( traits.lea(data,lobound-minlo), lo-lobound );
198      if (hi > hibound)
199        traits.init( traits.lea(data,hibound-minlo+1), hi-hibound );
200      else if (hibound > hi)
201        traits.fini( traits.lea(data,hi-minlo+1), hibound-hi );       
202      lobound = lo;
203      hibound = hi;
204      return;
205    }
206  // General case
207  int nminlo = minlo;
208  int nmaxhi = maxhi;
209  if (nminlo > nmaxhi)
210    nminlo = nmaxhi = lo;
211  while (nminlo > lo) {
212    int incr = nmaxhi - nminlo;
213    nminlo -= (incr < 8 ? 8 : (incr > 32768 ? 32768 : incr));
214  }
215  while (nmaxhi < hi) {
216    int incr = nmaxhi - nminlo;
217    nmaxhi += (incr < 8 ? 8 : (incr > 32768 ? 32768 : incr));
218  }
219  // allocate and move
220  int beg = lo;
221  int end = hi;
222  int bytesize = traits.size * (nmaxhi-nminlo+1);
223  void *ndata = ::operator new(bytesize);
224#if GCONTAINER_ZERO_FILL
225  memset(ndata, 0, bytesize);  // slower but cleaner
226#endif
227  G_TRY
228    {
229      if (lo < lobound)
230        { traits.init( traits.lea(ndata,lo-nminlo), lobound-lo ); beg=lobound; }
231      else if (lobound < lo)
232        { traits.fini( traits.lea(data,lobound-minlo), lo-lobound); }
233      if (hibound < hi)
234        { traits.init( traits.lea(ndata,hibound-nminlo+1), hi-hibound ); end=hibound; }
235      else if (hi < hibound)
236        { traits.fini( traits.lea(data, hi-minlo+1), hibound-hi ); }
237      if (end >= beg)
238        { traits.copy( traits.lea(ndata, beg-nminlo), 
239                       traits.lea(data, beg-minlo),
240                       end-beg+1, 1 ); }
241    }
242  G_CATCH_ALL
243    {
244      if (ndata)
245        ::operator delete(ndata);
246      G_RETHROW;
247    }
248  G_ENDCATCH;
249  // free and replace
250  if (data) 
251    ::operator delete(data);
252  data = ndata;
253  minlo = nminlo;
254  maxhi = nmaxhi;
255  lobound = lo;
256  hibound = hi;
257}
258
259
260void 
261GArrayBase::shift(int disp)
262{
263  lobound += disp;
264  hibound += disp;
265  minlo += disp;
266  maxhi += disp;
267}
268
269
270void 
271GArrayBase::del(int n, int howmany)
272{
273  if (howmany < 0)
274    G_THROW( ERR_MSG("GContainer.bad_howmany") );
275  if (howmany == 0)
276    return;
277  if ( n < lobound || n+(int)howmany-1 > hibound)
278    G_THROW( ERR_MSG("GContainer.bad_sub2") );
279  traits.fini( traits.lea(data, n-minlo), howmany );
280  if ( n+howmany-1 < hibound)
281    traits.copy( traits.lea(data, n-minlo),
282                 traits.lea(data, n-minlo+howmany),
283                 hibound - (n+howmany-1), 1 );
284  hibound = hibound - howmany;
285}
286
287
288static inline void *
289nextptr(void *p, int elsize)
290{
291  return (void*)(((char*)p) + elsize);
292}
293
294
295static inline void *
296prevptr(void *p, int elsize)
297{
298  return (void*)(((char*)p) - elsize); 
299}
300
301
302void 
303GArrayBase::ins(int n, const void *src, int howmany)
304{
305  if (howmany < 0)
306    G_THROW( ERR_MSG("GContainer.bad_howmany") );
307  if (howmany == 0)
308    return;
309  // Make enough room
310  if (hibound+howmany > maxhi)
311    {
312      int nmaxhi = maxhi;
313      while (nmaxhi < hibound+howmany)
314        nmaxhi += (nmaxhi < 8 ? 8 : (nmaxhi > 32768 ? 32768 : nmaxhi));
315      int bytesize = traits.size * (nmaxhi-minlo+1);
316      void *ndata = ::operator new (bytesize);
317#if GCONTAINER_ZERO_FILL
318      memset(ndata, 0, bytesize);
319#endif
320      G_TRY
321        {
322          if (hibound >= lobound)
323            traits.copy( traits.lea(ndata, lobound-minlo),
324                         traits.lea(data, lobound-minlo),
325                         hibound-lobound+1, 1 );
326        }
327      G_CATCH_ALL
328        {
329          if (ndata)
330            ::operator delete (ndata);
331          G_RETHROW;
332        }
333      G_ENDCATCH;
334      if (data)
335        ::operator delete(data);
336      data = ndata;
337      maxhi = nmaxhi;
338    }
339  // Shift data
340  int elsize = traits.size;
341  void *pdst = traits.lea(data, hibound+howmany-minlo);
342  void *psrc = traits.lea(data, hibound-minlo);
343  void *pend = traits.lea(data, n-minlo);
344  while ((char*)psrc >= (char*)pend)
345    {
346      traits.copy( pdst, psrc, 1, 1 );
347      pdst = prevptr(pdst, elsize);
348      psrc = prevptr(psrc, elsize);
349    }
350  hibound += howmany;
351  // Initialize new data
352  if (! src)
353    {
354      traits.init( traits.lea(data, n-minlo), howmany );
355      hibound += howmany;
356      return;
357    }
358  // Initialize new data with copy constructor
359  pdst = traits.lea(data, n-minlo);
360  pend = traits.lea(data, n+howmany-minlo);
361  while ((char*)pdst < (char*)pend)
362    {
363      traits.copy( pdst, src, 1, 0);
364      pdst = nextptr(pdst, elsize);
365    }
366}
367
368
369
370// ------------------------------------------------------------
371// GPOSITION
372// ------------------------------------------------------------
373
374
375
376void 
377GPosition::throw_invalid(void *c) const
378{
379  if (c != cont)
380    G_THROW( ERR_MSG("GContainer.bad_pos_cont") );
381  else if (! ptr)
382    G_THROW( ERR_MSG("GContainer.bad_pos_null") );
383  else 
384    G_THROW( ERR_MSG("GContainer.bad_pos") );
385}
386
387
388
389// ------------------------------------------------------------
390// DOUBLY LINKED LISTS
391// ------------------------------------------------------------
392
393
394GListBase::GListBase(const Traits& traits)
395  : traits(traits)
396{
397  nelem = 0;
398  head.next = head.prev = 0;
399}
400
401
402GListBase::GListBase(const GListBase &ref)
403  : traits(ref.traits)
404{
405  nelem = 0;
406  head.next = head.prev = 0;
407  GListBase::operator= (ref);
408}
409
410GListBase::~GListBase()
411{
412  G_TRY
413  {
414    empty();
415  }
416  G_CATCH_ALL
417  {
418  }
419  G_ENDCATCH;
420}
421
422
423void 
424GListBase::append(Node *n)
425{
426  // Link
427  n->next = 0;
428  n->prev = head.prev;
429  head.prev = n;
430  if (n->prev)
431    n->prev->next = n;
432  else
433    head.next = n;
434  // Finish
435  nelem += 1;
436}
437
438
439void 
440GListBase::prepend(Node *n)
441{
442  // Link
443  n->next = head.next;
444  n->prev = 0;
445  head.next = n;
446  if (n->next)
447    n->next->prev = n;
448  else
449    head.prev = n;
450  // Finish
451  nelem += 1;
452}
453
454
455void 
456GListBase::insert_after(GPosition pos, Node *n)
457{
458  // Prepare
459  if (pos.ptr)
460    {
461      if (pos.cont != (void*)this)
462        pos.throw_invalid((void*)this);
463      Node *p = pos.ptr;
464      n->prev = p;
465      n->next = p->next;
466    }
467  else
468    {
469      n->prev = 0;
470      n->next = head.next;
471    }
472  // Link
473  if (n->prev)
474    n->prev->next = n;
475  else
476    head.next = n;
477  if (n->next)
478    n->next->prev = n;
479  else
480    head.prev = n;
481  // Finish
482  nelem += 1;
483}
484
485
486void 
487GListBase::insert_before(GPosition pos, Node *n)
488{
489  // Prepare
490  if (pos.ptr)
491    {
492      if (pos.cont != (void*)this)
493        pos.throw_invalid((void*)this);
494      Node *p = pos.ptr;
495      n->prev = p->prev;
496      n->next = p;
497    }
498  else
499    {
500      n->prev = head.prev;
501      n->next = 0;
502    }
503  // Link
504  if (n->prev)
505    n->prev->next = n;
506  else
507    head.next = n;
508  if (n->next)
509    n->next->prev = n;
510  else
511    head.prev = n;
512  // Finish
513  nelem += 1;
514}
515
516
517void
518GListBase::insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos)
519{
520  // Check
521  if (!frompos.ptr || frompos.cont != (void*)&fromlist)
522    frompos.throw_invalid((void*)&fromlist);
523  if (pos.ptr && pos.cont != (void*)this)
524    pos.throw_invalid((void*)this);
525  // Update frompos
526  Node *n = frompos.ptr;
527  frompos.ptr = n->next;
528  if (pos.ptr == n) return;
529  // Unlink
530  if (n->next)
531    n->next->prev = n->prev;
532  else
533    fromlist.head.prev = n->prev;
534  if (n->prev)
535    n->prev->next = n->next;
536  else
537    fromlist.head.next = n->next;
538  fromlist.nelem -= 1;
539  // Prepare insertion
540  if (pos.ptr)
541    {
542      Node *p = pos.ptr;
543      n->prev = p->prev;
544      n->next = p;
545    }
546  else
547    {
548      n->prev = head.prev;
549      n->next = 0;
550    }
551  // Link
552  if (n->prev)
553    n->prev->next = n;
554  else
555    head.next = n;
556  if (n->next)
557    n->next->prev = n;
558  else
559    head.prev = n;
560  nelem += 1;
561}
562
563
564void 
565GListBase::del(GPosition &pos)
566{
567  // Check
568  if (!pos.ptr || pos.cont != (void*)this) return;
569  // Unlink
570  Node *n = pos.ptr;
571  if (n->next)
572    n->next->prev = n->prev;
573  else
574    head.prev = n->prev;
575  if (n->prev)
576    n->prev->next = n->next;
577  else
578    head.next = n->next;
579  // Finish
580  nelem -= 1;
581  traits.fini( (void*)n, 1);
582  operator delete ( (void*)n );
583  pos.ptr = 0;
584}
585
586
587GPosition
588GListBase::nth(unsigned int n) const
589{
590  Node *p = 0;
591  if ((int)n < nelem)
592    for (p=head.next; p; p=p->next)
593      if ( n-- == 0)
594        break;
595  return GPosition(p, (void*)this);
596}
597
598
599void 
600GListBase::empty()
601{
602  Node *n=head.next;
603  while (n)
604    {
605      Node *p = n->next;
606      traits.fini( (void*)n, 1 );
607      operator delete ( (void*)n );
608      n = p;
609    }
610  head.next = head.prev = 0;
611  nelem = 0;
612}
613
614
615GListBase & 
616GListBase::operator= (const GListBase & ref)
617{
618  if (this == &ref)
619    return *this;
620  empty();
621  for(Node *n = ref.head.next; n; n=n->next)
622    {
623      Node *m = (Node*) operator new (traits.size);
624      traits.copy( (void*)m, (void*)n, 1, 0);
625      append(m);
626    }
627  return *this;
628}
629
630
631
632
633
634// ------------------------------------------------------------
635// ASSOCIATIVE MAPS
636// ------------------------------------------------------------
637
638
639
640
641GSetBase::GSetBase(const Traits &traits)
642  : traits(traits), nelems(0), nbuckets(0), 
643    gtable(table), first(0)
644{
645  rehash(17);
646}
647
648
649GSetBase::GSetBase(const GSetBase &ref)
650  : traits(ref.traits), 
651    nelems(0), nbuckets(0), gtable(table), first(0)
652{
653  GSetBase::operator= (ref);
654}
655
656
657GSetBase::~GSetBase()
658{
659  G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH;
660//  delete [] table;
661}
662
663
664GCONT HNode *
665GSetBase::hashnode(unsigned int hashcode) const
666{
667  int bucket = hashcode % nbuckets;
668  return table[bucket];
669}
670
671GCONT HNode *
672GSetBase::installnode(HNode *n)
673{
674  // Rehash if table is more than 60% full
675  if (nelems*3 > nbuckets*2)
676    rehash( 2*nbuckets - 1 );
677  // Create and insert
678  insertnode(n);
679  return n;
680}
681
682void 
683GSetBase::insertnode(HNode *n)
684{
685  int bucket = n->hashcode % nbuckets;
686  n->prev = n->hprev = table[bucket];
687  if (n->prev) 
688    {
689      // bucket was not empty
690      n->next = n->prev->next;
691      n->prev->next = n;
692      if (n->next)
693        n->next->prev = n;
694    }
695  else
696    {
697      // bucket was empty.
698      n->next = first;
699      first = n;
700      if (n->next)
701        n->next->prev = n;
702    }
703  // finish
704  table[bucket] = n;
705  nelems += 1;
706}
707
708
709void   
710GSetBase::deletenode(GCONT HNode *n)
711{
712  if (n == 0) 
713    return;
714  int bucket = n->hashcode % nbuckets;
715  // Regular links
716  if (n->next)
717    n->next->prev = n->prev;
718  if (n->prev)
719    n->prev->next = n->next;
720  else
721    first = (HNode*)(n->next);
722  // HPrev links
723  if (table[bucket] == n)
724    table[bucket] = n->hprev;
725  else
726    ((HNode*)(n->next))->hprev = n->hprev;
727  // Delete entry
728  traits.fini( (void*)n, 1 );
729  operator delete ( (void*)n );
730  nelems -= 1;
731}
732
733
734void   
735GSetBase::rehash(int newbuckets)
736{
737  // Save chain of nodes
738  Node *n = first;
739  // Simulate an empty map
740  nelems = 0;
741  first = 0;
742  // Allocate a new empty bucket table
743// delete [] table;
744  gtable.resize(0);
745  nbuckets = newbuckets;
746  typedef HNode *HNodePtr;
747// table = new HNodePtr[nbuckets];
748  gtable.resize(nbuckets);
749  gtable.clear();
750//  for (int i=0; i<nbuckets; i++)
751//    table[i] = 0;
752  // Insert saved nodes
753  while (n)
754    {
755      Node *p = n->next;
756      insertnode((HNode*)n);
757      n = p;
758    }
759}
760
761
762GSetBase& 
763GSetBase::operator=(const GSetBase &ref)
764{
765  if (this == &ref) 
766    return *this;
767  empty();
768  rehash(ref.nbuckets);
769  for (Node *n = ref.first; n; n=n->next)
770    {
771      HNode *m = (HNode*) operator new (traits.size);
772      traits.copy( (void*)m, (void*)n, 1, 0);
773      insertnode(m);
774    }
775  return *this;
776}
777
778
779GPosition
780GSetBase::firstpos() const
781{
782  return GPosition(first, (void*)this);
783}
784
785
786void 
787GSetBase::del(GPosition &pos)
788{
789  if (pos.ptr && pos.cont==(void*)this)
790    {
791      deletenode((HNode*)pos.ptr);
792      pos.ptr = 0;
793    }
794}
795
796void 
797GSetBase::empty()
798{
799  HNode *n = first;
800  while (n)
801    {
802      HNode *p = (HNode*)(n->next);
803      traits.fini( (void*)n, 1 );
804      operator delete ( (void*)n );
805      n = p;
806    }
807  first = 0;
808  nelems = 0;
809  gtable.clear();
810//  for (int i=0; i<nbuckets; i++)
811//    table[i] = 0;
812}
813
814
815#ifdef HAVE_NAMESPACES
816}
817# ifndef NOT_USING_DJVU_NAMESPACE
818using namespace DJVU;
819# endif
820#endif
821
Note: See TracBrowser for help on using the repository browser.