head 1.2; access; symbols perseant-exfatfs-base-20250801:1.2 perseant-exfatfs-base-20240630:1.2 cjep_sun2x:1.2.0.44 cjep_sun2x-base:1.2 cjep_staticlib_x-base1:1.2 cjep_staticlib_x:1.2.0.42 cjep_staticlib_x-base:1.2 phil-wifi-20200421:1.2 phil-wifi-20200411:1.2 phil-wifi-20200406:1.2 pgoyette-compat-merge-20190127:1.2 pgoyette-compat-20190127:1.2 pgoyette-compat-20190118:1.2 pgoyette-compat-1226:1.2 pgoyette-compat-1126:1.2 pgoyette-compat-1020:1.2 pgoyette-compat-0930:1.2 pgoyette-compat-0906:1.2 pgoyette-compat-0728:1.2 pgoyette-compat-0625:1.2 pgoyette-compat-0521:1.2 pgoyette-compat-0502:1.2 pgoyette-compat-0422:1.2 pgoyette-compat-0415:1.2 pgoyette-compat-0407:1.2 pgoyette-compat-0330:1.2 pgoyette-compat-0322:1.2 pgoyette-compat-0315:1.2 pgoyette-compat:1.2.0.40 pgoyette-compat-base:1.2 perseant-stdc-iso10646:1.2.0.38 perseant-stdc-iso10646-base:1.2 prg-localcount2-base3:1.2 prg-localcount2-base2:1.2 prg-localcount2-base1:1.2 prg-localcount2:1.2.0.36 prg-localcount2-base:1.2 pgoyette-localcount-20170426:1.2 bouyer-socketcan-base1:1.2 pgoyette-localcount-20170320:1.2 bouyer-socketcan:1.2.0.34 bouyer-socketcan-base:1.2 pgoyette-localcount-20170107:1.2 pgoyette-localcount-20161104:1.2 localcount-20160914:1.2 pgoyette-localcount-20160806:1.2 pgoyette-localcount-20160726:1.2 pgoyette-localcount:1.2.0.32 pgoyette-localcount-base:1.2 netbsd-5-2-3-RELEASE:1.2 netbsd-5-1-5-RELEASE:1.2 yamt-pagecache-base9:1.2 yamt-pagecache-tag8:1.2 tls-earlyentropy:1.2.0.28 tls-earlyentropy-base:1.2 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.2 riastradh-drm2-base3:1.2 netbsd-5-2-2-RELEASE:1.2 netbsd-5-1-4-RELEASE:1.2 netbsd-5-2-1-RELEASE:1.2 netbsd-5-1-3-RELEASE:1.2 agc-symver:1.2.0.30 agc-symver-base:1.2 tls-maxphys-base:1.2 yamt-pagecache-base8:1.2 netbsd-5-2:1.2.0.26 yamt-pagecache-base7:1.2 netbsd-5-2-RELEASE:1.2 netbsd-5-2-RC1:1.2 yamt-pagecache-base6:1.2 yamt-pagecache-base5:1.2 yamt-pagecache-base4:1.2 netbsd-5-1-2-RELEASE:1.2 netbsd-5-1-1-RELEASE:1.2 yamt-pagecache-base3:1.2 yamt-pagecache-base2:1.2 yamt-pagecache:1.2.0.24 yamt-pagecache-base:1.2 bouyer-quota2-nbase:1.2 bouyer-quota2:1.2.0.22 bouyer-quota2-base:1.2 matt-nb5-pq3:1.2.0.20 matt-nb5-pq3-base:1.2 netbsd-5-1:1.2.0.18 netbsd-5-1-RELEASE:1.2 netbsd-5-1-RC4:1.2 netbsd-5-1-RC3:1.2 netbsd-5-1-RC2:1.2 netbsd-5-1-RC1:1.2 netbsd-5-0-2-RELEASE:1.2 netbsd-5-0-1-RELEASE:1.2 jym-xensuspend-nbase:1.2 netbsd-5-0:1.2.0.16 netbsd-5-0-RELEASE:1.2 netbsd-5-0-RC4:1.2 netbsd-5-0-RC3:1.2 netbsd-5-0-RC2:1.2 jym-xensuspend:1.2.0.14 jym-xensuspend-base:1.2 netbsd-5-0-RC1:1.2 netbsd-5:1.2.0.12 netbsd-5-base:1.2 mjf-devfs2:1.2.0.10 mjf-devfs2-base:1.2 yamt-pf42-base4:1.2 yamt-pf42-base3:1.2 hpcarm-cleanup-nbase:1.2 yamt-pf42-base2:1.2 yamt-pf42:1.2.0.8 yamt-pf42-base:1.2 keiichi-mipv6:1.2.0.6 keiichi-mipv6-base:1.2 cube-autoconf:1.2.0.4 cube-autoconf-base:1.2 hpcarm-cleanup:1.2.0.2 hpcarm-cleanup-base:1.2 netbsd-1-3-PATCH003:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE2:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE1:1.1.1.1 netbsd-1-3-PATCH003-CANDIDATE0:1.1.1.1 netbsd-1-3-PATCH002:1.1.1.1 netbsd-1-3-PATCH001:1.1.1.1 netbsd-1-3-RELEASE:1.1.1.1 netbsd-1-3-BETA:1.1.1.1 netbsd-1-3:1.1.1.1.0.2 netbsd-1-3-base:1.1.1.1 netbsd-1-2-PATCH001:1.1.1.1 libg++-2-7-2:1.1.1.1 netbsd-1-2-RELEASE:1.1.1.1 netbsd-1-2-BETA:1.1.1.1 netbsd-1-2-base:1.1.1.1 netbsd-1-2:1.1.1.1.0.4 libg++-2-7-1:1.1.1.1 FSF:1.1.1; locks; strict; comment @# @; 1.2 date 98.12.12.23.50.56; author tv; state dead; branches; next 1.1; 1.1 date 96.03.09.00.01.02; author phil; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 96.03.09.00.01.02; author phil; state Exp; branches; next ; desc @@ 1.2 log @GC old gcc 2.7.2.2. @ text @// This may look like C code, but it is really -*- C++ -*- /* Copyright (C) 1988 Free Software Foundation written by Doug Lea (dl@@rocky.oswego.edu) This file is part of the GNU C++ Library. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifdef __GNUG__ #pragma implementation #endif #include #include "..RAVLMap.h" /* constants & inlines for maintaining balance & thread status in tree nodes */ #define AVLBALANCEMASK 3 #define AVLBALANCED 0 #define AVLLEFTHEAVY 1 #define AVLRIGHTHEAVY 2 #define LTHREADBIT 4 #define RTHREADBIT 8 static inline int bf(RAVLNode* t) { return t->stat & AVLBALANCEMASK; } static inline void set_bf(RAVLNode* t, int b) { t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK); } static inline int rthread(RAVLNode* t) { return t->stat & RTHREADBIT; } static inline void set_rthread(RAVLNode* t, int b) { if (b) t->stat |= RTHREADBIT; else t->stat &= ~RTHREADBIT; } static inline int lthread(RAVLNode* t) { return t->stat & LTHREADBIT; } static inline void set_lthread(RAVLNode* t, int b) { if (b) t->stat |= LTHREADBIT; else t->stat &= ~LTHREADBIT; } /* traversal primitives */ RAVLNode* RAVLMap::leftmost() { RAVLNode* t = root; if (t != 0) while (t->lt != 0) t = t->lt; return t; } RAVLNode* RAVLMap::rightmost() { RAVLNode* t = root; if (t != 0) while (t->rt != 0) t = t->rt; return t; } RAVLNode* RAVLMap::succ(RAVLNode* t) { RAVLNode* r = t->rt; if (!rthread(t)) while (!lthread(r)) r = r->lt; return r; } RAVLNode* RAVLMap::pred(RAVLNode* t) { RAVLNode* l = t->lt; if (!lthread(t)) while (!rthread(l)) l = l->rt; return l; } Pix RAVLMap::seek( key) { RAVLNode* t = root; if (t == 0) return 0; for (;;) { int cmp = CMP(key, t->item); if (cmp == 0) return Pix(t); else if (cmp < 0) { if (lthread(t)) return 0; else t = t->lt; } else if (rthread(t)) return 0; else t = t->rt; } } int RAVLMap::rankof( key) { int r; RAVLNode* t = root; if (t == 0) return 0; for (r=t->rank; t != 0; r+=t->rank) { int cmp = CMP(key, t->item); if (cmp == 0) return r; else if (cmp < 0) { if (lthread(t)) return 0; else { r -= t->rank; t = t->lt; } } else if (rthread(t)) return 0; else { t = t->rt; } } return 0; } Pix RAVLMap::ranktoPix(int i) { int r; RAVLNode* t = root; if ((i<1)||(i>count)) return 0; for (r=t->rank; r!=i; r+=t->rank) { if (r>i) { r -= t->rank; t = t->lt; } else t = t->rt; } return Pix(t); } /* The combination of threads and AVL bits make adding & deleting interesting, but very awkward. We use the following statics to avoid passing them around recursively */ static int _need_rebalancing; // to send back balance info from rec. calls static * _target_item; // add/del_item target static RAVLNode* _found_node; // returned added/deleted node static int _already_found; // for deletion subcases static int _rank_changed; // for rank computation void RAVLMap:: _add(RAVLNode*& t) { int cmp = CMP(*_target_item, t->item); if (cmp == 0) { _found_node = t; return; } else if (cmp < 0) { if (lthread(t)) { ++count; _found_node = new RAVLNode(*_target_item, def); set_lthread(_found_node, 1); set_rthread(_found_node, 1); _found_node->lt = t->lt; _found_node->rt = t; t->lt = _found_node; set_lthread(t, 0); _need_rebalancing = 1; _rank_changed = 1; } else _add(t->lt); if (_rank_changed) ++t->rank; if (_need_rebalancing) { switch(bf(t)) { case AVLRIGHTHEAVY: set_bf(t, AVLBALANCED); _need_rebalancing = 0; return; case AVLBALANCED: set_bf(t, AVLLEFTHEAVY); return; case AVLLEFTHEAVY: { RAVLNode* l = t->lt; if (bf(l) == AVLLEFTHEAVY) { t->rank -= l->rank; if (rthread(l)) t->lt = l; else t->lt = l->rt; set_lthread(t, rthread(l)); l->rt = t; set_rthread(l, 0); set_bf(t, AVLBALANCED); set_bf(l, AVLBALANCED); t = l; _need_rebalancing = 0; } else { RAVLNode* r = l->rt; r->rank += l->rank; t->rank -= r->rank; set_rthread(l, lthread(r)); if (lthread(r)) l->rt = r; else l->rt = r->lt; r->lt = l; set_lthread(r, 0); set_lthread(t, rthread(r)); if (rthread(r)) t->lt = r; else t->lt = r->rt; r->rt = t; set_rthread(r, 0); if (bf(r) == AVLLEFTHEAVY) set_bf(t, AVLRIGHTHEAVY); else set_bf(t, AVLBALANCED); if (bf(r) == AVLRIGHTHEAVY) set_bf(l, AVLLEFTHEAVY); else set_bf(l, AVLBALANCED); set_bf(r, AVLBALANCED); t = r; _need_rebalancing = 0; return; } } } } } else { if (rthread(t)) { ++count; _found_node = new RAVLNode(*_target_item, def); set_rthread(t, 0); set_lthread(_found_node, 1); set_rthread(_found_node, 1); _found_node->lt = t; _found_node->rt = t->rt; t->rt = _found_node; _need_rebalancing = 1; _rank_changed = 1; } else _add(t->rt); if (_need_rebalancing) { switch(bf(t)) { case AVLLEFTHEAVY: set_bf(t, AVLBALANCED); _need_rebalancing = 0; return; case AVLBALANCED: set_bf(t, AVLRIGHTHEAVY); return; case AVLRIGHTHEAVY: { RAVLNode* r = t->rt; if (bf(r) == AVLRIGHTHEAVY) { r->rank += t->rank; if (lthread(r)) t->rt = r; else t->rt = r->lt; set_rthread(t, lthread(r)); r->lt = t; set_lthread(r, 0); set_bf(t, AVLBALANCED); set_bf(r, AVLBALANCED); t = r; _need_rebalancing = 0; } else { RAVLNode* l = r->lt; r->rank -= l->rank; l->rank += t->rank; set_lthread(r, rthread(l)); if (rthread(l)) r->lt = l; else r->lt = l->rt; l->rt = r; set_rthread(l, 0); set_rthread(t, lthread(l)); if (lthread(l)) t->rt = l; else t->rt = l->lt; l->lt = t; set_lthread(l, 0); if (bf(l) == AVLRIGHTHEAVY) set_bf(t, AVLLEFTHEAVY); else set_bf(t, AVLBALANCED); if (bf(l) == AVLLEFTHEAVY) set_bf(r, AVLRIGHTHEAVY); else set_bf(r, AVLBALANCED); set_bf(l, AVLBALANCED); t = l; _need_rebalancing = 0; return; } } } } } } & RAVLMap::operator [] ( item) { if (root == 0) { ++count; root = new RAVLNode(item, def); set_rthread(root, 1); set_lthread(root, 1); return root->cont; } else { _target_item = &item; _need_rebalancing = 0; _rank_changed = 0; _add(root); return _found_node->cont; } } void RAVLMap::_del(RAVLNode* par, RAVLNode*& t) { int comp; if (_already_found) { if (rthread(t)) comp = 0; else comp = 1; } else comp = CMP(*_target_item, t->item); if (comp == 0) { if (lthread(t) && rthread(t)) { _found_node = t; if (t == par->lt) { set_lthread(par, 1); par->lt = t->lt; } else { set_rthread(par, 1); par->rt = t->rt; } _need_rebalancing = 1; _rank_changed = 1; return; } else if (lthread(t)) { _found_node = t; RAVLNode* s = succ(t); if (s != 0 && lthread(s)) s->lt = t->lt; t = t->rt; _need_rebalancing = 1; _rank_changed = 1; return; } else if (rthread(t)) { _found_node = t; RAVLNode* p = pred(t); if (p != 0 && rthread(p)) p->rt = t->rt; t = t->lt; _need_rebalancing = 1; _rank_changed = 1; return; } else // replace item & find someone deletable { RAVLNode* p = pred(t); t->item = p->item; t->cont = p->cont; _already_found = 1; comp = -1; // fall through below to left } } if (comp < 0) { if (lthread(t)) return; _del(t, t->lt); if (_rank_changed) --t->rank; if (!_need_rebalancing) return; switch (bf(t)) { case AVLLEFTHEAVY: set_bf(t, AVLBALANCED); return; case AVLBALANCED: set_bf(t, AVLRIGHTHEAVY); _need_rebalancing = 0; return; case AVLRIGHTHEAVY: { RAVLNode* r = t->rt; switch (bf(r)) { case AVLBALANCED: r->rank += t->rank; if (lthread(r)) t->rt = r; else t->rt = r->lt; set_rthread(t, lthread(r)); r->lt = t; set_lthread(r, 0); set_bf(t, AVLRIGHTHEAVY); set_bf(r, AVLLEFTHEAVY); _need_rebalancing = 0; t = r; return; case AVLRIGHTHEAVY: r->rank += t->rank; if (lthread(r)) t->rt = r; else t->rt = r->lt; set_rthread(t, lthread(r)); r->lt = t; set_lthread(r, 0); set_bf(t, AVLBALANCED); set_bf(r, AVLBALANCED); t = r; return; case AVLLEFTHEAVY: { RAVLNode* l = r->lt; r->rank -= l->rank; l->rank += t->rank; set_lthread(r, rthread(l)); if (rthread(l)) r->lt = l; else r->lt = l->rt; l->rt = r; set_rthread(l, 0); set_rthread(t, lthread(l)); if (lthread(l)) t->rt = l; else t->rt = l->lt; l->lt = t; set_lthread(l, 0); if (bf(l) == AVLRIGHTHEAVY) set_bf(t, AVLLEFTHEAVY); else set_bf(t, AVLBALANCED); if (bf(l) == AVLLEFTHEAVY) set_bf(r, AVLRIGHTHEAVY); else set_bf(r, AVLBALANCED); set_bf(l, AVLBALANCED); t = l; return; } } } } } else { if (rthread(t)) return; _del(t, t->rt); if (!_need_rebalancing) return; switch (bf(t)) { case AVLRIGHTHEAVY: set_bf(t, AVLBALANCED); return; case AVLBALANCED: set_bf(t, AVLLEFTHEAVY); _need_rebalancing = 0; return; case AVLLEFTHEAVY: { RAVLNode* l = t->lt; switch (bf(l)) { case AVLBALANCED: t->rank -= l->rank; if (rthread(l)) t->lt = l; else t->lt = l->rt; set_lthread(t, rthread(l)); l->rt = t; set_rthread(l, 0); set_bf(t, AVLLEFTHEAVY); set_bf(l, AVLRIGHTHEAVY); _need_rebalancing = 0; t = l; return; case AVLLEFTHEAVY: t->rank -= l->rank; if (rthread(l)) t->lt = l; else t->lt = l->rt; set_lthread(t, rthread(l)); l->rt = t; set_rthread(l, 0); set_bf(t, AVLBALANCED); set_bf(l, AVLBALANCED); t = l; return; case AVLRIGHTHEAVY: { RAVLNode* r = l->rt; r->rank += l->rank; t->rank -= r->rank; set_rthread(l, lthread(r)); if (lthread(r)) l->rt = r; else l->rt = r->lt; r->lt = l; set_lthread(r, 0); set_lthread(t, rthread(r)); if (rthread(r)) t->lt = r; else t->lt = r->rt; r->rt = t; set_rthread(r, 0); if (bf(r) == AVLLEFTHEAVY) set_bf(t, AVLRIGHTHEAVY); else set_bf(t, AVLBALANCED); if (bf(r) == AVLRIGHTHEAVY) set_bf(l, AVLLEFTHEAVY); else set_bf(l, AVLBALANCED); set_bf(r, AVLBALANCED); t = r; return; } } } } } } void RAVLMap::del( item) { if (root == 0) return; _need_rebalancing = 0; _already_found = 0; _found_node = 0; _rank_changed = 0; _target_item = &item; _del(root, root); if (_found_node) { delete(_found_node); if (--count == 0) root = 0; } } void RAVLMap::_kill(RAVLNode* t) { if (t != 0) { if (!lthread(t)) _kill(t->lt); if (!rthread(t)) _kill(t->rt); delete t; } } RAVLMap::RAVLMap(RAVLMap& b) :Map(b.def) { root = 0; count = 0; for (Pix i = b.first(); i != 0; b.next(i)) (*this)[b.key(i)] = b.contents(i); } int RAVLMap::OK() { int v = 1; if (root == 0) v = count == 0; else { int n = 1; RAVLNode* trail = leftmost(); v &= rankof(trail->item) == n; RAVLNode* t = succ(trail); while (t != 0) { ++n; v &= CMP(trail->item, t->item) < 0; v &= rankof(t->item) == n; trail = t; t = succ(t); } v &= n == count; } if (!v) error("invariant failure"); return v; } @ 1.1 log @Initial revision @ text @@ 1.1.1.1 log @Import of libg++-2.7.1. @ text @@