25
|
1 |
/* |
|
2 |
The contents of this file are subject to the Mozilla Public License |
|
3 |
Version 1.1 (the "License"); you may not use this file except in |
|
4 |
csompliance with the License. You may obtain a copy of the License at |
|
5 |
http://www.mozilla.org/MPL/ |
|
6 |
|
|
7 |
Software distributed under the License is distributed on an "AS IS" |
|
8 |
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the |
|
9 |
License for the specific language governing rights and limitations |
|
10 |
under the License. |
|
11 |
|
|
12 |
The Original Code is expat. |
|
13 |
|
|
14 |
The Initial Developer of the Original Code is James Clark. |
|
15 |
Portions created by James Clark are Copyright (C) 1998, 1999 |
|
16 |
James Clark. All Rights Reserved. |
|
17 |
|
|
18 |
Contributor(s): |
|
19 |
|
|
20 |
Alternatively, the contents of this file may be used under the terms |
|
21 |
of the GNU General Public License (the "GPL"), in which case the |
|
22 |
provisions of the GPL are applicable instead of those above. If you |
|
23 |
wish to allow use of your version of this file only under the terms of |
|
24 |
the GPL and not to allow others to use your version of this file under |
|
25 |
the MPL, indicate your decision by deleting the provisions above and |
|
26 |
replace them with the notice and other provisions required by the |
|
27 |
GPL. If you do not delete the provisions above, a recipient may use |
|
28 |
your version of this file under either the MPL or the GPL. |
|
29 |
*/ |
|
30 |
|
|
31 |
#include "xmldef.h" |
|
32 |
|
|
33 |
#ifdef XML_UNICODE_WCHAR_T |
|
34 |
#ifndef XML_UNICODE |
|
35 |
#define XML_UNICODE |
|
36 |
#endif |
|
37 |
#endif |
|
38 |
|
|
39 |
#include "hashtable.h" |
|
40 |
|
|
41 |
#define INIT_SIZE 64 |
|
42 |
|
|
43 |
static |
|
44 |
int keyeq(KEY s1, KEY s2) |
|
45 |
{ |
|
46 |
for (; *s1 == *s2; s1++, s2++) |
|
47 |
if (*s1 == 0) |
|
48 |
return 1; |
|
49 |
return 0; |
|
50 |
} |
|
51 |
|
|
52 |
static |
|
53 |
unsigned long hash(KEY s) |
|
54 |
{ |
|
55 |
unsigned long h = 0; |
|
56 |
while (*s) |
|
57 |
h = (h << 5) + h + (unsigned char)*s++; |
|
58 |
return h; |
|
59 |
} |
|
60 |
|
|
61 |
NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize) |
|
62 |
{ |
|
63 |
size_t i; |
|
64 |
if (table->size == 0) { |
|
65 |
if (!createSize) |
|
66 |
return 0; |
|
67 |
table->v = calloc(INIT_SIZE, sizeof(NAMED *)); |
|
68 |
if (!table->v) |
|
69 |
return 0; |
|
70 |
table->size = INIT_SIZE; |
|
71 |
table->usedLim = INIT_SIZE / 2; |
|
72 |
i = hash(name) & (table->size - 1); |
|
73 |
} |
|
74 |
else { |
|
75 |
unsigned long h = hash(name); |
|
76 |
for (i = h & (table->size - 1); |
|
77 |
table->v[i]; |
|
78 |
i == 0 ? i = table->size - 1 : --i) { |
|
79 |
if (keyeq(name, table->v[i]->name)) |
|
80 |
return table->v[i]; |
|
81 |
} |
|
82 |
if (!createSize) |
|
83 |
return 0; |
|
84 |
if (table->used == table->usedLim) { |
|
85 |
/* check for overflow */ |
|
86 |
size_t newSize = table->size * 2; |
|
87 |
NAMED **newV = calloc(newSize, sizeof(NAMED *)); |
|
88 |
if (!newV) |
|
89 |
return 0; |
|
90 |
for (i = 0; i < table->size; i++) |
|
91 |
if (table->v[i]) { |
|
92 |
size_t j; |
|
93 |
for (j = hash(table->v[i]->name) & (newSize - 1); |
|
94 |
newV[j]; |
|
95 |
j == 0 ? j = newSize - 1 : --j) |
|
96 |
; |
|
97 |
newV[j] = table->v[i]; |
|
98 |
} |
|
99 |
free(table->v); |
|
100 |
table->v = newV; |
|
101 |
table->size = newSize; |
|
102 |
table->usedLim = newSize/2; |
|
103 |
for (i = h & (table->size - 1); |
|
104 |
table->v[i]; |
|
105 |
i == 0 ? i = table->size - 1 : --i) |
|
106 |
; |
|
107 |
} |
|
108 |
} |
|
109 |
table->v[i] = calloc(1, createSize); |
|
110 |
if (!table->v[i]) |
|
111 |
return 0; |
|
112 |
table->v[i]->name = name; |
|
113 |
(table->used)++; |
|
114 |
return table->v[i]; |
|
115 |
} |
|
116 |
|
|
117 |
void hashTableDestroy(HASH_TABLE *table) |
|
118 |
{ |
|
119 |
size_t i; |
|
120 |
for (i = 0; i < table->size; i++) { |
|
121 |
NAMED *p = table->v[i]; |
|
122 |
if (p) |
|
123 |
free(p); |
|
124 |
} |
|
125 |
free(table->v); |
|
126 |
} |
|
127 |
|
|
128 |
void hashTableInit(HASH_TABLE *p) |
|
129 |
{ |
|
130 |
p->size = 0; |
|
131 |
p->usedLim = 0; |
|
132 |
p->used = 0; |
|
133 |
p->v = 0; |
|
134 |
} |
|
135 |
|
|
136 |
void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table) |
|
137 |
{ |
|
138 |
iter->p = table->v; |
|
139 |
iter->end = iter->p + table->size; |
|
140 |
} |
|
141 |
|
|
142 |
NAMED *hashTableIterNext(HASH_TABLE_ITER *iter) |
|
143 |
{ |
|
144 |
while (iter->p != iter->end) { |
|
145 |
NAMED *tem = *(iter->p)++; |
|
146 |
if (tem) |
|
147 |
return tem; |
|
148 |
} |
|
149 |
return 0; |
|
150 |
} |
|
151 |
|