1 /*
2 * epos/src/hash.cc
3 * (c) geo@cuni.cz (Jirka Hanika)
4 *
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License in doc/COPYING for more details.
14 *
15 *
16 */
17
18 #include "epos.h"
19 #include "hashtmpl.h"
20
21 int _hash_sp = 0;
22 hsearchtree <void, void> **_hash_stk[_HASH_DEPTH+1];
23
24 /****************************************************************************
25 This constructor will construct a hash table out of a text file "filename".
26 Its potential capacity will be adjusted to the percentage_full specified.
27 The parameters are explained in hash.h
28 ****************************************************************************/
29
hash(const char * filename,const char * dirname,const char * treename,const char * description,int perc_full,int perc_downsize,int perc_upsize,int max_tree_depth,bool allow_id,bool multi_data)30 hash::hash(const char *filename, const char *dirname, const char *treename,
31 const char *description,
32 int perc_full, int perc_downsize, int perc_upsize,
33 int max_tree_depth, bool allow_id, bool multi_data)
34 : hash_table<char, char>(0)
35 {
36 text *hashfile;
37 char *buff;
38 char *key;
39 const char *value;
40 int l = 0;
41 char *tmp;
42 free(ht);
43 ht = NULL;
44
45 dupkey = dupdata = true;
46 buff = get_text_line_buffer();
47
48 D_PRINT(0, "hash::hash: using file %s\n", filename);
49
50 maxdep = longest = items = 0;
51 if (max_tree_depth == -1) max_tree_depth=_HASH_DEPTH;
52 perc_optimal = perc_full;
53
54 capacity = 0;
55 hashfile = new text(filename, dirname, treename, description, true);
56 if (!description && !hashfile->exists()) {
57 shriek(811, "%s: Description required with hash tables", filename);
58 }
59 while (hashfile->get_line(buff)) l++;
60
61 capacity = l*100/perc_full | 1;
62 cfg_rehash(perc_downsize, perc_upsize, max_tree_depth);
63 ht = (hsearchtree<char, char> **)xcalloc(capacity,sizeof(hsearchtree<char, char>*));
64 // fseek(hashfile, 0, SEEK_SET);
65 hashfile->rewind(false);
66 l = 0;
67 while (l++, hashfile->get_line(buff)) try {
68 tmp = buff + strlen(buff);
69 while (strchr(WHITESPACE, *--tmp) && tmp>=buff);
70 tmp[1]=0; //Strip out trailing whitespace
71
72 tmp = key = buff + strspn(buff, WHITESPACE);
73 if (!*key) continue; //Nothing but a comment
74 tmp += strcspn(key, WHITESPACE);
75 if (*tmp) *tmp++ = 0; //terminate the key and go on
76 value = tmp += strspn(tmp, WHITESPACE);
77 if (!*value) switch (allow_id) {
78 case true: value = key; break;
79 case false: shriek(811, "%s:%d No value specified",
80 hashfile->current_file, hashfile->current_line);
81 // default: value = no_data;
82 }
83 else if (!multi_data && tmp[strcspn(tmp,WHITESPACE)])
84 shriek(811, "%s:%d Multiple values specified", hashfile->current_file, hashfile->current_line);
85 add(key, value);
86 } catch (any_exception *e) {
87 if (e->code / 10 != 81) throw e;
88 delete e;
89 }
90 // fclose(hashfile);
91 delete hashfile;
92 // fail:
93 free(buff);
94
95 D_PRINT(0, "hash::hash: successfully returning, file %s\n", filename);
96 if (_hash_sp) shriek(862, "Hash stack dirty! %d", _hash_sp);
97 }
98
add_int(const char * key,int value)99 void hash::add_int(const char *key, int value)
100 {
101 char buff[MAX_DIGITS+1];
102 char *i;
103 buff[MAX_DIGITS]=0;
104 i=buff+MAX_DIGITS-1;
105 char negative=value<0;
106 if (negative) value *=-1;
107 do {
108 *i=(char)((unsigned int)value%10 + '0');
109 value = (unsigned int)value / 10;
110 i--;
111 } while (value);
112 if (negative) *i='-'; else i++;
113 D_PRINT(0, "hash::add_int %s to '%s'\n",key,i);
114 add(key, (char *)i);
115 }
116
117 int
translate_int(const char * key)118 hash::translate_int(const char *key)
119 {
120 char *result;
121 char *i;
122 signed char sign=1;
123 unsigned int to_return=0;
124 if(!(result=(char *)translate(key))) return INT_NOT_FOUND;
125 if (*result=='-') result++,sign=-1;
126 if (*result=='+') result++;
127 for(i=result;*i;i++) to_return=to_return*10+*i-'0';
128 return (int)to_return*sign;
129 }
130
131 void
debug()132 hash::debug()
133 {
134 int i;
135 D_PRINT(1, "hash::debug dump follows\n");
136 for(i=0;i<capacity;i++) listtree(ht[i], 0);
137 D_PRINT(1, "hash::debug done.\n");
138 }
139
140
141 // forall(_hdump);
142
143
144 /****************************************************************************
145 Various little nothings
146 ****************************************************************************/
147
148 void
listtree(hsearchtree<char,char> * tree,int indent)149 hash::listtree(hsearchtree <char, char> *tree, int indent)
150 {
151 if (tree!=NULL) {
152 for(int i=0; i<indent; i++) D_PRINT(1, " ");
153 D_PRINT(1, "%s %s %d\n",(char *)tree->key,(char *)tree->data, tree->height);
154 if (tree->l && tree->r && tree->height!=tree->l->height+1 &&
155 tree->height!=tree->r->height+1 ||
156 !tree->r && tree->l && tree->l->height+1!=tree->height ||
157 !tree->l && tree->r && tree->r->height+1!=tree->height )
158 // shriek(862, "Bad height: %d", tree->height);
159 listtree(tree->r, indent+1);
160 listtree(tree->l, indent+1);
161 // if (tree->l && tree->r && abs(tree->l->height-tree->r->height)>1)
162 // shriek(862, "Both children, but bad: %d", tree->height);
163 }
164 }
165
166 slab <hsearchtree_size> *hash_tree_slab = 0;
167
shutdown_hashing()168 void shutdown_hashing()
169 {
170 #ifdef HASH_IS_SLABBING
171 if (hash_tree_slab) delete hash_tree_slab;
172 #endif
173 }
174