WvStreams
wvhashtable.cc
1/*
2 * Worldvisions Weaver Software:
3 * Copyright (C) 1997-2002 Net Integration Technologies, Inc.
4 *
5 * Small, efficient, type-safe hash table class. See wvhashtable.h.
6 */
7#include "wvhashtable.h"
8#include "wvstring.h"
9
10// we do not accept the _numslots value directly. Instead, we find the
11// next number of slots which is >= _numslots and one less then a power
12// of 2. This usually results in a fairly good hash table size.
13WvHashTableBase::WvHashTableBase(unsigned _numslots)
14{
15 int slides = 1;
16 while ((_numslots >>= 1) != 0)
17 slides++;
18 numslots = (1 << slides) - 1;
19}
20
21
22// never returns NULL. If the object is not found, the 'previous' link
23// is the last one in the list.
24WvLink *WvHashTableBase::prevlink(WvListBase *wvslots, const void *data,
25 unsigned hash) const
26{
27 WvListBase::IterBase i(wvslots[hash % numslots]);
28 WvLink *prev;
29
30 i.rewind();
31 for (prev = i.cur(); prev->next; prev = i.next())
32 {
33 if (compare(data, prev->next->data))
34 break;
35 }
36 return prev;
37}
38
39
40void *WvHashTableBase::genfind(WvListBase *wvslots, const void *data,
41 unsigned hash) const
42{
43 WvLink *prev = prevlink(wvslots, data, hash);
44 if (prev->next)
45 return prev->next->data;
46 else
47 return NULL;
48}
49
50
52{
53 size_t count = 0;
54
55 for (unsigned i = 0; i < numslots; i++)
56 count += wvslots[i].count();
57 return count;
58}
59
60
62{
63 for (unsigned i = 0; i < numslots; i++)
64 if (! wvslots[i].isempty())
65 return false;
66 return true;
67}
68
69
70WvLink *WvHashTableBase::IterBase::next()
71{
72 // In the best case, we can just look at the next item in the bucket.
73 link = link->next;
74 if (link)
75 return link;
76
77 // Keep local copies of information, so we don't have to poke into the
78 // data structure.
79 WvLink *_link = NULL; // we would have returned if link were non-NULL
80 WvListBase *begin = tbl->wvslots;
81 WvListBase *cur = begin + tblindex;
82 WvListBase *end = begin + tbl->numslots - 1;
83
84 // We'll go from the current bucket to the last bucket, in hopes that
85 // one of them will contain something.
86 while (cur < end)
87 {
88 ++cur;
89 _link = cur->head.next;
90 if (_link)
91 break;
92 }
93
94 tblindex = cur - begin; // Compute the tblindex.
95 link = _link; // Save the link
96 return link;
97}
size_t count() const
Returns the number of elements in the hash table.
bool isempty() const
Returns true if the hash table is empty.