| /* |
| The contents of this file are subject to the Mozilla Public License |
| Version 1.1 (the "License"); you may not use this file except in |
| csompliance 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 Original Code is expat. |
| |
| The Initial Developer of the Original Code is James Clark. |
| Portions created by James Clark are Copyright (C) 1998, 1999 |
| James Clark. All Rights Reserved. |
| |
| Contributor(s): |
| |
| Alternatively, the contents of this file may be used under the terms |
| of the GNU General Public License (the "GPL"), in which case the |
| provisions of the GPL are applicable instead of those above. If you |
| wish to allow use of your version of this file only under the terms of |
| the GPL and not to allow others to use your version of this file under |
| the MPL, indicate your decision by deleting the provisions above and |
| replace them with the notice and other provisions required by the |
| GPL. If you do not delete the provisions above, a recipient may use |
| your version of this file under either the MPL or the GPL. |
| */ |
| |
| #include "xmldef.h" |
| |
| #ifdef XML_UNICODE_WCHAR_T |
| #ifndef XML_UNICODE |
| #define XML_UNICODE |
| #endif |
| #endif |
| |
| #include "hashtable.h" |
| |
| #define INIT_SIZE 64 |
| |
| static |
| int keyeq(KEY s1, KEY s2) |
| { |
| for (; *s1 == *s2; s1++, s2++) |
| if (*s1 == 0) |
| return 1; |
| return 0; |
| } |
| |
| static |
| unsigned long hash(KEY s) |
| { |
| unsigned long h = 0; |
| while (*s) |
| h = (h << 5) + h + (unsigned char)*s++; |
| return h; |
| } |
| |
| NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize) |
| { |
| size_t i; |
| if (table->size == 0) { |
| if (!createSize) |
| return 0; |
| table->v = calloc(INIT_SIZE, sizeof(NAMED *)); |
| if (!table->v) |
| return 0; |
| table->size = INIT_SIZE; |
| table->usedLim = INIT_SIZE / 2; |
| i = hash(name) & (table->size - 1); |
| } |
| else { |
| unsigned long h = hash(name); |
| for (i = h & (table->size - 1); |
| table->v[i]; |
| i == 0 ? i = table->size - 1 : --i) { |
| if (keyeq(name, table->v[i]->name)) |
| return table->v[i]; |
| } |
| if (!createSize) |
| return 0; |
| if (table->used == table->usedLim) { |
| /* check for overflow */ |
| size_t newSize = table->size * 2; |
| NAMED **newV = calloc(newSize, sizeof(NAMED *)); |
| if (!newV) |
| return 0; |
| for (i = 0; i < table->size; i++) |
| if (table->v[i]) { |
| size_t j; |
| for (j = hash(table->v[i]->name) & (newSize - 1); |
| newV[j]; |
| j == 0 ? j = newSize - 1 : --j) |
| ; |
| newV[j] = table->v[i]; |
| } |
| free(table->v); |
| table->v = newV; |
| table->size = newSize; |
| table->usedLim = newSize/2; |
| for (i = h & (table->size - 1); |
| table->v[i]; |
| i == 0 ? i = table->size - 1 : --i) |
| ; |
| } |
| } |
| table->v[i] = calloc(1, createSize); |
| if (!table->v[i]) |
| return 0; |
| table->v[i]->name = name; |
| (table->used)++; |
| return table->v[i]; |
| } |
| |
| void hashTableDestroy(HASH_TABLE *table) |
| { |
| size_t i; |
| for (i = 0; i < table->size; i++) { |
| NAMED *p = table->v[i]; |
| if (p) |
| free(p); |
| } |
| free(table->v); |
| } |
| |
| void hashTableInit(HASH_TABLE *p) |
| { |
| p->size = 0; |
| p->usedLim = 0; |
| p->used = 0; |
| p->v = 0; |
| } |
| |
| void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table) |
| { |
| iter->p = table->v; |
| iter->end = iter->p + table->size; |
| } |
| |
| NAMED *hashTableIterNext(HASH_TABLE_ITER *iter) |
| { |
| while (iter->p != iter->end) { |
| NAMED *tem = *(iter->p)++; |
| if (tem) |
| return tem; |
| } |
| return 0; |
| } |
| |