xref: /386bsd/usr/src/lib/libg++/g++-include/gen/RPlex.ccP (revision a2142627) 
1// This may look like C code, but it is really -*- C++ -*-
2/*
3Copyright (C) 1988 Free Software Foundation
4    written by Doug Lea (dl@rocky.oswego.edu)
5    based on code by Marc Shapiro (shapiro@sor.inria.fr)
6
7This file is part of GNU CC.
8
9GNU CC is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY.  No author or distributor
11accepts responsibility to anyone for the consequences of using it
12or for whether it serves any particular purpose or works at all,
13unless he says so in writing.  Refer to the GNU CC General Public
14License for full details.
15
16Everyone is granted permission to copy, modify and redistribute
17GNU CC, but only under the conditions described in the
18GNU CC General Public License.   A copy of this license is
19supposed to have been given to you along with GNU CC so you
20can know your rights and responsibilities.  It should be in a
21file named COPYING.  Among other things, the copyright notice
22and this notice must be preserved on all copies.
23*/
24
25#ifdef __GNUG__
26#pragma implementation
27#endif
28#include "<T>.RPlex.h"
29
30typedef <T>IChunk* _<T>IChunk_ptr;
31
32<T>RPlex:: <T>RPlex()
33{
34  lo = fnc = 0;
35  csize = DEFAULT_INITIAL_CAPACITY;
36  <T>* data = new <T>[csize];
37  set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
38  hd = ch;
39  maxch = MIN_NCHUNKS;
40  lch = maxch / 2;
41  fch = lch + 1;
42  base = ch->base_index() - lch * csize;
43  chunks = new _<T>IChunk_ptr[maxch];
44  chunks[lch] = ch;
45}
46
47<T>RPlex:: <T>RPlex(int chunksize)
48{
49  if (chunksize == 0) error("invalid constructor specification");
50  lo = fnc = 0;
51  if (chunksize > 0)
52  {
53    csize = chunksize;
54    <T>* data = new <T>[csize];
55    set_cache(new <T>IChunk(data,  lo, lo, fnc, csize+lo));
56    hd = ch;
57  }
58  else
59  {
60    csize = -chunksize;
61    <T>* data = new <T>[csize];
62    set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
63    hd = ch;
64  }
65  maxch = MIN_NCHUNKS;
66  lch = maxch / 2;
67  fch = lch + 1;
68  base = ch->base_index() - lch * csize;
69  chunks = new _<T>IChunk_ptr[maxch];
70  chunks[lch] = ch;
71}
72
73
74<T>RPlex:: <T>RPlex(int l, int chunksize)
75{
76  if (chunksize == 0) error("invalid constructor specification");
77  lo = fnc = l;
78  if (chunksize > 0)
79  {
80    csize = chunksize;
81    <T>* data = new <T>[csize];
82    set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
83    hd = ch;
84  }
85  else
86  {
87    csize = -chunksize;
88    <T>* data = new <T>[csize];
89    set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
90    hd = ch;
91  }
92  maxch = MIN_NCHUNKS;
93  lch = maxch / 2;
94  fch = lch + 1;
95  base = ch->base_index() - lch * csize;
96  chunks = new _<T>IChunk_ptr[maxch];
97  chunks[lch] = ch;
98}
99
100void <T>RPlex::make_initial_chunks(int up)
101{
102  int count = 0;
103  int need = fnc - lo;
104  hd = 0;
105  if (up)
106  {
107    int l = lo;
108    do
109    {
110      ++count;
111      int sz;
112      if (need >= csize)
113        sz = csize;
114      else
115        sz = need;
116      <T>* data = new <T> [csize];
117      <T>IChunk* h = new <T>IChunk(data,  l, l, l+sz, l+csize);
118      if (hd != 0)
119        h->link_to_next(hd);
120      else
121        hd = h;
122      l += sz;
123      need -= sz;
124    } while (need > 0);
125  }
126  else
127  {
128    int hi = fnc;
129    do
130    {
131      ++count;
132      int sz;
133      if (need >= csize)
134        sz = csize;
135      else
136        sz = need;
137      <T>* data = new <T> [csize];
138      <T>IChunk* h = new <T>IChunk(data,  hi-csize, hi-sz, hi, hi);
139      if (hd != 0)
140        h->link_to_next(hd);
141      hd = h;
142      hi -= sz;
143      need -= sz;
144    } while (need > 0);
145  }
146  set_cache((<T>IChunk*)hd);
147
148  maxch = MIN_NCHUNKS;
149  if (maxch < count * 2)
150    maxch = count * 2;
151  chunks = new _<T>IChunk_ptr[maxch];
152  lch = maxch / 3;
153  fch = lch + count;
154  base = ch->base_index() - csize * lch;
155  int k = lch;
156  do
157  {
158    chunks[k++] = ch;
159    set_cache(ch->next());
160  } while (ch != hd);
161}
162
163<T>RPlex:: <T>RPlex(int l, int hi, const <T&> initval, int chunksize)
164{
165  lo = l;
166  fnc = hi + 1;
167  if (chunksize == 0)
168  {
169    csize = fnc - l;
170    make_initial_chunks(1);
171  }
172  else if (chunksize < 0)
173  {
174    csize = -chunksize;
175    make_initial_chunks(0);
176  }
177  else
178  {
179    csize = chunksize;
180    make_initial_chunks(1);
181  }
182  fill(initval);
183}
184
185<T>RPlex::<T>RPlex(const <T>RPlex& a)
186{
187  lo = a.lo;
188  fnc = a.fnc;
189  csize = a.csize;
190  make_initial_chunks();
191  for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
192}
193
194void <T>RPlex::operator= (const <T>RPlex& a)
195{
196  if (&a != this)
197  {
198    invalidate();
199    lo = a.lo;
200    fnc = a.fnc;
201    csize = a.csize;
202    make_initial_chunks();
203    for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
204  }
205}
206
207
208void <T>RPlex::cache(const <T>* p) const
209{
210  const <T>IChunk* old = ch;
211  const <T>IChunk* t = ch;
212  while (!t->actual_pointer(p))
213  {
214    t = (t->next());
215    if (t == old) index_error();
216  }
217  set_cache(t);
218}
219
220int <T>RPlex::owns(Pix px) const
221{
222  <T>* p = (<T>*)px;
223  const <T>IChunk* old = ch;
224  const <T>IChunk* t = ch;
225  while (!t->actual_pointer(p))
226  {
227    t = (t->next());
228    if (t == old) return 0;
229  }
230  set_cache(t);
231  return 1;
232}
233
234
235<T>* <T>RPlex::dosucc(const <T>* p) const
236{
237  if (p == 0) return 0;
238  const <T>IChunk* old = ch;
239  const <T>IChunk* t = ch;
240  while (!t->actual_pointer(p))
241  {
242    t = (t->next());
243    if (t == old) return 0;
244  }
245  int i = t->index_of(p) + 1;
246  if (i >= fnc) return 0;
247  if (i >= t->fence_index()) t = (t->next());
248  set_cache(t);
249  return t->pointer_to(i);
250}
251
252<T>* <T>RPlex::dopred(const <T>* p) const
253{
254  if (p == 0) return 0;
255  const <T>IChunk* old = ch;
256  const <T>IChunk* t = ch;
257  while (!t->actual_pointer(p))
258  {
259    t = (t->prev());
260    if (t == old) return 0;
261  }
262  int i = t->index_of(p) - 1;
263  if (i < lo) return 0;
264  if (i < t->low_index()) t = (t->prev());
265  set_cache(t);
266  return (t->pointer_to(i));
267}
268
269int <T>RPlex::add_high(const <T&> elem)
270{
271  <T>IChunk* t = tl();
272  if (!t->can_grow_high())
273  {
274    if (t-><T>IChunk::empty() && one_chunk())
275    {
276      t->clear(fnc);
277      base = t->base_index() - lch * csize;
278    }
279    else
280    {
281      <T>* data = new <T> [csize];
282      t = (new <T>IChunk(data,  fnc, fnc, fnc,fnc+csize));
283      t->link_to_prev(tl());
284      if (fch == maxch)
285      {
286        maxch *= 2;
287        <T>IChunk** newch = new _<T>IChunk_ptr [maxch];
288        bcopy(chunks, newch, fch * sizeof(_<T>IChunk_ptr));
289        delete chunks;
290        chunks = newch;
291      }
292      chunks[fch++] = t;
293    }
294  }
295  *((t-><T>IChunk::grow_high())) = elem;
296  set_cache(t);
297  return fnc++;
298}
299
300int <T>RPlex::del_high ()
301{
302  if (empty()) empty_error();
303  <T>IChunk* t = tl();
304  if (t-><T>IChunk::empty()) // kill straggler first
305  {
306    <T>IChunk* pred = t->prev();
307    del_chunk(t);
308    t = (pred);
309    --fch;
310  }
311  t-><T>IChunk::shrink_high();
312  if (t-><T>IChunk::empty() && !one_chunk())
313  {
314    <T>IChunk* pred = t->prev();
315    del_chunk(t);
316    t = (pred);
317    --fch;
318  }
319  set_cache(t);
320  return --fnc - 1;
321}
322
323int <T>RPlex::add_low (const <T&> elem)
324{
325  <T>IChunk* t = hd;
326  if (!t->can_grow_low())
327  {
328    if (t-><T>IChunk::empty() && one_chunk())
329    {
330      t->cleardown(lo);
331      base = t->base_index() - lch * csize;
332    }
333    else
334    {
335      <T>* data = new <T> [csize];
336      hd = new <T>IChunk(data,  lo-csize, lo, lo, lo);
337      hd->link_to_next(t);
338      t = ( hd);
339      if (lch == 0)
340      {
341        lch = maxch;
342        fch += maxch;
343        maxch *= 2;
344        <T>IChunk** newch = new _<T>IChunk_ptr [maxch];
345        bcopy(chunks, &(newch[lch]), lch * sizeof(_<T>IChunk_ptr));
346        delete chunks;
347        chunks = newch;
348        base = t->base_index() - (lch - 1) * csize;
349      }
350      chunks[--lch] = t;
351    }
352  }
353  *((t-><T>IChunk::grow_low())) = elem;
354  set_cache(t);
355  return --lo;
356}
357
358
359int <T>RPlex::del_low ()
360{
361  if (empty()) empty_error();
362  <T>IChunk* t = hd;
363  if (t-><T>IChunk::empty())
364  {
365    hd = t->next();
366    del_chunk(t);
367    t = hd;
368    ++lch;
369  }
370  t-><T>IChunk::shrink_low();
371  if (t-><T>IChunk::empty() && !one_chunk())
372  {
373    hd = t->next();
374    del_chunk(t);
375    t = hd;
376    ++lch;
377  }
378  set_cache(t);
379  return ++lo;
380}
381
382void <T>RPlex::append(const <T>RPlex& a)
383{
384  for (int i = a.low(); i < a.fence(); a.next(i)) add_high(a[i]);
385}
386
387void <T>RPlex::prepend (const <T>RPlex& a)
388{
389  for (int i = a.high(); i > a.ecnef(); a.prev(i)) add_low(a[i]);
390}
391
392void <T>RPlex::reverse()
393{
394  <T> tmp;
395  int l = lo;
396  int h = fnc - 1;
397  <T>IChunk* loch = hd;
398  <T>IChunk* hich = tl();
399  while (l < h)
400  {
401    <T>* lptr = loch->pointer_to(l);
402    <T>* hptr = hich->pointer_to(h);
403    tmp = *lptr;
404    *lptr = *hptr;
405    *hptr = tmp;
406    if (++l >= loch->fence_index()) loch = loch->next();
407    if (--h < hich->low_index()) hich = hich->prev();
408  }
409}
410
411void <T>RPlex::fill(const <T&> x)
412{
413  for (int i = lo; i < fnc; ++i) (*this)[i] = x;
414}
415
416void <T>RPlex::fill(const <T&> x, int lo, int hi)
417{
418  for (int i = lo; i <= hi; ++i) (*this)[i] = x;
419}
420
421
422void <T>RPlex::clear()
423{
424  for (int i = lch + 1; i < fch; ++i)
425    del_chunk(chunks[i]);
426  fch = lch + 1;
427  set_cache(chunks[lch]);
428  ch-><T>IChunk::clear(lo);
429  fnc = lo;
430}
431
432int <T>RPlex::reset_low(int l)
433{
434  int old = lo;
435  int diff = l - lo;
436  if (diff != 0)
437  {
438    lo += diff;
439    fnc += diff;
440    <T>IChunk* t = hd;
441    do
442    {
443      t->re_index(t->low_index() + diff);
444      t = t->next();
445    } while (t != hd);
446  }
447  base = hd->base_index() - lch * csize;
448  return old;
449}
450
451
452int <T>RPlex::OK () const
453{
454  int v = hd != 0 && ch != 0;         // at least one chunk
455
456  v &= fnc == tl()->fence_index();  // last chunk fnc == plex fnc
457  v &= lo == hd-><T>IChunk::low_index();    // first lo == plex lo
458
459  v &= base == hd->base_index() - lch * csize; // base is correct;
460  v &= lch < fch;
461  v &= fch <= maxch;                  // within allocation;
462
463// loop for others:
464
465  int k = lch;                        // to cross-check nch
466
467  int found_ch = 0;                   // to make sure ch is in list;
468  const <T>IChunk* t = (hd);
469  for (;;)
470  {
471    v &= chunks[k++] == t;             // each chunk is at proper index
472    if (t == ch) ++found_ch;
473    v &= t-><T>IChunk::OK();              // each chunk is OK
474    if (t == tl())
475      break;
476    else                              // and has indices contiguous to succ
477    {
478      v &= t->top_index() == t->next()->base_index();
479      if (t != hd)                  // internal chunks full
480      {
481        v &= !t->empty();
482        v &= !t->can_grow_low();
483        v &= !t->can_grow_high();
484      }
485      t = t->next();
486    }
487  }
488  v &= found_ch == 1;
489  v &= fch == k;
490  if (!v) error("invariant failure");
491  return v;
492}
493