WvStreams
|
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 }