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