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