source: trunk/libdjvu/GContainer.cpp @ 15

Last change on this file since 15 was 15, checked in by Eugene Romanenko, 15 years ago

needed libs update

File size: 16.9 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.12 2003/11/07 22:08:21 leonb Exp $
55// $Name: release_3_5_16 $
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
390#include <stdio.h>
391GListBase::~GListBase()
392{
393  G_TRY
394  {
395    empty();
396  }
397  G_CATCH_ALL
398  {
399  }
400  G_ENDCATCH;
401}
402
403
404void 
405GListBase::append(Node *n)
406{
407  // Link
408  n->next = 0;
409  n->prev = head.prev;
410  head.prev = n;
411  if (n->prev)
412    n->prev->next = n;
413  else
414    head.next = n;
415  // Finish
416  nelem += 1;
417}
418
419
420void 
421GListBase::prepend(Node *n)
422{
423  // Link
424  n->next = head.next;
425  n->prev = 0;
426  head.next = n;
427  if (n->next)
428    n->next->prev = n;
429  else
430    head.prev = n;
431  // Finish
432  nelem += 1;
433}
434
435
436void 
437GListBase::insert_after(GPosition pos, Node *n)
438{
439  // Prepare
440  if (pos.ptr)
441    {
442      if (pos.cont != (void*)this)
443        pos.throw_invalid((void*)this);
444      Node *p = pos.ptr;
445      n->prev = p;
446      n->next = p->next;
447    }
448  else
449    {
450      n->prev = 0;
451      n->next = head.next;
452    }
453  // Link
454  if (n->prev)
455    n->prev->next = n;
456  else
457    head.next = n;
458  if (n->next)
459    n->next->prev = n;
460  else
461    head.prev = n;
462  // Finish
463  nelem += 1;
464}
465
466
467void 
468GListBase::insert_before(GPosition pos, Node *n)
469{
470  // Prepare
471  if (pos.ptr)
472    {
473      if (pos.cont != (void*)this)
474        pos.throw_invalid((void*)this);
475      Node *p = pos.ptr;
476      n->prev = p->prev;
477      n->next = p;
478    }
479  else
480    {
481      n->prev = head.prev;
482      n->next = 0;
483    }
484  // Link
485  if (n->prev)
486    n->prev->next = n;
487  else
488    head.next = n;
489  if (n->next)
490    n->next->prev = n;
491  else
492    head.prev = n;
493  // Finish
494  nelem += 1;
495}
496
497
498void
499GListBase::insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos)
500{
501  // Check
502  if (!frompos.ptr || frompos.cont != (void*)&fromlist)
503    frompos.throw_invalid((void*)&fromlist);
504  if (pos.ptr && pos.cont != (void*)this)
505    pos.throw_invalid((void*)this);
506  // Update frompos
507  Node *n = frompos.ptr;
508  frompos.ptr = n->next;
509  if (pos.ptr == n) return;
510  // Unlink
511  if (n->next)
512    n->next->prev = n->prev;
513  else
514    fromlist.head.prev = n->prev;
515  if (n->prev)
516    n->prev->next = n->next;
517  else
518    fromlist.head.next = n->next;
519  fromlist.nelem -= 1;
520  // Prepare insertion
521  if (pos.ptr)
522    {
523      Node *p = pos.ptr;
524      n->prev = p->prev;
525      n->next = p;
526    }
527  else
528    {
529      n->prev = head.prev;
530      n->next = 0;
531    }
532  // Link
533  if (n->prev)
534    n->prev->next = n;
535  else
536    head.next = n;
537  if (n->next)
538    n->next->prev = n;
539  else
540    head.prev = n;
541  nelem += 1;
542}
543
544
545void 
546GListBase::del(GPosition &pos)
547{
548  // Check
549  if (!pos.ptr || pos.cont != (void*)this) return;
550  // Unlink
551  Node *n = pos.ptr;
552  if (n->next)
553    n->next->prev = n->prev;
554  else
555    head.prev = n->prev;
556  if (n->prev)
557    n->prev->next = n->next;
558  else
559    head.next = n->next;
560  // Finish
561  nelem -= 1;
562  traits.fini( (void*)n, 1);
563  operator delete ( (void*)n );
564  pos.ptr = 0;
565}
566
567
568GPosition
569GListBase::nth(unsigned int n) const
570{
571  Node *p = 0;
572  if ((int)n < nelem)
573    for (p=head.next; p; p=p->next)
574      if ( n-- == 0)
575        break;
576  return GPosition(p, (void*)this);
577}
578
579
580void 
581GListBase::empty()
582{
583  Node *n=head.next;
584  while (n)
585    {
586      Node *p = n->next;
587      traits.fini( (void*)n, 1 );
588      operator delete ( (void*)n );
589      n = p;
590    }
591  head.next = head.prev = 0;
592  nelem = 0;
593}
594
595
596GListBase & 
597GListBase::operator= (const GListBase & ref)
598{
599  if (this == &ref)
600    return *this;
601  empty();
602  for(Node *n = ref.head.next; n; n=n->next)
603    {
604      Node *m = (Node*) operator new (traits.size);
605      traits.copy( (void*)m, (void*)n, 1, 0);
606      append(m);
607    }
608  return *this;
609}
610
611
612
613
614
615// ------------------------------------------------------------
616// ASSOCIATIVE MAPS
617// ------------------------------------------------------------
618
619
620
621
622GSetBase::GSetBase(const Traits &traits)
623  : traits(traits), nelems(0), nbuckets(0), 
624    gtable(table), first(0)
625{
626  rehash(17);
627}
628
629
630GSetBase::GSetBase(const GSetBase &ref)
631  : traits(ref.traits), 
632    nelems(0), nbuckets(0), gtable(table), first(0)
633{
634  GSetBase::operator= (ref);
635}
636
637
638GSetBase::~GSetBase()
639{
640  G_TRY { empty(); } G_CATCH_ALL { } G_ENDCATCH;
641//  delete [] table;
642}
643
644
645GCONT HNode *
646GSetBase::hashnode(unsigned int hashcode) const
647{
648  int bucket = hashcode % nbuckets;
649  return table[bucket];
650}
651
652GCONT HNode *
653GSetBase::installnode(HNode *n)
654{
655  // Rehash if table is more than 60% full
656  if (nelems*3 > nbuckets*2)
657    rehash( 2*nbuckets - 1 );
658  // Create and insert
659  insertnode(n);
660  return n;
661}
662
663void 
664GSetBase::insertnode(HNode *n)
665{
666  int bucket = n->hashcode % nbuckets;
667  n->prev = n->hprev = table[bucket];
668  if (n->prev) 
669    {
670      // bucket was not empty
671      n->next = n->prev->next;
672      n->prev->next = n;
673      if (n->next)
674        n->next->prev = n;
675    }
676  else
677    {
678      // bucket was empty.
679      n->next = first;
680      first = n;
681      if (n->next)
682        n->next->prev = n;
683    }
684  // finish
685  table[bucket] = n;
686  nelems += 1;
687}
688
689
690void   
691GSetBase::deletenode(GCONT HNode *n)
692{
693  if (n == 0) 
694    return;
695  int bucket = n->hashcode % nbuckets;
696  // Regular links
697  if (n->next)
698    n->next->prev = n->prev;
699  if (n->prev)
700    n->prev->next = n->next;
701  else
702    first = (HNode*)(n->next);
703  // HPrev links
704  if (table[bucket] == n)
705    table[bucket] = n->hprev;
706  else
707    ((HNode*)(n->next))->hprev = n->hprev;
708  // Delete entry
709  traits.fini( (void*)n, 1 );
710  operator delete ( (void*)n );
711  nelems -= 1;
712}
713
714
715void   
716GSetBase::rehash(int newbuckets)
717{
718  // Save chain of nodes
719  Node *n = first;
720  // Simulate an empty map
721  nelems = 0;
722  first = 0;
723  // Allocate a new empty bucket table
724// delete [] table;
725  gtable.resize(0);
726  nbuckets = newbuckets;
727  typedef HNode *HNodePtr;
728// table = new HNodePtr[nbuckets];
729  gtable.resize(nbuckets);
730  gtable.clear();
731//  for (int i=0; i<nbuckets; i++)
732//    table[i] = 0;
733  // Insert saved nodes
734  while (n)
735    {
736      Node *p = n->next;
737      insertnode((HNode*)n);
738      n = p;
739    }
740}
741
742
743GSetBase& 
744GSetBase::operator=(const GSetBase &ref)
745{
746  if (this == &ref) 
747    return *this;
748  empty();
749  rehash(ref.nbuckets);
750  for (Node *n = ref.first; n; n=n->next)
751    {
752      HNode *m = (HNode*) operator new (traits.size);
753      traits.copy( (void*)m, (void*)n, 1, 0);
754      insertnode(m);
755    }
756  return *this;
757}
758
759
760GPosition
761GSetBase::firstpos() const
762{
763  return GPosition(first, (void*)this);
764}
765
766
767void 
768GSetBase::del(GPosition &pos)
769{
770  if (pos.ptr && pos.cont==(void*)this)
771    {
772      deletenode((HNode*)pos.ptr);
773      pos.ptr = 0;
774    }
775}
776
777void 
778GSetBase::empty()
779{
780  HNode *n = first;
781  while (n)
782    {
783      HNode *p = (HNode*)(n->next);
784      traits.fini( (void*)n, 1 );
785      operator delete ( (void*)n );
786      n = p;
787    }
788  first = 0;
789  nelems = 0;
790  gtable.clear();
791//  for (int i=0; i<nbuckets; i++)
792//    table[i] = 0;
793}
794
795
796#ifdef HAVE_NAMESPACES
797}
798# ifndef NOT_USING_DJVU_NAMESPACE
799using namespace DJVU;
800# endif
801#endif
802
Note: See TracBrowser for help on using the repository browser.