// 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>.VHMap.h"
/* codes for status fields */
<T><C>VHMap::<T><C>VHMap(<C&> dflt, unsigned int sz)
tab = new <T>[size = sz];
for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
<T><C>VHMap::<T><C>VHMap(<T><C>VHMap& a) : <T><C>Map(a.def)
tab = new <T>[size = a.size];
for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
for (Pix p = a.first(); p; a.next(p)) (*this)[a.key(p)] = a.contents(p);
* hashing method: double hash based on high bits of hash fct,
* followed by linear probe. Can't do too much better if table
* sizes not constrained to be prime.
static inline unsigned int doublehashinc(unsigned int h, unsigned int s)
unsigned int dh = ((h / s) % s);
Pix <T><C>VHMap::seek(<T&> key)
unsigned int hashval = <T>HASH(key);
unsigned int h = hashval % size;
for (unsigned int i = 0; i <= size; ++i)
if (status[h] == EMPTYCELL)
else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
h = (h + doublehashinc(hashval, size)) % size;
<C>& <T><C>VHMap::operator [](<T&> item)
if (HASHTABLE_TOO_CROWDED(count, size))
unsigned int bestspot = size;
unsigned int hashval = <T>HASH(item);
unsigned int h = hashval % size;
for (unsigned int i = 0; i <= size; ++i)
if (status[h] == EMPTYCELL)
if (bestspot >= size) bestspot = h;
status[bestspot] = VALIDCELL;
else if (status[h] == DELETEDCELL)
if (bestspot >= size) bestspot = h;
else if (<T>EQ(tab[h],item))
h = (h + doublehashinc(hashval, size)) % size;
status[bestspot] = VALIDCELL;
void <T><C>VHMap::del(<T&> key)
unsigned int hashval = <T>HASH(key);
unsigned int h = hashval % size;
for (unsigned int i = 0; i <= size; ++i)
if (status[h] == EMPTYCELL)
else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
h = (h + doublehashinc(hashval, size)) % size;
void <T><C>VHMap::clear()
for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
void <T><C>VHMap::resize(unsigned int newsize)
newsize = DEFAULT_INITIAL_CAPACITY;
while (HASHTABLE_TOO_CROWDED(count, newsize)) newsize <<= 1;
char* oldstatus = status;
unsigned int oldsize = size;
tab = new <T>[size = newsize];
for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
for (i = 0; i < oldsize; ++i)
if (oldstatus[i] == VALIDCELL)
(*this)[oldtab[i]] = oldcont[i];
for (unsigned int pos = 0; pos < size; ++pos)
if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
void <T><C>VHMap::next(Pix& i)
unsigned int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1;
for (; pos < size; ++pos)
if (status[pos] == VALIDCELL)
for (unsigned int i = 0; i < size; ++i)
if (status[i] == VALIDCELL) ++n;
else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL)
if (!v) error("invariant failure");