WvStreams
wvhashtable.cc
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Small, efficient, type-safe hash table class.  See wvhashtable.h.
00006  */
00007 #include "wvhashtable.h"
00008 #include "wvstring.h"
00009 
00010 // we do not accept the _numslots value directly.  Instead, we find the
00011 // next number of slots which is >= _numslots and one less then a power
00012 // of 2.  This usually results in a fairly good hash table size.
00013 WvHashTableBase::WvHashTableBase(unsigned _numslots)
00014 {
00015     int slides = 1;
00016     while ((_numslots >>= 1) != 0)
00017         slides++;
00018     numslots = (1 << slides) - 1;
00019 }
00020 
00021 
00022 // never returns NULL.  If the object is not found, the 'previous' link
00023 // is the last one in the list.
00024 WvLink *WvHashTableBase::prevlink(WvListBase *wvslots, const void *data,
00025                               unsigned hash) const
00026 {
00027     WvListBase::IterBase i(wvslots[hash % numslots]);
00028     WvLink *prev;
00029     
00030     i.rewind();
00031     for (prev = i.cur(); prev->next; prev = i.next())
00032     {
00033         if (compare(data, prev->next->data))
00034             break;
00035     }
00036     return prev;
00037 }
00038 
00039 
00040 void *WvHashTableBase::genfind(WvListBase *wvslots, const void *data,
00041                               unsigned hash) const
00042 {
00043     WvLink *prev = prevlink(wvslots, data, hash);
00044     if (prev->next)
00045         return prev->next->data;
00046     else
00047         return NULL;
00048 }
00049 
00050 
00051 size_t WvHashTableBase::count() const
00052 {
00053     size_t count = 0;
00054     
00055     for (unsigned i = 0; i < numslots; i++)
00056         count += wvslots[i].count();
00057     return count;
00058 }
00059 
00060 
00061 bool WvHashTableBase::isempty() const
00062 {
00063     for (unsigned i = 0; i < numslots; i++)
00064         if (! wvslots[i].isempty())
00065             return false;
00066     return true;
00067 }
00068 
00069 
00070 WvLink *WvHashTableBase::IterBase::next()
00071 {
00072     // In the best case, we can just look at the next item in the bucket.
00073     link = link->next;
00074     if (link)
00075         return link;
00076 
00077     // Keep local copies of information, so we don't have to poke into the
00078     // data structure.
00079     WvLink *_link = NULL;       // we would have returned if link were non-NULL
00080     WvListBase *begin = tbl->wvslots;
00081     WvListBase *cur = begin + tblindex;
00082     WvListBase *end = begin + tbl->numslots - 1;
00083 
00084     // We'll go from the current bucket to the last bucket, in hopes that
00085     // one of them will contain something.
00086     while (cur < end)
00087     {
00088         ++cur;
00089         _link = cur->head.next;
00090         if (_link)
00091             break;
00092     }
00093 
00094     tblindex = cur - begin;     // Compute the tblindex.
00095     link = _link;               // Save the link
00096     return link;
00097 }