00001
00002
00003
00004
00005
00006
00007 #include "wvhashtable.h"
00008 #include "wvstring.h"
00009
00010
00011
00012
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
00023
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
00073 link = link->next;
00074 if (link)
00075 return link;
00076
00077
00078
00079 WvLink *_link = NULL;
00080 WvListBase *begin = tbl->wvslots;
00081 WvListBase *cur = begin + tblindex;
00082 WvListBase *end = begin + tbl->numslots - 1;
00083
00084
00085
00086 while (cur < end)
00087 {
00088 ++cur;
00089 _link = cur->head.next;
00090 if (_link)
00091 break;
00092 }
00093
00094 tblindex = cur - begin;
00095 link = _link;
00096 return link;
00097 }