source: trunk/libdjvu/GContainer.cpp @ 199

Last change on this file since 199 was 17, checked in by Eugene Romanenko, 16 years ago

update makefiles, remove absolute paths, update djvulibre to version 3.5.17

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