00001
00002
00003
00004
00005
00006
00007 #include "wvhashtable.h"
00008 #include "wvstring.h"
00009
00010
00011
00012 unsigned WvHash(const char *s)
00013 {
00014 unsigned hash = 0, slide, andval;
00015 if (!s) return 0;
00016
00017 slide = sizeof(hash)*8 - 5;
00018 andval = 0x1F << slide;
00019
00020 while (*s)
00021 hash = (hash<<5) ^ (*(s++) & 0x1F) ^ ((hash & andval) >> slide);
00022
00023 return hash;
00024 }
00025
00026 unsigned WvHash(const WvString &s)
00027 {
00028 return !s ? 0 : WvHash((const char *)s);
00029 }
00030
00031
00032 unsigned WvHash(const int &i)
00033 {
00034 return i;
00035 }
00036
00037
00038
00039
00040
00041 WvHashTableBase::WvHashTableBase(unsigned _numslots)
00042 {
00043 int slides = 1;
00044 while ((_numslots >>= 1) != 0)
00045 slides++;
00046 numslots = (1 << slides) - 1;
00047 }
00048
00049
00050
00051
00052 WvLink *WvHashTableBase::prevlink(WvListBase *slots, const void *data,
00053 unsigned hash, Comparator *comp)
00054 {
00055 WvListBase::IterBase i(slots[hash % numslots]);
00056 WvLink *prev;
00057
00058 i.rewind();
00059 for (prev = i.cur(); prev->next; prev = i.next())
00060 {
00061 if (comp(data, prev->next->data))
00062 break;
00063 }
00064 return prev;
00065 }
00066
00067
00068 void *WvHashTableBase::genfind(WvListBase *slots, const void *data,
00069 unsigned hash, Comparator *comp)
00070 {
00071 WvLink *prev = prevlink(slots, data, hash, comp);
00072 if (prev->next)
00073 return prev->next->data;
00074 else
00075 return NULL;
00076 }
00077
00078
00079 size_t WvHashTableBase::count() const
00080 {
00081 size_t count = 0;
00082
00083 for (unsigned i = 0; i < numslots; i++)
00084 count += slots[i].count();
00085 return count;
00086 }
00087
00088
00089 WvLink *WvHashTableBase::IterBase::next()
00090 {
00091 link = link->next;
00092 while (!link && tblindex < tbl->numslots - 1)
00093 link = tbl->slots[++tblindex].head.next;
00094 return link;
00095 }