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.46; author tv; state dead; branches; next 1.1; 1.1 date 96.03.09.00.00.59; author phil; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 96.03.09.00.00.59; 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 ".AVLSet.h" #include /* 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(AVLNode* t) { return t->stat & AVLBALANCEMASK; } static inline void set_bf(AVLNode* t, int b) { t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK); } static inline int rthread(AVLNode* t) { return t->stat & RTHREADBIT; } static inline void set_rthread(AVLNode* t, int b) { if (b) t->stat |= RTHREADBIT; else t->stat &= ~RTHREADBIT; } static inline int lthread(AVLNode* t) { return t->stat & LTHREADBIT; } static inline void set_lthread(AVLNode* t, int b) { if (b) t->stat |= LTHREADBIT; else t->stat &= ~LTHREADBIT; } /* traversal primitives */ AVLNode* AVLSet::leftmost() { AVLNode* t = root; if (t != 0) while (t->lt != 0) t = t->lt; return t; } AVLNode* AVLSet::rightmost() { AVLNode* t = root; if (t != 0) while (t->rt != 0) t = t->rt; return t; } AVLNode* AVLSet::succ(AVLNode* t) { AVLNode* r = t->rt; if (!rthread(t)) while (!lthread(r)) r = r->lt; return r; } AVLNode* AVLSet::pred(AVLNode* t) { AVLNode* l = t->lt; if (!lthread(t)) while (!rthread(l)) l = l->rt; return l; } Pix AVLSet::seek( key) { AVLNode* 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; } } /* 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 AVLNode* _found_node; // returned added/deleted node static int _already_found; // for deletion subcases static AVLNode** _hold_nodes; // used for rebuilding trees static int _max_hold_index; // # elements-1 in _hold_nodes void AVLSet:: _add(AVLNode*& 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 AVLNode(*_target_item); 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; } else _add(t->lt); 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: { AVLNode* l = t->lt; if (bf(l) == AVLLEFTHEAVY) { 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 { AVLNode* r = l->rt; 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 AVLNode(*_target_item); 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; } 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: { AVLNode* r = t->rt; if (bf(r) == AVLRIGHTHEAVY) { 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 { AVLNode* l = r->lt; 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; } } } } } } Pix AVLSet::add( item) { if (root == 0) { ++count; root = new AVLNode(item); set_rthread(root, 1); set_lthread(root, 1); return Pix(root); } else { _target_item = &item; _need_rebalancing = 0; _add(root); return Pix(_found_node); } } void AVLSet::_del(AVLNode* par, AVLNode*& 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; return; } else if (lthread(t)) { _found_node = t; AVLNode* s = succ(t); if (s != 0 && lthread(s)) s->lt = t->lt; t = t->rt; _need_rebalancing = 1; return; } else if (rthread(t)) { _found_node = t; AVLNode* p = pred(t); if (p != 0 && rthread(p)) p->rt = t->rt; t = t->lt; _need_rebalancing = 1; return; } else // replace item & find someone deletable { AVLNode* p = pred(t); t->item = p->item; _already_found = 1; comp = -1; // fall through below to left } } if (comp < 0) { if (lthread(t)) return; _del(t, t->lt); 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: { AVLNode* r = t->rt; switch (bf(r)) { case AVLBALANCED: 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: 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: { AVLNode* l = r->lt; 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: { AVLNode* l = t->lt; switch (bf(l)) { case AVLBALANCED: 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: 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: { AVLNode* r = l->rt; 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 AVLSet::del( item) { if (root == 0) return; _need_rebalancing = 0; _already_found = 0; _found_node = 0; _target_item = &item; _del(root, root); if (_found_node) { delete(_found_node); if (--count == 0) root = 0; } } // build an ordered array of pointers to tree nodes back into a tree // we know that at least one element exists static AVLNode* _do_treeify(int lo, int hi, int& h) { int lh, rh; int mid = (lo + hi) / 2; AVLNode* t = _hold_nodes[mid]; if (lo > mid - 1) { set_lthread(t, 1); if (mid == 0) t->lt = 0; else t->lt = _hold_nodes[mid-1]; lh = 0; } else { set_lthread(t, 0); t->lt = _do_treeify(lo, mid-1, lh); } if (hi < mid + 1) { set_rthread(t, 1); if (mid == _max_hold_index) t->rt = 0; else t->rt = _hold_nodes[mid+1]; rh = 0; } else { set_rthread(t, 0); t->rt = _do_treeify(mid+1, hi, rh); } if (lh == rh) { set_bf(t, AVLBALANCED); h = lh + 1; } else if (lh == rh - 1) { set_bf(t, AVLRIGHTHEAVY); h = rh + 1; } else if (rh == lh - 1) { set_bf(t, AVLLEFTHEAVY); h = lh + 1; } else // can't happen abort(); return t; } static AVLNode* _treeify(int n) { AVLNode* t; if (n == 0) t = 0; else { int b; _max_hold_index = n-1; t = _do_treeify(0, _max_hold_index, b); } delete _hold_nodes; return t; } void AVLSet::_kill(AVLNode* t) { if (t != 0) { if (!lthread(t)) _kill(t->lt); if (!rthread(t)) _kill(t->rt); delete t; } } AVLSet::AVLSet(AVLSet& b) { if ((count = b.count) == 0) { root = 0; } else { _hold_nodes = new AVLNodePtr [count]; AVLNode* t = b.leftmost(); int i = 0; while (t != 0) { _hold_nodes[i++] = new AVLNode(t->item); t = b.succ(t); } root = _treeify(count); } } int AVLSet::operator == (AVLSet& y) { if (count != y.count) return 0; else { AVLNode* t = leftmost(); AVLNode* u = y.leftmost(); for (;;) { if (t == 0) return 1; else if (!(EQ(t->item, u->item))) return 0; else { t = succ(t); u = y.succ(u); } } } } int AVLSet::operator <= (AVLSet& y) { if (count > y.count) return 0; else { AVLNode* t = leftmost(); AVLNode* u = y.leftmost(); for (;;) { if (t == 0) return 1; else if (u == 0) return 0; int cmp = CMP(t->item, u->item); if (cmp == 0) { t = succ(t); u = y.succ(u); } else if (cmp < 0) return 0; else u = y.succ(u); } } } void AVLSet::operator |=(AVLSet& y) { AVLNode* t = leftmost(); AVLNode* u = y.leftmost(); int rsize = count + y.count; _hold_nodes = new AVLNodePtr [rsize]; int k = 0; for (;;) { if (t == 0) { while (u != 0) { _hold_nodes[k++] = new AVLNode(u->item); u = y.succ(u); } break; } else if (u == 0) { while (t != 0) { _hold_nodes[k++] = t; t = succ(t); } break; } int cmp = CMP(t->item, u->item); if (cmp == 0) { _hold_nodes[k++] = t; t = succ(t); u = y.succ(u); } else if (cmp < 0) { _hold_nodes[k++] = t; t = succ(t); } else { _hold_nodes[k++] = new AVLNode(u->item); u = y.succ(u); } } root = _treeify(k); count = k; } void AVLSet::operator &= (AVLSet& y) { AVLNode* t = leftmost(); AVLNode* u = y.leftmost(); int rsize = (count < y.count)? count : y.count; _hold_nodes = new AVLNodePtr [rsize]; int k = 0; for (;;) { if (t == 0) break; if (u == 0) { while (t != 0) { AVLNode* tmp = succ(t); delete t; t = tmp; } break; } int cmp = CMP(t->item, u->item); if (cmp == 0) { _hold_nodes[k++] = t; t = succ(t); u = y.succ(u); } else if (cmp < 0) { AVLNode* tmp = succ(t); delete t; t = tmp; } else u = y.succ(u); } root = _treeify(k); count = k; } void AVLSet::operator -=(AVLSet& y) { AVLNode* t = leftmost(); AVLNode* u = y.leftmost(); int rsize = count; _hold_nodes = new AVLNodePtr [rsize]; int k = 0; for (;;) { if (t == 0) break; else if (u == 0) { while (t != 0) { _hold_nodes[k++] = t; t = succ(t); } break; } int cmp = CMP(t->item, u->item); if (cmp == 0) { AVLNode* tmp = succ(t); delete t; t = tmp; u = y.succ(u); } else if (cmp < 0) { _hold_nodes[k++] = t; t = succ(t); } else u = y.succ(u); } root = _treeify(k); count = k; } int AVLSet::owns(Pix i) { if (i == 0) return 0; for (AVLNode* t = leftmost(); t != 0; t = succ(t)) if (Pix(t) == i) return 1; return 0; } int AVLSet::OK() { int v = 1; if (root == 0) v = count == 0; else { int n = 1; AVLNode* trail = leftmost(); AVLNode* t = succ(trail); while (t != 0) { ++n; v &= CMP(trail->item, t->item) < 0; 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 @@