1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
/*
* The contents of this file are subject to the Mozilla Public License
* Version 1.0 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
* License for the specific language governing rights and limitations
* under the License.
*
* The Initial Developer of this code is David Baum.
* Portions created by David Baum are Copyright (C) 1998 David Baum.
* All Rights Reserved.
*/
#include <string.h>
#include "PHashTable.h"
PHashable::~PHashable() {
}
bool PHashable::MatchKey(const char *key) {
return strcmp(key, fKey)==0 ? true : false;
}
P_HashTable::P_HashTable(int size) {
fBuckets = new PListSS<PHashable>[size];
fSize = size;
}
P_HashTable::~P_HashTable() {
delete [] fBuckets;
}
PHashable* P_HashTable::_Find(const char *key) {
PHashable *ptr;
int hash = Hash(key);
for(ptr=fBuckets[hash].GetHead(); ptr; ptr=ptr->GetNext()) {
if (ptr->MatchKey(key)) return ptr;
}
return nil;
}
void P_HashTable::Add(PHashable *item) {
int hash = Hash(item->GetKey());
fBuckets[hash].InsertHead(item);
}
bool P_HashTable::Remove(PHashable *item) {
int hash = Hash(item->GetKey());
return fBuckets[hash].Remove(item);
}
void P_HashTable::DeleteAll() {
int i;
PHashable *item;
for(i=0; i<fSize; i++) {
while((item = fBuckets[i].RemoveHead()) != nil)
delete item;
}
}
int P_HashTable::Hash(const char *string)
{
register unsigned long h=0,g;
register const char *p;
for(p=string; *p != 0; p++)
{
h = (h <<4) + (*p);
if ((g= h & 0xf0000000) != 0)
{
h = h ^ (g >> 24);
h = h ^ g;
}
}
return (int)(h % fSize);
}
|
