xref: /386bsd/usr/include/nonstd/gnu/g++/gen/XPlex.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>.XPlex.h"
29
30
31<T>XPlex:: <T>XPlex()
32{
33  lo = fnc = 0;
34  csize = DEFAULT_INITIAL_CAPACITY;
35  <T>* data = new <T>[csize];
36  set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
37  hd = ch;
38}
39
40<T>XPlex:: <T>XPlex(int chunksize)
41{
42  if (chunksize == 0) error("invalid constructor specification");
43  lo = fnc = 0;
44  if (chunksize > 0)
45  {
46    csize = chunksize;
47    <T>* data = new <T>[csize];
48    set_cache(new <T>IChunk(data,  lo, lo, fnc, csize));
49    hd = ch;
50  }
51  else
52  {
53    csize = -chunksize;
54    <T>* data = new <T>[csize];
55    set_cache(new <T>IChunk(data,  chunksize, lo, fnc, fnc));
56    hd = ch;
57  }
58}
59
60
61<T>XPlex:: <T>XPlex(int l, int chunksize)
62{
63  if (chunksize == 0) error("invalid constructor specification");
64  lo = fnc = l;
65  if (chunksize > 0)
66  {
67    csize = chunksize;
68    <T>* data = new <T>[csize];
69    set_cache(new <T>IChunk(data,  lo, lo, fnc, csize+lo));
70    hd = ch;
71  }
72  else
73  {
74    csize = -chunksize;
75    <T>* data = new <T>[csize];
76    set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
77    hd = ch;
78  }
79}
80
81void <T>XPlex::make_initial_chunks(int up)
82{
83  int need = fnc - lo;
84  hd = 0;
85  if (up)
86  {
87    int l = lo;
88    do
89    {
90      int sz;
91      if (need >= csize)
92        sz = csize;
93      else
94        sz = need;
95      <T>* data = new <T> [csize];
96      <T>IChunk* h = new <T>IChunk(data,  l, l, l+sz, l+csize);
97      if (hd != 0)
98        h->link_to_next(hd);
99      else
100        hd = h;
101      l += sz;
102      need -= sz;
103    } while (need > 0);
104  }
105  else
106  {
107    int hi = fnc;
108    do
109    {
110      int sz;
111      if (need >= csize)
112        sz = csize;
113      else
114        sz = need;
115      <T>* data = new <T> [csize];
116      <T>IChunk* h = new <T>IChunk(data,  hi-csize, hi-sz, hi, hi);
117      if (hd != 0)
118        h->link_to_next(hd);
119      hd = h;
120      hi -= sz;
121      need -= sz;
122    } while (need > 0);
123  }
124  set_cache(hd);
125}
126
127<T>XPlex:: <T>XPlex(int l, int hi, const <T&> initval, int chunksize)
128{
129  lo = l;
130  fnc = hi + 1;
131  if (chunksize == 0)
132  {
133    csize = fnc - l;
134    make_initial_chunks(1);
135  }
136  else if (chunksize < 0)
137  {
138    csize = -chunksize;
139    make_initial_chunks(0);
140  }
141  else
142  {
143    csize = chunksize;
144    make_initial_chunks(1);
145  }
146  fill(initval);
147}
148
149<T>XPlex::<T>XPlex(const <T>XPlex& a)
150{
151  lo = a.lo;
152  fnc = a.fnc;
153  csize = a.csize;
154  make_initial_chunks();
155  for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
156}
157
158void <T>XPlex::operator= (const <T>XPlex& a)
159{
160  if (&a != this)
161  {
162    invalidate();
163    lo = a.lo;
164    fnc = a.fnc;
165    csize = a.csize;
166    make_initial_chunks();
167    for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
168  }
169}
170
171
172void <T>XPlex::cache(int idx) const
173{
174  const <T>IChunk* tail = tl();
175  const <T>IChunk* t = ch;
176  while (idx >= t->fence_index())
177  {
178    if (t == tail) index_error();
179    t = (t->next());
180  }
181  while (idx < t->low_index())
182  {
183    if (t == hd) index_error();
184    t = (t->prev());
185  }
186  set_cache(t);
187}
188
189
190void <T>XPlex::cache(const <T>* p) const
191{
192  const <T>IChunk* old = ch;
193  const <T>IChunk* t = ch;
194  while (!t->actual_pointer(p))
195  {
196    t = (t->next());
197    if (t == old) index_error();
198  }
199  set_cache(t);
200}
201
202int <T>XPlex::owns(Pix px) const
203{
204  <T>* p = (<T>*)px;
205  const <T>IChunk* old = ch;
206  const <T>IChunk* t = ch;
207  while (!t->actual_pointer(p))
208  {
209    t = (t->next());
210    if (t == old) { set_cache(t); return 0; }
211  }
212  set_cache(t);
213  return 1;
214}
215
216
217<T>* <T>XPlex::dosucc(const <T>* p) const
218{
219  if (p == 0) return 0;
220  const <T>IChunk* old = ch;
221  const <T>IChunk* t = ch;
222
223  while (!t->actual_pointer(p))
224  {
225    t = (t->next());
226    if (t == old)  return 0;
227  }
228  int i = t->index_of(p) + 1;
229  if (i >= fnc) return 0;
230  if (i >= t->fence_index()) t = (t->next());
231  set_cache(t);
232  return (t->pointer_to(i));
233}
234
235<T>* <T>XPlex::dopred(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->prev());
243    if (t == old) return 0;
244  }
245  int i = t->index_of(p) - 1;
246  if (i < lo) return 0;
247  if (i < t->low_index()) t = (t->prev());
248  set_cache(t);
249  return (t->pointer_to(i));
250}
251
252
253int <T>XPlex::add_high(const <T&> elem)
254{
255  <T>IChunk* t = tl();
256  if (!t->can_grow_high())
257  {
258    if (t-><T>IChunk::empty() && one_chunk())
259      t->clear(fnc);
260    else
261    {
262      <T>* data = new <T> [csize];
263      t = (new <T>IChunk(data,  fnc, fnc, fnc,fnc+csize));
264      t->link_to_prev(tl());
265    }
266  }
267  *((t-><T>IChunk::grow_high())) = elem;
268  set_cache(t);
269  return fnc++;
270}
271
272int <T>XPlex::del_high ()
273{
274  if (empty()) empty_error();
275  <T>IChunk* t = tl();
276  t-><T>IChunk::shrink_high();
277  if (t-><T>IChunk::empty() && !one_chunk())
278  {
279    <T>IChunk* pred = t->prev();
280    del_chunk(t);
281    t = pred;
282  }
283  set_cache(t);
284  return --fnc - 1;
285}
286
287int <T>XPlex::add_low (const <T&> elem)
288{
289  <T>IChunk* t = hd;
290  if (!t->can_grow_low())
291  {
292    if (t-><T>IChunk::empty() && one_chunk())
293      t->cleardown(lo);
294    else
295    {
296      <T>* data = new <T> [csize];
297      hd = new <T>IChunk(data,  lo-csize, lo, lo, lo);
298      hd->link_to_next(t);
299      t = hd;
300    }
301  }
302  *((t-><T>IChunk::grow_low())) = elem;
303  set_cache(t);
304  return --lo;
305}
306
307
308int <T>XPlex::del_low ()
309{
310  if (empty()) empty_error();
311  <T>IChunk* t = hd;
312  t-><T>IChunk::shrink_low();
313  if (t-><T>IChunk::empty() && !one_chunk())
314  {
315    hd = t->next();
316    del_chunk(t);
317    t = hd;
318  }
319  set_cache(t);
320  return ++lo;
321}
322
323void <T>XPlex::append (const <T>XPlex& a)
324{
325  for (int i = a.low(); i < a.fence(); a.next(i)) add_high(a[i]);
326}
327
328void <T>XPlex::prepend (const <T>XPlex& a)
329{
330  for (int i = a.high(); i > a.ecnef(); a.prev(i)) add_low(a[i]);
331}
332
333void <T>XPlex::reverse()
334{
335  <T> tmp;
336  int l = lo;
337  int h = fnc - 1;
338  <T>IChunk* loch = hd;
339  <T>IChunk* hich = tl();
340  while (l < h)
341  {
342    <T>* lptr = loch->pointer_to(l);
343    <T>* hptr = hich->pointer_to(h);
344    tmp = *lptr;
345    *lptr = *hptr;
346    *hptr = tmp;
347    if (++l >= loch->fence_index()) loch = loch->next();
348    if (--h < hich->low_index()) hich = hich->prev();
349  }
350}
351
352void <T>XPlex::fill(const <T&> x)
353{
354  for (int i = lo; i < fnc; ++i) (*this)[i] = x;
355}
356
357void <T>XPlex::fill(const <T&> x, int l, int hi)
358{
359  for (int i = l; i <= hi; ++i) (*this)[i] = x;
360}
361
362
363void <T>XPlex::clear()
364{
365  if (fnc != lo)
366  {
367    <T>IChunk* t = tl();
368    while (t != hd)
369    {
370      <T>IChunk* prv = t->prev();
371      del_chunk(t);
372      t = prv;
373    }
374    t-><T>IChunk::clear(lo);
375    set_cache(t);
376    fnc = lo;
377  }
378}
379
380
381int <T>XPlex::OK () const
382{
383  int v = hd != 0 && ch != 0;     // at least one chunk
384
385  v &= fnc == tl()->fence_index();// last chunk fence == plex fence
386  v &= lo == ((hd))-><T>IChunk::low_index();    // first lo == plex lo
387
388// loop for others:
389  int found_ch = 0;                   // to make sure ch is in list;
390  const <T>IChunk* t = (hd);
391  for (;;)
392  {
393    if (t == ch) ++found_ch;
394    v &= t-><T>IChunk::OK();              // each chunk is OK
395    if (t == tl())
396      break;
397    else                              // and has indices contiguous to succ
398    {
399      v &= t->top_index() == t->next()->base_index();
400      if (t != hd)                  // internal chunks full
401      {
402        v &= !t->empty();
403        v &= !t->can_grow_low();
404        v &= !t->can_grow_high();
405      }
406      t = t->next();
407    }
408  }
409  v &= found_ch == 1;
410  if (!v) error("invariant failure");
411  return v;
412}
413