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.
13 WvHashTableBase::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.
24 WvLink *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 
40 void *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 
51 size_t WvHashTableBase::count() const
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 
70 WvLink *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 }
WvListBase::IterBase
Definition: wvlinklist.h:73
WvListBase
Definition: wvlinklist.h:21
WvHashTableBase::count
size_t count() const
Returns the number of elements in the hash table.
Definition: wvhashtable.cc:51
WvHashTableBase::isempty
bool isempty() const
Returns true if the hash table is empty.
Definition: wvhashtable.cc:61