1 /*
2 * TurboXSL XML+XSLT processing library
3 * Dictionary for hashed names -> pointers conversion
4 *
5 *
6 * (c) Egor Voznessenski, voznyak@mail.ru
7 *
8 * $Id$
9 *
10 **/
11
12 #include "xmldict.h"
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include "logger.h"
19
20 typedef struct _dict_entry {
21 XMLSTRING name;
22 const void *data;
23 unsigned next;
24 } XMLDICTENTRY;
25
26 struct _dict {
27 XMLDICTENTRY *entries;
28 unsigned allocated;
29 unsigned used;
30 unsigned hash[128];
31 };
32
33 /*
34 * sdbm hash function
35 */
hash_function(unsigned char * str)36 unsigned long hash_function(unsigned char *str)
37 {
38 unsigned long hash = 0;
39 int c;
40
41 while ((c = *str++))
42 hash = c + (hash << 6) + (hash << 16) - hash;
43
44 return hash;
45 }
46
bucket_number(XMLSTRING str)47 unsigned int bucket_number(XMLSTRING str)
48 {
49 if (str->hash == 0) str->hash = hash_function(str->s);
50 return (unsigned int)(str->hash % 127);
51 }
52
dict_new(unsigned size)53 XMLDICT *dict_new(unsigned size)
54 {
55 XMLDICT *dict;
56 dict = malloc(sizeof(XMLDICT));
57 if(!size) size = 100;
58
59 if(dict) {
60 memset(dict,0,sizeof(XMLDICT));
61 dict->allocated = size;
62 dict->entries = malloc(size * sizeof(XMLDICTENTRY));
63 if(!dict->entries) {
64 free(dict);
65 dict = 0;
66 }
67 }
68 if(!dict) {
69 error("dict_new:: failed to allocate storage");
70 }
71 return dict;
72 }
73
dict_free(XMLDICT * dict)74 void dict_free(XMLDICT *dict)
75 {
76 if(dict) {
77 if(dict->entries)
78 free(dict->entries);
79 free(dict);
80 }
81 }
82
dict_find(XMLDICT * dict,XMLSTRING name)83 const void *dict_find(XMLDICT *dict, XMLSTRING name)
84 {
85 if(!dict || !name)
86 return NULL;
87
88 unsigned h = bucket_number(name);
89 for(h=dict->hash[h];h;) {
90 --h;
91 if(xmls_equals(dict->entries[h].name, name)) return dict->entries[h].data;
92 h = dict->entries[h].next;
93 }
94 return NULL;
95 }
96
dict_add(XMLDICT * dict,XMLSTRING name,const void * data)97 int dict_add(XMLDICT *dict, XMLSTRING name, const void *data)
98 {
99 unsigned h,d;
100
101 if(!dict || !name) return 0;
102
103 if(dict->used >= dict->allocated) {
104 dict->allocated += 100;
105 dict->entries = realloc(dict->entries,dict->allocated * sizeof(XMLDICTENTRY));
106 }
107
108 d = h = bucket_number(name);
109 for(h=dict->hash[h];h;) {
110 --h;
111 if(xmls_equals(dict->entries[h].name, name)) return 0; // already have this
112 h = dict->entries[h].next;
113 }
114 dict->entries[dict->used].name = name;
115 dict->entries[dict->used].data = data;
116 dict->entries[dict->used].next = dict->hash[d];
117 dict->hash[d] = ++dict->used;
118 return 1;
119 }
120
dict_replace(XMLDICT * dict,XMLSTRING name,const void * data)121 void dict_replace(XMLDICT *dict, XMLSTRING name, const void *data)
122 {
123 if(!dict || !name)
124 return;
125
126 if(dict->used >= dict->allocated) {
127 dict->allocated += 100;
128 dict->entries = realloc(dict->entries,dict->allocated * sizeof(XMLDICTENTRY));
129 }
130 dict->entries[dict->used].name = name;
131 dict->entries[dict->used].data = data;
132
133 unsigned h = bucket_number(name);
134 dict->entries[dict->used].next = dict->hash[h];
135 dict->hash[h] = ++dict->used;
136 }
137