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

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

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
#include ".VOHSet.h"


/* codes for status fields */
#define EMPTYCELL 0
#define VALIDCELL 1
#define DELETEDCELL 2


VOHSet::VOHSet(int sz)
{
// The size of the hash table is always the smallest power of 2 >= the size
// indicated by the user. This allows several optimizations, including
// the use of actual double hashing and elimination of the mod instruction.

size = 1;
while (size < sz) size <<= 1;
tab = new [size];
status = new char[size];
for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
count = cnt = 0;
}

VOHSet::VOHSet(VOHSet& a)
{
tab = new [size = a.size];
status = new char[size];
for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
count = cnt = 0;
for (Pix p = a.first(); p; a.next(p)) add(a(p));
}

Pix VOHSet::seek( key)
{
// Uses ordered double hashing to perform a search of the table.
// This greatly speeds up the average-case time for an unsuccessful search.

unsigned hashval = HASH(key);

// We can avoid the mod operation since size is a power of 2.
unsigned h = hashval & (size - 1);

// The increment must be odd, since all odd numbers are relatively
// prime to a power of 2!!
unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));

// There is always at least 1 empty cell, so this loop is guaranteed to halt!
while (status[h] != EMPTYCELL)
{
int cmp = CMP (key, tab[h]);
if (cmp == 0)
{
if (status[h] == VALIDCELL)
return Pix(&tab[h]);
else
return 0;
}
else if (cmp > 0)
return 0;
else
h = ((h + inc) & (size - 1));
}
return 0;
}

// This adds an item if it doesn't already exist. By performing the initial
// comparison we assure that the table always contains at least 1 empty
// spot. This speeds up later searching by a constant factor.
// The insertion algorithm uses ordered double hashing. See Standish's
// 1980 ``Data Structure's Techniques'' book for details.

Pix VOHSet::add( x)
{
if (size <= cnt+1)
resize();

unsigned hashval = HASH(x);
unsigned h = hashval & (size - 1);

if (status[h] != VALIDCELL) // save some work if possible
{
if (status[h] == EMPTYCELL)
cnt++;
count++;
tab[h] = x;
status[h] = VALIDCELL;
return Pix(&tab[h]);
}
int cmp = CMP(x, tab[h]);
if (cmp == 0)
return Pix(&tab[h]);

item = x;
Pix mypix = 0;
unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));

for (;;)
{
if (cmp < 0)
{
temp = tab[h];
tab[h] = item;
item = temp;
if (mypix == 0) mypix = Pix(&tab[h]);
inc = ((((HASH(item) / size) << 1) + 1) & (size - 1));
h = ((h + inc) & (size - 1));
if (status[h] != EMPTYCELL) cmp = CMP(item, tab[h]);
}
else
h = ((h + inc) & (size - 1));
if (status[h] != VALIDCELL)
{
if (status[h] == EMPTYCELL)
cnt++;
count++;
tab[h] = item;
status[h] = VALIDCELL;
return (mypix == 0)? Pix(&tab[h]) : mypix;
}
}
}


void VOHSet::del( key)
{
// This performs a deletion by marking the item's status field.
// Note that we only decrease the count, *not* the cnt, since this
// would cause trouble for subsequent steps in the algorithm. See
// Reingold and Hanson's ``Data Structure's'' book for a justification
// of this approach.

unsigned hashval = HASH(key);
unsigned h = hashval & (size - 1);
unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));

while (status[h] != EMPTYCELL)
{
int cmp = CMP(key, tab[h]);
if (cmp > 0)
h = ((h + inc) & (size - 1));
else if (status[h] == VALIDCELL && cmp == 0)
{
status[h] = DELETEDCELL;
count--;
return;
}
else
return;
}
}

void VOHSet::clear()
{
for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
count = cnt = 0;
}

void VOHSet::resize(int newsize)
{
if (newsize <= count)
newsize = count;
int s = 1;
while (s <= newsize) s <<= 1;
newsize = s;

* oldtab = tab;
char* oldstatus = status;
int oldsize = size;
tab = new [size = newsize];
status = new char[size];
for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
count = cnt = 0;

for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]);
delete [] oldtab;
delete oldstatus;
}

Pix VOHSet::first()
{
for (int pos = 0; pos < size; ++pos)
if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
return 0;
}

void VOHSet::next(Pix& i)
{
if (i == 0) return;
int pos = ((unsigned)i - (unsigned)tab) / sizeof() + 1;
for (; pos < size; ++pos)
if (status[pos] == VALIDCELL)
{
i = Pix(&tab[pos]);
return;
}
i = 0;
}


int VOHSet:: operator == (VOHSet& b)
{
if (count != b.count)
return 0;
else
{
for (int i = 0; i < size; ++i)
if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
return 0;
for (i = 0; i < b.size; ++i)
if (b.status[i] == VALIDCELL && seek(b.tab[i]) == 0)
return 0;
return 1;
}
}

int VOHSet:: operator != (VOHSet& b)
{
return !(*this == b);
}

int VOHSet::operator <= (VOHSet& b)
{
if (count > b.count)
return 0;
else
{
for (int i = 0; i < size; ++i)
if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
return 0;
return 1;
}
}

void VOHSet::operator |= (VOHSet& b)
{
if (&b == this || b.count == 0)
return;
for (int i = 0; i < b.size; ++i)
if (b.status[i] == VALIDCELL) add(b.tab[i]);
}

void VOHSet::operator &= (VOHSet& b)
{
if (&b == this || count == 0)
return;
for (int i = 0; i < size; ++i)
{
if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
{
status[i] = DELETEDCELL;
--count;
}
}
}

void VOHSet::operator -= (VOHSet& b)
{
for (int i = 0; i < size; ++i)
{
if (status[i] == VALIDCELL && b.seek(tab[i]) != 0)
{
status[i] = DELETEDCELL;
--count;
}
}
}

int VOHSet::OK()
{
int v = tab != 0;
v &= status != 0;
int n = 0;
for (int i = 0; i < size; ++i)
{
if (status[i] == VALIDCELL) ++n;
else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL)
v = 0;
}
v &= n == count;
if (!v) error("invariant failure");
return v;
}