Category : OS/2 Files
Archive   : GPPDEV8F.ZIP
Filename : CHSET.CCP

// This may look like C code, but it is really -*- C++ -*-
/*
Copyright (C) 1988 Free Software Foundation
written by Doug Lea ([email protected])

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.
*/

#ifdef __GNUG__
#pragma implementation
#endif
#include ".CHSet.h"

// A CHSet is implemented as an array (tab) of buckets, each of which
// contains a pointer to a list of CHNodes. Each node contains a
// pointer to the next node in the list, and a pointer to the .
// The end of the list is marked by a next node pointer which is odd
// when considered as an integer (least significant bit = 1). The
// assumption is that CHNodes will all begin on even addresses. If
// the odd pointer is right-shifted by one bit, it becomes the index
// within the tab array of the next bucket (that is, bucket i has
// next bucket pointer 2*(i+1)+1).

// The bucket pointers are initialized by the constructor and
// used to support the next(Pix&) method.

// This implementation is not portable to machines with different
// pointer and integer sizes, or on which CHNodes might be aligned on
// odd byte boundaries, but allows the same pointer to be used for
// chaining within a bucket and to the next bucket.


static inline int goodCHptr(CHNode* t)
{
return ((((unsigned)t) & 1) == 0);
}

static inline CHNode* index_to_CHptr(int i)
{
return (CHNode*)((i << 1) + 1);
}

static inline int CHptr_to_index(CHNode* t)
{
return ( ((unsigned) t) >> 1);
}

CHSet::CHSet(unsigned int sz)
{
tab = (CHNode**)(new CHNodePtr[size = sz]);
for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1);
count = 0;
}

CHSet::CHSet(CHSet& a)
{
tab = (CHNode**)(new CHNodePtr[size = a.size]);
for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1);
count = 0;
for (Pix p = a.first(); p; a.next(p)) add(a(p));
}


Pix CHSet::seek( key)
{
unsigned int h = HASH(key) % size;

for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl)
if (EQ(key, t->hd))
return Pix(t);

return 0;
}


Pix CHSet::add( item)
{
unsigned int h = HASH(item) % size;

for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl)
if (EQ(item, t->hd))
return Pix(t);

++count;
t = new CHNode(item, tab[h]);
tab[h] = t;
return Pix(t);
}


void CHSet::del( key)
{
unsigned int h = HASH(key) % size;

CHNode* t = tab[h];
CHNode* trail = t;
while (goodCHptr(t))
{
if (EQ(key, t->hd))
{
if (trail == t)
tab[h] = t->tl;
else
trail->tl = t->tl;
delete t;
--count;
return;
}
trail = t;
t = t->tl;
}
}


void CHSet::clear()
{
for (unsigned int i = 0; i < size; ++i)
{
CHNode* p = tab[i];
tab[i] = index_to_CHptr(i+1);
while (goodCHptr(p))
{
CHNode* nxt = p->tl;
delete(p);
p = nxt;
}
}
count = 0;
}

Pix CHSet::first()
{
for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]);
return 0;
}

void CHSet::next(Pix& p)
{
if (p == 0) return;
CHNode* t = ((CHNode*)p)->tl;
if (goodCHptr(t))
p = Pix(t);
else
{
for (unsigned int i = CHptr_to_index(t); i < size; ++i)
{
if (goodCHptr(tab[i]))
{
p = Pix(tab[i]);
return;
}
}
p = 0;
}
}

int CHSet::operator == (CHSet& b)
{
if (count != b.count)
return 0;
else
{
CHNode* p;
for (unsigned int i = 0; i < size; ++i)
for (p = tab[i]; goodCHptr(p); p = p->tl)
if (b.seek(p->hd) == 0)
return 0;
for (i = 0; i < b.size; ++i)
for (p = b.tab[i]; goodCHptr(p); p = p->tl)
if (seek(p->hd) == 0)
return 0;
return 1;
}
}

int CHSet::operator <= (CHSet& b)
{
if (count > b.count)
return 0;
else
{
for (unsigned int i = 0; i < size; ++i)
for (CHNode* p = tab[i]; goodCHptr(p); p = p->tl)
if (b.seek(p->hd) == 0)
return 0;
return 1;
}
}

void CHSet::operator |= (CHSet& b)
{
if (&b == this || b.count == 0)
return;
for (unsigned int i = 0; i < b.size; ++i)
for (CHNode* p = b.tab[i]; goodCHptr(p); p = p->tl)
add(p->hd);
}

void CHSet::operator &= (CHSet& b)
{
for (unsigned int i = 0; i < size; ++i)
{
CHNode* t = tab[i];
CHNode* trail = t;
while (goodCHptr(t))
{
CHNode* nxt = t->tl;
if (b.seek(t->hd) == 0)
{
if (trail == tab[i])
trail = tab[i] = nxt;
else
trail->tl = nxt;
delete t;
--count;
}
else
trail = t;
t = nxt;
}
}
}

void CHSet::operator -= (CHSet& b)
{
for (unsigned int i = 0; i < size; ++i)
{
CHNode* t = tab[i];
CHNode* trail = t;
while (goodCHptr(t))
{
CHNode* nxt = t->tl;
if (b.seek(t->hd) != 0)
{
if (trail == tab[i])
trail = tab[i] = nxt;
else
trail->tl = nxt;
delete t;
--count;
}
else
trail = t;
t = nxt;
}
}
}

int CHSet::OK()
{
int v = tab != 0;
int n = 0;
for (unsigned int i = 0; i < size; ++i)
{
for (CHNode* p = tab[i]; goodCHptr(p); p = p->tl) ++n;
v &= CHptr_to_index(p) == i + 1;
}
v &= count == n;
if (!v) error("invariant failure");
return v;
}