Commit | Line | Data |
---|---|---|
e87b4ac1 PR |
1 | // This may look like C code, but it is really -*- C++ -*- |
2 | /* | |
3 | Copyright (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 | ||
7 | This file is part of the GNU C++ Library. This library is free | |
8 | software; you can redistribute it and/or modify it under the terms of | |
9 | the GNU Library General Public License as published by the Free | |
10 | Software Foundation; either version 2 of the License, or (at your | |
11 | option) any later version. This library is distributed in the hope | |
12 | that it will be useful, but WITHOUT ANY WARRANTY; without even the | |
13 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
14 | PURPOSE. See the GNU Library General Public License for more details. | |
15 | You should have received a copy of the GNU Library General Public | |
16 | License along with this library; if not, write to the Free Software | |
17 | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
18 | */ | |
19 | ||
20 | #ifdef __GNUG__ | |
21 | #pragma implementation | |
22 | #endif | |
23 | #include "<T>.MPlex.h" | |
24 | ||
25 | // <T>MChunk support | |
26 | ||
27 | ||
28 | <T>MChunk::<T>MChunk(<T>* d, | |
29 | int baseidx, | |
30 | int lowidx, | |
31 | int fenceidx, | |
32 | int topidx) | |
33 | : <T>IChunk(d, baseidx, lowidx, fenceidx, topidx) | |
34 | { | |
35 | unused = fence - low; | |
36 | unsigned msize = (top - base)/_MAP_BITS + 1; | |
37 | map = (unsigned long *) (new long[msize]); | |
38 | memset((void*)map, 0, msize * sizeof(long)); | |
39 | } | |
40 | ||
41 | void <T>MChunk:: shrink_high () | |
42 | { | |
43 | if (fence <= low) empty_error(); | |
44 | --fence; | |
45 | if (!valid(fence)) | |
46 | --unused; | |
47 | else | |
48 | free(fence); | |
49 | reset_high(); | |
50 | } | |
51 | ||
52 | void <T>MChunk:: shrink_low () | |
53 | { | |
54 | if (fence <= low) empty_error(); | |
55 | if (!valid(low)) | |
56 | --unused; | |
57 | else | |
58 | free(low); | |
59 | ++low; | |
60 | reset_low(); | |
61 | } | |
62 | ||
63 | void <T>MChunk::clear(int lo) | |
64 | { | |
65 | int s = top - base; | |
66 | low = base = fence = lo; | |
67 | top = base + s; | |
68 | unused = 0; | |
69 | memset((void*)map, 0, ((top - base)/_MAP_BITS + 1) * sizeof(long)); | |
70 | } | |
71 | ||
72 | void <T>MChunk::cleardown(int hi) | |
73 | { | |
74 | int s = top - base; | |
75 | low = top = fence = hi; | |
76 | base = top - s; | |
77 | unused = 0; | |
78 | memset((void*)map, 0, ((top - base)/_MAP_BITS + 1) * sizeof(long)); | |
79 | } | |
80 | ||
81 | int <T>MChunk::del(int idx) | |
82 | { | |
83 | if (idx < low || idx >= fence) index_error(); | |
84 | int v = valid(idx); | |
85 | if (v) | |
86 | { | |
87 | free(idx); | |
88 | ++unused; | |
89 | } | |
90 | return v; | |
91 | } | |
92 | ||
93 | ||
94 | int <T>MChunk::undel(int idx) | |
95 | { | |
96 | if (idx < low || idx >= fence) index_error(); | |
97 | int v = valid(idx); | |
98 | if (!v) | |
99 | { | |
100 | mark(idx); | |
101 | --unused; | |
102 | } | |
103 | return v; | |
104 | } | |
105 | ||
106 | int <T>MChunk::unused_index() const | |
107 | { | |
108 | if (unused_indices() == 0) index_error(); | |
109 | int slot; | |
110 | if (low == base) // can traverse 32 slots at a time | |
111 | { | |
112 | int blk = 0; | |
113 | while (map[blk] == ~0L) ++blk; | |
114 | slot = blk * _MAP_BITS + base; | |
115 | } | |
116 | else | |
117 | slot = low; | |
118 | ||
119 | while(valid(slot)) ++slot; | |
120 | return slot; | |
121 | } | |
122 | ||
123 | int <T>MChunk::first_index() const | |
124 | { | |
125 | if (empty()) return fence; | |
126 | int slot; | |
127 | if (low == base) | |
128 | { | |
129 | int blk = 0; | |
130 | while (map[blk] == 0) ++blk; | |
131 | slot = blk * _MAP_BITS + base; | |
132 | } | |
133 | else | |
134 | slot = low; | |
135 | ||
136 | while(!valid(slot)) ++slot; | |
137 | return slot; | |
138 | } | |
139 | ||
140 | int <T>MChunk::last_index() const | |
141 | { | |
142 | if (empty()) return low - 1; | |
143 | int slot; | |
144 | if (top == fence) | |
145 | { | |
146 | int blk = (top - base) / _MAP_BITS; | |
147 | while (map[blk] == 0) --blk; | |
148 | slot = blk * _MAP_BITS + base + _MAP_BITS - 1; | |
149 | } | |
150 | else | |
151 | slot = fence - 1; | |
152 | ||
153 | while(!valid(slot)) --slot; | |
154 | return slot; | |
155 | } | |
156 | ||
157 | ||
158 | int <T>MChunk:: OK() const | |
159 | { | |
160 | int v = data != 0; // have some data | |
161 | v &= map != 0; // and a map | |
162 | v &= base <= low; // ok, index-wise | |
163 | v &= low <= fence; | |
164 | v &= fence <= top; | |
165 | ||
166 | v &= ((<T>MChunk*)(nxt->prev())) == this; // and links are OK | |
167 | v &= ((<T>MChunk*)(prv->next())) == this; | |
168 | ||
169 | int bitcount = 0; // and unused count correct | |
170 | for (int i = low; i < fence; ++i) if (!valid(i)) ++bitcount; | |
171 | v &= unused == bitcount; | |
172 | ||
173 | if (!v) error("invariant failure"); | |
174 | return(v); | |
175 | } | |
176 | ||
177 | <T>* <T>MChunk::succ(<T>* p) const | |
178 | { | |
179 | int i = ((int) p - (int) data) / sizeof(<T>) + base + 1; | |
180 | if (p == 0 || i < low) return 0; | |
181 | while (i < fence && !valid(i)) ++i; | |
182 | if (i >= fence) return 0; | |
183 | return pointer_to(i); | |
184 | } | |
185 | ||
186 | <T>* <T>MChunk::pred(<T>* p) const | |
187 | { | |
188 | int i = ((int) p - (int) data) / sizeof(<T>) + base - 1; | |
189 | if (p == 0 || i >= fence) return 0; | |
190 | while (i >= low && !valid(i)) --i; | |
191 | if (i < low) return 0; | |
192 | return pointer_to(i); | |
193 | } | |
194 | ||
195 | <T>* <T>MChunk::first_pointer() const | |
196 | { | |
197 | if (empty()) return 0; | |
198 | int slot; | |
199 | if (low == base) | |
200 | { | |
201 | int blk = 0; | |
202 | while (map[blk] == 0) ++blk; | |
203 | slot = blk * _MAP_BITS + base; | |
204 | } | |
205 | else | |
206 | slot = low; | |
207 | ||
208 | while(!valid(slot)) ++slot; | |
209 | return pointer_to(slot); | |
210 | } | |
211 | ||
212 | <T>* <T>MChunk::last_pointer() const | |
213 | { | |
214 | if (empty()) return 0; | |
215 | int slot; | |
216 | if (top == fence) | |
217 | { | |
218 | int blk = (top - base) / _MAP_BITS; | |
219 | while (map[blk] == 0) --blk; | |
220 | slot = blk * _MAP_BITS + base + _MAP_BITS - 1; | |
221 | } | |
222 | else | |
223 | slot = fence - 1; | |
224 | ||
225 | while(!valid(slot)) --slot; | |
226 | return pointer_to(slot); | |
227 | } | |
228 | ||
229 | <T>MPlex:: <T>MPlex() | |
230 | { | |
231 | unused = 0; | |
232 | lo = fnc = 0; | |
233 | csize = DEFAULT_INITIAL_CAPACITY; | |
234 | <T>* data = new <T>[csize]; | |
235 | hd = ch = new <T>MChunk(data, lo, lo, fnc, lo+csize); | |
236 | } | |
237 | ||
238 | <T>MPlex:: <T>MPlex(int chunksize) | |
239 | { | |
240 | if (chunksize == 0) error("invalid constructor specification"); | |
241 | unused = 0; | |
242 | lo = fnc = 0; | |
243 | if (chunksize > 0) | |
244 | { | |
245 | csize = chunksize; | |
246 | <T>* data = new <T>[csize]; | |
247 | hd = ch = new <T>MChunk(data, lo, lo, fnc, csize); | |
248 | } | |
249 | else | |
250 | { | |
251 | csize = -chunksize; | |
252 | <T>* data = new <T>[csize]; | |
253 | hd = ch = new <T>MChunk(data, chunksize, lo, fnc, fnc); | |
254 | } | |
255 | } | |
256 | ||
257 | ||
258 | <T>MPlex:: <T>MPlex(int l, int chunksize) | |
259 | { | |
260 | if (chunksize == 0) error("invalid constructor specification"); | |
261 | unused = 0; | |
262 | lo = fnc = l; | |
263 | if (chunksize > 0) | |
264 | { | |
265 | csize = chunksize; | |
266 | <T>* data = new <T>[csize]; | |
267 | hd = ch = new <T>MChunk(data, lo, lo, fnc, csize+lo); | |
268 | } | |
269 | else | |
270 | { | |
271 | csize = -chunksize; | |
272 | <T>* data = new <T>[csize]; | |
273 | hd = ch = new <T>MChunk(data, chunksize+lo, lo, fnc, fnc); | |
274 | } | |
275 | } | |
276 | ||
277 | ||
278 | void <T>MPlex::make_initial_chunks(int up) | |
279 | { | |
280 | int need = fnc - lo; | |
281 | hd = 0; | |
282 | if (up) | |
283 | { | |
284 | int l = lo; | |
285 | do | |
286 | { | |
287 | int sz; | |
288 | if (need >= csize) | |
289 | sz = csize; | |
290 | else | |
291 | sz = need; | |
292 | <T>* data = new <T> [csize]; | |
293 | <T>MChunk* h = new <T>MChunk(data, l, l, l+sz, l+csize); | |
294 | if (hd != 0) | |
295 | h->link_to_next(hd); | |
296 | else | |
297 | hd = h; | |
298 | l += sz; | |
299 | need -= sz; | |
300 | } while (need > 0); | |
301 | } | |
302 | else | |
303 | { | |
304 | int hi = fnc; | |
305 | do | |
306 | { | |
307 | int sz; | |
308 | if (need >= csize) | |
309 | sz = csize; | |
310 | else | |
311 | sz = need; | |
312 | <T>* data = new <T> [csize]; | |
313 | <T>MChunk* h = new <T>MChunk(data, hi-csize, hi-sz, hi, hi); | |
314 | if (hd != 0) | |
315 | h->link_to_next(hd); | |
316 | hd = h; | |
317 | hi -= sz; | |
318 | need -= sz; | |
319 | } while (need > 0); | |
320 | } | |
321 | ch = (<T>MChunk*) hd; | |
322 | } | |
323 | ||
324 | <T>MPlex:: <T>MPlex(int l, int hi, const <T&> initval, int chunksize) | |
325 | { | |
326 | lo = l; | |
327 | fnc = hi + 1; | |
328 | if (chunksize == 0) | |
329 | { | |
330 | csize = fnc - l; | |
331 | make_initial_chunks(1); | |
332 | } | |
333 | else if (chunksize < 0) | |
334 | { | |
335 | csize = -chunksize; | |
336 | make_initial_chunks(0); | |
337 | } | |
338 | else | |
339 | { | |
340 | csize = chunksize; | |
341 | make_initial_chunks(1); | |
342 | } | |
343 | unused = fnc - lo; | |
344 | for (int i=lo; i<fnc; ++i) | |
345 | undel_index(i); | |
346 | fill(initval); | |
347 | } | |
348 | ||
349 | <T>MPlex::<T>MPlex(const <T>MPlex& a) | |
350 | { | |
351 | lo = a.lo; | |
352 | fnc = a.fnc; | |
353 | csize = a.csize; | |
354 | unused = fnc - lo; | |
355 | hd = 0; | |
356 | const <T>IChunk* p = a.hd; | |
357 | do | |
358 | { | |
359 | <T>* data = new <T> [p->size()]; | |
360 | <T>MChunk* h = new <T>MChunk(data, p->base_index(), | |
361 | p->low_index(), p->fence_index(), p->top_index()); | |
362 | if (hd != 0) | |
363 | h->link_to_next(hd); | |
364 | else | |
365 | hd = h; | |
366 | p = p->next(); | |
367 | } while (p != a.hd); | |
368 | ch = (<T>MChunk*) hd; | |
369 | for (int i = a.low(); i < a.fence(); a.next(i)) | |
370 | { | |
371 | undel_index(i); | |
372 | (*this)[i] = a[i]; | |
373 | } | |
374 | } | |
375 | ||
376 | void <T>MPlex::operator= (const <T>MPlex& a) | |
377 | { | |
378 | if (&a != this) | |
379 | { | |
380 | invalidate(); | |
381 | lo = a.lo; | |
382 | fnc = a.fnc; | |
383 | csize = a.csize; | |
384 | unused = fnc - lo; | |
385 | hd = 0; | |
386 | const <T>IChunk* p = a.hd; | |
387 | do | |
388 | { | |
389 | <T>* data = new <T> [p->size()]; | |
390 | <T>MChunk* h = new <T>MChunk(data, p->base_index(), | |
391 | p->low_index(), p->fence_index(), | |
392 | p->top_index()); | |
393 | if (hd != 0) | |
394 | h->link_to_next(hd); | |
395 | else | |
396 | hd = h; | |
397 | p = p->next(); | |
398 | } while (p != a.hd); | |
399 | ch = (<T>MChunk*) hd; | |
400 | for (int i = a.low(); i < a.fence(); a.next(i)) | |
401 | { | |
402 | undel_index(i); | |
403 | (*this)[i] = a[i]; | |
404 | } | |
405 | } | |
406 | } | |
407 | ||
408 | int <T>MPlex::valid(int idx) const | |
409 | { | |
410 | const <T>MChunk* tail = (<T>MChunk*)tl(); | |
411 | const <T>MChunk* t = ch; | |
412 | while (idx >= t->fence_index()) | |
413 | { | |
414 | if (t == tail) return 0; | |
415 | t = ((<T>MChunk*)(t->next())); | |
416 | } | |
417 | while (idx < t->low_index()) | |
418 | { | |
419 | if (t == (<T>MChunk*)(hd)) return 0; | |
420 | t = ((<T>MChunk*)(t->prev())); | |
421 | } | |
422 | set_cache(t); | |
423 | return t-><T>MChunk::valid_index(idx); | |
424 | } | |
425 | ||
426 | void <T>MPlex::cache(int idx) const | |
427 | { | |
428 | const <T>MChunk* tail = (<T>MChunk*)tl(); | |
429 | const <T>MChunk* t = ch; | |
430 | while (idx >= t->fence_index()) | |
431 | { | |
432 | if (t == tail) index_error(); | |
433 | t = ((<T>MChunk*)(t->next())); | |
434 | } | |
435 | while (idx < t->low_index()) | |
436 | { | |
437 | if (t == (<T>MChunk*)hd) index_error(); | |
438 | t = ((<T>MChunk*)(t->prev())); | |
439 | } | |
440 | if (!t-><T>MChunk::valid_index(idx)) index_error(); | |
441 | set_cache(t); | |
442 | } | |
443 | ||
444 | void <T>MPlex::cache(const <T>* p) const | |
445 | { | |
446 | const <T>MChunk* old = ch; | |
447 | const <T>MChunk* t = ch; | |
448 | while (!t->actual_pointer(p)) | |
449 | { | |
450 | t = ((<T>MChunk*)(t->next())); | |
451 | if (t == old) index_error(); | |
452 | } | |
453 | if (!t-><T>MChunk::valid_pointer(p)) index_error(); | |
454 | set_cache(t); | |
455 | } | |
456 | ||
457 | int <T>MPlex::owns(Pix px) const | |
458 | { | |
459 | <T>* p = (<T>*)px; | |
460 | const <T>MChunk* old = ch; | |
461 | const <T>MChunk* t = ch; | |
462 | while (!t->actual_pointer(p)) | |
463 | { | |
464 | t = ((<T>MChunk*)(t->next())); | |
465 | if (t == old) return 0; | |
466 | } | |
467 | set_cache(t); | |
468 | return t-><T>MChunk::valid_pointer(p); | |
469 | } | |
470 | ||
471 | int <T>MPlex::add_high(const <T&> elem) | |
472 | { | |
473 | <T>MChunk* t = ((<T>MChunk*) tl()); | |
474 | ||
475 | if (!t->can_grow_high()) | |
476 | { | |
477 | <T>* data = new <T> [csize]; | |
478 | t = (new <T>MChunk(data, fnc,fnc,fnc,fnc+csize)); | |
479 | t->link_to_prev(tl()); | |
480 | } | |
481 | ||
482 | *((t-><T>MChunk::grow_high())) = elem; | |
483 | set_cache(t); | |
484 | return fnc++; | |
485 | } | |
486 | ||
487 | int <T>MPlex::add_low (const <T&> elem) | |
488 | { | |
489 | <T>MChunk* t = ((<T>MChunk*) hd); | |
490 | if (!t->can_grow_low()) | |
491 | { | |
492 | <T>* data = new <T> [csize]; | |
493 | hd = new <T>MChunk(data, lo-csize, lo, lo, lo); | |
494 | hd->link_to_next(t); | |
495 | t = ((<T>MChunk*) hd); | |
496 | } | |
497 | ||
498 | *((t-><T>MChunk::grow_low())) = elem; | |
499 | set_cache(t); | |
500 | return --lo; | |
501 | } | |
502 | ||
503 | void <T>MPlex::adjust_bounds() | |
504 | { | |
505 | <T>MChunk* t = ((<T>MChunk*) tl()); | |
506 | ||
507 | // clean up tail | |
508 | ||
509 | t->reset_high(); | |
510 | while (t-><T>MChunk::empty() && !one_chunk()) | |
511 | { | |
512 | <T>MChunk* pred = (<T>MChunk*)(t->prev()); | |
513 | del_chunk(t); | |
514 | pred->reset_high(); | |
515 | t = (pred); | |
516 | } | |
517 | if (one_chunk()) | |
518 | t->reset_high(); | |
519 | ||
520 | int oldfnc = fnc; | |
521 | fnc = t->fence_index(); | |
522 | unused -= oldfnc - fnc; | |
523 | ||
524 | // and head.. | |
525 | t = ((<T>MChunk*) hd); | |
526 | t->reset_low(); | |
527 | while (t-><T>MChunk::empty() && !one_chunk()) | |
528 | { | |
529 | hd = (<T>MChunk*)(t->next()); | |
530 | del_chunk(t); | |
531 | t = ((<T>MChunk*) hd); | |
532 | t->reset_low(); | |
533 | } | |
534 | ||
535 | int oldlo = lo; | |
536 | lo = t->low_index(); | |
537 | unused -= lo - oldlo; | |
538 | ||
539 | ||
540 | set_cache(t); | |
541 | } | |
542 | ||
543 | int <T>MPlex::del_high () | |
544 | { | |
545 | if (empty()) empty_error(); | |
546 | <T>MChunk* t = ((<T>MChunk*) tl()); | |
547 | while (t-><T>MChunk::empty() && !one_chunk()) // possible stragglers | |
548 | { | |
549 | <T>MChunk* pred = (<T>MChunk*)(t->prev()); | |
550 | del_chunk(t); | |
551 | pred->reset_high(); | |
552 | t = (pred); | |
553 | } | |
554 | t-><T>MChunk::shrink_high(); | |
555 | while (t-><T>MChunk::empty() && !one_chunk()) | |
556 | { | |
557 | <T>MChunk* pred = (<T>MChunk*)(t->prev()); | |
558 | del_chunk(t); | |
559 | pred->reset_high(); | |
560 | t = (pred); | |
561 | } | |
562 | int oldfnc = fnc; | |
563 | fnc = t->fence_index(); | |
564 | unused -= oldfnc - fnc - 1; | |
565 | set_cache(t); | |
566 | return fnc - 1; | |
567 | } | |
568 | ||
569 | int <T>MPlex::del_low () | |
570 | { | |
571 | if (empty()) empty_error(); | |
572 | <T>MChunk* t = ((<T>MChunk*) hd); | |
573 | while (t-><T>MChunk::empty() && !one_chunk()) | |
574 | { | |
575 | hd = (<T>MChunk*)(t->next()); | |
576 | del_chunk(t); | |
577 | t = ((<T>MChunk*) hd); | |
578 | t->reset_low(); | |
579 | } | |
580 | t-><T>MChunk::shrink_low(); | |
581 | while (t-><T>MChunk::empty() && !one_chunk()) | |
582 | { | |
583 | hd = (<T>MChunk*)(t->next()); | |
584 | del_chunk(t); | |
585 | t = ((<T>MChunk*) hd); | |
586 | t->reset_low(); | |
587 | } | |
588 | int oldlo = lo; | |
589 | lo = t->low_index(); | |
590 | unused -= lo - oldlo - 1; | |
591 | set_cache(t); | |
592 | return lo; | |
593 | } | |
594 | ||
595 | int <T>MPlex::add(const <T&> elem) | |
596 | { | |
597 | if (unused == 0) | |
598 | return add_high(elem); | |
599 | ||
600 | for(<T>MChunk* t = ch; | |
601 | t->unused_indices() == 0; | |
602 | t = (<T>MChunk*)(t->prev())) | |
603 | ; | |
604 | ||
605 | int i = t->unused_index(); | |
606 | set_cache(t); | |
607 | undel_index(i); | |
608 | (*this)[i] = elem; | |
609 | return i; | |
610 | } | |
611 | ||
612 | int <T>MPlex::unused_index() const | |
613 | { | |
614 | if (unused == 0) index_error(); | |
615 | ||
616 | for(<T>MChunk* t = ch; | |
617 | t->unused_indices() == 0; | |
618 | t = (<T>MChunk*)(t->prev())) | |
619 | ; | |
620 | ||
621 | set_cache(t); | |
622 | return t->unused_index(); | |
623 | } | |
624 | ||
625 | Pix <T>MPlex::unused_Pix() const | |
626 | { | |
627 | if (unused == 0) return 0; | |
628 | ||
629 | for(<T>MChunk* t = ch; | |
630 | t->unused_indices() == 0; | |
631 | t = (<T>MChunk*)(t->prev())) | |
632 | ; | |
633 | ||
634 | set_cache(t); | |
635 | return t->pointer_to(t->unused_index()); | |
636 | } | |
637 | ||
638 | int <T>MPlex::del_index(int idx) | |
639 | { | |
640 | if (idx < lo || idx >= fnc) index_error(); | |
641 | if (<T>MPlex::valid(idx)) | |
642 | { | |
643 | ++unused; | |
644 | ch-><T>MChunk::del(idx); | |
645 | return 1; | |
646 | } | |
647 | else | |
648 | return 0; | |
649 | } | |
650 | ||
651 | int <T>MPlex::dopred(int idx) const | |
652 | { | |
653 | ||
654 | if (idx >= fnc) idx = fnc; | |
655 | if (idx <= lo) return lo - 1; | |
656 | ||
657 | const <T>MChunk* t = ch; | |
658 | ||
659 | while (idx > t->fence_index()) | |
660 | { | |
661 | t = ((<T>MChunk*)(t->next())); | |
662 | } | |
663 | while (idx <= t->low_index()) | |
664 | { | |
665 | t = ((<T>MChunk*)(t->prev())); | |
666 | } | |
667 | int i = t-><T>MChunk::pred(idx); | |
668 | while (i < t->low_index() && i >= lo) | |
669 | { | |
670 | t = ((<T>MChunk*)(t->prev())); | |
671 | i = t-><T>MChunk::last_index(); | |
672 | } | |
673 | set_cache(t); | |
674 | return i; | |
675 | } | |
676 | ||
677 | ||
678 | int <T>MPlex::dosucc(int idx) const | |
679 | { | |
680 | if (idx < lo) idx = lo; | |
681 | if (idx >= fnc - 1) return fnc; | |
682 | ||
683 | const <T>MChunk* t = ch; | |
684 | while (idx >= t->fence_index()) | |
685 | { | |
686 | t = ((<T>MChunk*)(t->next())); | |
687 | } | |
688 | while (idx < t->low_index()) | |
689 | { | |
690 | t = ((<T>MChunk*)(t->prev())); | |
691 | } | |
692 | int i = t-><T>MChunk::succ(idx); | |
693 | while (i >= t->fence_index() && i < fnc) | |
694 | { | |
695 | t = (<T>MChunk*)(t->next()); | |
696 | i = t-><T>MChunk::first_index(); | |
697 | } | |
698 | set_cache(t); | |
699 | return i; | |
700 | } | |
701 | ||
702 | void <T>MPlex::prev(Pix& i) const | |
703 | { | |
704 | if (i == 0) return; | |
705 | ||
706 | <T>* p = (<T>*) i; | |
707 | const <T>MChunk* old = ch; | |
708 | const <T>MChunk* t = ch; | |
709 | ||
710 | while (!t->actual_pointer(p)) | |
711 | { | |
712 | t = ((<T>MChunk*)(t->prev())); | |
713 | if (t == old) | |
714 | { | |
715 | i = 0; | |
716 | return; | |
717 | } | |
718 | } | |
719 | <T>* q = t-><T>MChunk::pred(p); | |
720 | while (q == 0 && t != (<T>MChunk*)hd) | |
721 | { | |
722 | t = ((<T>MChunk*)(t->prev())); | |
723 | q = t-><T>MChunk::last_pointer(); | |
724 | } | |
725 | ||
726 | i = Pix(q); | |
727 | set_cache(t); | |
728 | return; | |
729 | } | |
730 | ||
731 | void <T>MPlex::next(Pix& i) const | |
732 | { | |
733 | if (i == 0) return; | |
734 | ||
735 | <T>* p = (<T>*) i; | |
736 | const <T>MChunk* tail = (<T>MChunk*)(tl()); | |
737 | const <T>MChunk* old = ch; | |
738 | const <T>MChunk* t = ch; | |
739 | ||
740 | while (!t->actual_pointer(p)) | |
741 | { | |
742 | t = ((<T>MChunk*)(t->next())); | |
743 | if (t == old) | |
744 | { | |
745 | i = 0; | |
746 | return; | |
747 | } | |
748 | } | |
749 | <T>* q = t-><T>MChunk::succ(p); | |
750 | while (q == 0 && t != tail) | |
751 | { | |
752 | t = ((<T>MChunk*)(t->next())); | |
753 | q = t-><T>MChunk::first_pointer(); | |
754 | } | |
755 | ||
756 | i = Pix(q); | |
757 | set_cache(t); | |
758 | return; | |
759 | } | |
760 | ||
761 | ||
762 | void <T>MPlex::undel_index(int idx) | |
763 | { | |
764 | if (idx < lo || idx >= fnc) index_error(); | |
765 | ||
766 | <T>MChunk* t = ch; | |
767 | while (idx >= t->fence_index()) | |
768 | { | |
769 | t = ((<T>MChunk*)(t->next())); | |
770 | } | |
771 | while (idx < t->low_index()) | |
772 | { | |
773 | t = ((<T>MChunk*)(t->prev())); | |
774 | } | |
775 | int was_present = t-><T>MChunk::undel(idx); | |
776 | if (!was_present) | |
777 | { | |
778 | --unused; | |
779 | } | |
780 | set_cache(t); | |
781 | return; | |
782 | } | |
783 | ||
784 | void <T>MPlex::clear() | |
785 | { | |
786 | if (fnc != lo) | |
787 | { | |
788 | <T>MChunk* t = ((<T>MChunk*)tl()); | |
789 | while (t != hd) | |
790 | { | |
791 | <T>MChunk* prv = (<T>MChunk*)(t->prev()); | |
792 | del_chunk(t); | |
793 | t = prv; | |
794 | } | |
795 | t-><T>MChunk::clear(lo); | |
796 | set_cache(t); | |
797 | fnc = lo; | |
798 | unused = 0; | |
799 | } | |
800 | } | |
801 | ||
802 | int <T>MPlex::OK () const | |
803 | { | |
804 | int v = hd != 0; // at least one chunk | |
805 | ||
806 | int found_ch = 0; // to make sure ch is in list; | |
807 | ||
808 | int count = 0; // to count unused slots | |
809 | ||
810 | const <T>MChunk* t = (<T>MChunk*)(hd); | |
811 | ||
812 | int gap = t->low_index() - lo; | |
813 | v &= gap == 0; // hd lo not less than lo. | |
814 | count += gap; | |
815 | ||
816 | for (;;) | |
817 | { | |
818 | if (t == ch) ++found_ch; | |
819 | v &= t-><T>MChunk::OK(); // each chunk is OK | |
820 | count += t->unused_indices(); | |
821 | if (t == (<T>MChunk*)(tl())) | |
822 | break; | |
823 | else // and has indices less than succ | |
824 | { | |
825 | gap = t->next()->base_index() - t->top_index(); | |
826 | v &= gap == 0; | |
827 | count += gap; | |
828 | ||
829 | if (t != (<T>MChunk*)hd) // internal chunks can't grow | |
830 | v &= !t->can_grow_low() && !t->can_grow_high(); | |
831 | ||
832 | t = (const <T>MChunk*)(t->next()); | |
833 | } | |
834 | } | |
835 | gap = fnc - t->fence_index(); | |
836 | v &= gap == 0; | |
837 | count += gap; | |
838 | ||
839 | v &= count == unused; // chunk counts agree with plex | |
840 | ||
841 | v &= found_ch == 1; | |
842 | if (!v) error("invariant failure"); | |
843 | return v; | |
844 | } | |
845 |