// 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, 675 Mass Ave, Cambridge, MA 02139, USA.
#include "<T>.<C>.AVLMap.h"
constants & inlines for maintaining balance & thread status in tree nodes
static inline int bf(<T><C>AVLNode* t)
return t->stat & AVLBALANCEMASK;
static inline void set_bf(<T><C>AVLNode* t, int b)
t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
static inline int rthread(<T><C>AVLNode* t)
return t->stat & RTHREADBIT;
static inline void set_rthread(<T><C>AVLNode* t, int b)
static inline int lthread(<T><C>AVLNode* t)
return t->stat & LTHREADBIT;
static inline void set_lthread(<T><C>AVLNode* t, int b)
<T><C>AVLNode* <T><C>AVLMap::leftmost()
if (t != 0) while (t->lt != 0) t = t->lt;
<T><C>AVLNode* <T><C>AVLMap::rightmost()
if (t != 0) while (t->rt != 0) t = t->rt;
<T><C>AVLNode* <T><C>AVLMap::succ(<T><C>AVLNode* t)
<T><C>AVLNode* r = t->rt;
if (!rthread(t)) while (!lthread(r)) r = r->lt;
<T><C>AVLNode* <T><C>AVLMap::pred(<T><C>AVLNode* t)
<T><C>AVLNode* l = t->lt;
if (!lthread(t)) while (!rthread(l)) l = l->rt;
Pix <T><C>AVLMap::seek(<T&> key)
int cmp = <T>CMP(key, t->item);
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 <T>* _target_item; // add/del_item target
static <T><C>AVLNode* _found_node; // returned added/deleted node
static int _already_found; // for deletion subcases
void <T><C>AVLMap:: _add(<T><C>AVLNode*& t)
int cmp = <T>CMP(*_target_item, t->item);
_found_node = new <T><C>AVLNode(*_target_item, def);
set_lthread(_found_node, 1);
set_rthread(_found_node, 1);
<T><C>AVLNode* l = t->lt;
if (bf(l) == AVLLEFTHEAVY)
set_lthread(t, rthread(l));
<T><C>AVLNode* r = l->rt;
set_rthread(l, lthread(r));
set_lthread(t, rthread(r));
if (bf(r) == AVLLEFTHEAVY)
set_bf(t, AVLRIGHTHEAVY);
if (bf(r) == AVLRIGHTHEAVY)
_found_node = new <T><C>AVLNode(*_target_item, def);
set_lthread(_found_node, 1);
set_rthread(_found_node, 1);
set_bf(t, AVLRIGHTHEAVY);
<T><C>AVLNode* r = t->rt;
if (bf(r) == AVLRIGHTHEAVY)
set_rthread(t, lthread(r));
<T><C>AVLNode* l = r->lt;
set_lthread(r, rthread(l));
set_rthread(t, lthread(l));
if (bf(l) == AVLRIGHTHEAVY)
if (bf(l) == AVLLEFTHEAVY)
set_bf(r, AVLRIGHTHEAVY);
<C>& <T><C>AVLMap::operator [] (<T&> item)
root = new <T><C>AVLNode(item, def);
return _found_node->cont;
void <T><C>AVLMap::_del(<T><C>AVLNode* par, <T><C>AVLNode*& t)
comp = <T>CMP(*_target_item, t->item);
if (lthread(t) && rthread(t))
<T><C>AVLNode* s = succ(t);
if (s != 0 && lthread(s))
<T><C>AVLNode* p = pred(t);
if (p != 0 && rthread(p))
else // replace item & find someone deletable
<T><C>AVLNode* p = pred(t);
comp = -1; // fall through below to left
set_bf(t, AVLRIGHTHEAVY);
<T><C>AVLNode* r = t->rt;
set_rthread(t, lthread(r));
set_bf(t, AVLRIGHTHEAVY);
set_rthread(t, lthread(r));
<T><C>AVLNode* l = r->lt;
set_lthread(r, rthread(l));
set_rthread(t, lthread(l));
if (bf(l) == AVLRIGHTHEAVY)
if (bf(l) == AVLLEFTHEAVY)
set_bf(r, AVLRIGHTHEAVY);
<T><C>AVLNode* l = t->lt;
set_lthread(t, rthread(l));
set_bf(l, AVLRIGHTHEAVY);
set_lthread(t, rthread(l));
<T><C>AVLNode* r = l->rt;
set_rthread(l, lthread(r));
set_lthread(t, rthread(r));
if (bf(r) == AVLLEFTHEAVY)
set_bf(t, AVLRIGHTHEAVY);
if (bf(r) == AVLRIGHTHEAVY)
void <T><C>AVLMap::del(<T&> item)
void <T><C>AVLMap::_kill(<T><C>AVLNode* t)
if (!lthread(t)) _kill(t->lt);
if (!rthread(t)) _kill(t->rt);
<T><C>AVLMap::<T><C>AVLMap(<T><C>AVLMap& b) :<T><C>Map(b.def)
for (Pix i = b.first(); i != 0; b.next(i))
(*this)[b.key(i)] = b.contents(i);
<T><C>AVLNode* trail = leftmost();
<T><C>AVLNode* t = succ(trail);
v &= <T>CMP(trail->item, t->item) < 0;
if (!v) error("invariant failure");