// This may look like C code, but it is really -*- C++ -*-
Copyright (C) 1991 Free Software Foundation
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.
* Bags implemented via William Pugh SkipList algorithms.
* CACM, June 1990, p 668-676.
MLCG* <T>SkipBag::gen = 0;
int <T>SkipBaginit::count = 0;
static int countbits(long bits)
<T>SkipBag::<T>SkipBag(long size)
header(new <T>SkipBagNode (countbits(size)+1)),
max_levels (countbits(size)+1),
random_bits(gen->asLong()),
randoms_left(BITS_IN_RANDOM / 2)
<T>SkipBagNodePtr *buffer_start = header->forward;
<T>SkipBagNodePtr *trav = &header->forward[max_levels];
while (trav > buffer_start)
*--trav = (<T>SkipBagNodePtr) header;
<T>SkipBag::<T>SkipBag(<T>SkipBag& b)
header (new <T>SkipBagNode (b.max_levels)),
max_levels (b.max_levels),
random_bits (gen->asLong()),
randoms_left (BITS_IN_RANDOM / 2)
<T>SkipBagNodePtr *buffer_start = header->forward;
<T>SkipBagNodePtr *trav = &header->forward[max_levels];
while (trav > buffer_start)
*--trav = (<T>SkipBagNodePtr)header;
for (<T>SkipBagNodePtr t = b.leftmost(); t; t = b.succ(t))
Pix <T>SkipBag::add (<T&> item)
<T>SkipBagNodePtr *update = new <T>SkipBagNodePtr[max_levels+1];
<T>SkipBagNodePtr curr = (<T>SkipBagNodePtr) this->header;
while ((temp = curr->forward[l])!=header &&
<T>CMP(temp->item, item) < 0)
if ((l = random_level ()) > level)
update[l] = (<T>SkipBagNodePtr)header;
temp = new <T>RealSkipBagNode (item, l);
<T>SkipBagNodePtr *temp_forward = temp->forward;
<T>SkipBagNodePtr *curr_forward = update[l]->forward;
temp_forward[l] = curr_forward[l];
void <T>SkipBag::del(<T&> key)
<T>SkipBagNodePtr *update = new <T>SkipBagNodePtr[max_levels+1];
<T>SkipBagNodePtr curr = (<T>SkipBagNodePtr)header;
while ((temp = curr->forward[l])!=header
&& <T>CMP(temp->item,key) < 0)
if (<T>CMP(temp->item,key)==0)
<T>SkipBagNodePtr *temp_forward = temp->forward;
l <= curr_level && (curr = update[l])->forward[l] == temp;
curr->forward[l] = temp_forward[l];
<T>SkipBagNodePtr *forward = header->forward;
while (forward[curr_level]==header && curr_level > 0)
<T>SkipBagNodePtr <T>SkipBag::rightmost()
<T>SkipBagNode* curr = header;
while ((temp = curr->forward[l])!=header)
return temp==header ? 0 : temp;
<T>SkipBagNodePtr <T>SkipBag::pred(<T>SkipBagNodePtr t)
<T>SkipBagNodePtr temp, curr = (<T>SkipBagNodePtr) header;
while ((temp = curr->forward[l])!=t)
return curr == header ? 0 : curr;
<T>SkipBagNode *p = this->header->forward[0];
<T>SkipBagNodePtr q = p->forward[0];
<T>SkipBagNodePtr *buffer_start = header->forward;
<T>SkipBagNodePtr *trav = &header->forward[level+1];
while (trav > buffer_start)
*--trav = (<T>SkipBagNodePtr)header;
Pix <T>SkipBag::seek(<T&> key, Pix i)
<T>SkipBagNode *curr = header;
curr = (<T>SkipBagNode *)i;
while ((temp = curr->forward[l])!=header &&
<T>CMP(temp->item, key) < 0)
if (<T>CMP(temp->item, key) != 0)
int <T>SkipBag::nof(<T&> item)
<T>SkipBagNodePtr t = (<T>SkipBagNodePtr)(seek(item));
} while (t != 0 && <T>EQ(item, t->item));
void <T>SkipBag::remove(<T&> key)
* random function for probabilistic balancing
* Hardwired for p = .25. Not too flexible,
* but fast. Changing this would require a constructor
* that would accept a different value for p, etc.
* Perhaps someone else would like to implement this?
int <T>SkipBag::random_level (void)
random_bits = gen->asLong();
randoms_left = BITS_IN_RANDOM / 2;
return rlevel > max_levels ? max_levels : rlevel;
<T>SkipBagNodePtr trail = leftmost();
if (trail) t = succ(trail);
v &= <T>CMP(trail->item, t->item) < 0;
if (!v) error("invariant failure");
<T>SkipBaginit::<T>SkipBaginit()
<T>SkipBag::gen = new MLCG(time(0));
<T>SkipBaginit::~<T>SkipBaginit()