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 | */ |
---|
21 | |
---|
22 | #include "xmldef.h" |
---|
23 | |
---|
24 | #ifdef XML_UNICODE_WCHAR_T |
---|
25 | #ifndef XML_UNICODE |
---|
26 | #define XML_UNICODE |
---|
27 | #endif |
---|
28 | #endif |
---|
29 | |
---|
30 | #include "hashtable.h" |
---|
31 | |
---|
32 | #define INIT_SIZE 64 |
---|
33 | |
---|
34 | static |
---|
35 | int keyeq(KEY s1, KEY s2) |
---|
36 | { |
---|
37 | for (; *s1 == *s2; s1++, s2++) |
---|
38 | if (*s1 == 0) |
---|
39 | return 1; |
---|
40 | return 0; |
---|
41 | } |
---|
42 | |
---|
43 | static |
---|
44 | unsigned long hash(KEY s) |
---|
45 | { |
---|
46 | unsigned long h = 0; |
---|
47 | while (*s) |
---|
48 | h = (h << 5) + h + (unsigned char)*s++; |
---|
49 | return h; |
---|
50 | } |
---|
51 | |
---|
52 | NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize) |
---|
53 | { |
---|
54 | size_t i; |
---|
55 | if (table->size == 0) { |
---|
56 | if (!createSize) |
---|
57 | return 0; |
---|
58 | table->v = calloc(INIT_SIZE, sizeof(NAMED *)); |
---|
59 | if (!table->v) |
---|
60 | return 0; |
---|
61 | table->size = INIT_SIZE; |
---|
62 | table->usedLim = INIT_SIZE / 2; |
---|
63 | i = hash(name) & (table->size - 1); |
---|
64 | } |
---|
65 | else { |
---|
66 | unsigned long h = hash(name); |
---|
67 | for (i = h & (table->size - 1); |
---|
68 | table->v[i]; |
---|
69 | i == 0 ? i = table->size - 1 : --i) { |
---|
70 | if (keyeq(name, table->v[i]->name)) |
---|
71 | return table->v[i]; |
---|
72 | } |
---|
73 | if (!createSize) |
---|
74 | return 0; |
---|
75 | if (table->used == table->usedLim) { |
---|
76 | /* check for overflow */ |
---|
77 | size_t newSize = table->size * 2; |
---|
78 | NAMED **newV = calloc(newSize, sizeof(NAMED *)); |
---|
79 | if (!newV) |
---|
80 | return 0; |
---|
81 | for (i = 0; i < table->size; i++) |
---|
82 | if (table->v[i]) { |
---|
83 | size_t j; |
---|
84 | for (j = hash(table->v[i]->name) & (newSize - 1); |
---|
85 | newV[j]; |
---|
86 | j == 0 ? j = newSize - 1 : --j) |
---|
87 | ; |
---|
88 | newV[j] = table->v[i]; |
---|
89 | } |
---|
90 | g_free(table->v); |
---|
91 | table->v = newV; |
---|
92 | table->size = newSize; |
---|
93 | table->usedLim = newSize/2; |
---|
94 | for (i = h & (table->size - 1); |
---|
95 | table->v[i]; |
---|
96 | i == 0 ? i = table->size - 1 : --i) |
---|
97 | ; |
---|
98 | } |
---|
99 | } |
---|
100 | table->v[i] = calloc(1, createSize); |
---|
101 | if (!table->v[i]) |
---|
102 | return 0; |
---|
103 | table->v[i]->name = name; |
---|
104 | (table->used)++; |
---|
105 | return table->v[i]; |
---|
106 | } |
---|
107 | |
---|
108 | void hashTableDestroy(HASH_TABLE *table) |
---|
109 | { |
---|
110 | size_t i; |
---|
111 | for (i = 0; i < table->size; i++) { |
---|
112 | NAMED *p = table->v[i]; |
---|
113 | if (p) |
---|
114 | g_free(p); |
---|
115 | } |
---|
116 | g_free(table->v); |
---|
117 | } |
---|
118 | |
---|
119 | void hashTableInit(HASH_TABLE *p) |
---|
120 | { |
---|
121 | p->size = 0; |
---|
122 | p->usedLim = 0; |
---|
123 | p->used = 0; |
---|
124 | p->v = 0; |
---|
125 | } |
---|
126 | |
---|
127 | void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table) |
---|
128 | { |
---|
129 | iter->p = table->v; |
---|
130 | iter->end = iter->p + table->size; |
---|
131 | } |
---|
132 | |
---|
133 | NAMED *hashTableIterNext(HASH_TABLE_ITER *iter) |
---|
134 | { |
---|
135 | while (iter->p != iter->end) { |
---|
136 | NAMED *tem = *(iter->p)++; |
---|
137 | if (tem) |
---|
138 | return tem; |
---|
139 | } |
---|
140 | return 0; |
---|
141 | } |
---|
142 | |
---|