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