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