utils/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
  61 bool WvHashTableBase::isempty() const
  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 }