1 /* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
15
16 /* Quick & light hash implementation for tab completion purposes
17 *
18 * by Andi Gutmans <andi@zend.com>
19 * and Zeev Suraski <zeev@zend.com>
20 * Small portability changes by Monty. Changed also to use my_malloc/my_free
21 */
22
23 #include <my_global.h>
24 #include <m_string.h>
25 #include <my_sys.h>
26 #include "completion_hash.h"
27
hashpjw(const char * arKey,uint nKeyLength)28 uint hashpjw(const char *arKey, uint nKeyLength)
29 {
30 uint h = 0, g, i;
31
32 for (i = 0; i < nKeyLength; i++) {
33 h = (h << 4) + arKey[i];
34 if ((g = (h & 0xF0000000))) {
35 h = h ^ (g >> 24);
36 h = h ^ g;
37 }
38 }
39 return h;
40 }
41
completion_hash_init(HashTable * ht,uint nSize)42 int completion_hash_init(HashTable *ht, uint nSize)
43 {
44 ht->arBuckets = (Bucket **) my_malloc(nSize* sizeof(Bucket *),
45 MYF(MY_ZEROFILL | MY_WME));
46
47 if (!ht->arBuckets)
48 {
49 ht->initialized = 0;
50 return FAILURE;
51 }
52 init_alloc_root(&ht->mem_root, "completion_hash", 8192, 0, MYF(0));
53 ht->pHashFunction = hashpjw;
54 ht->nTableSize = nSize;
55 ht->initialized = 1;
56 return SUCCESS;
57 }
58
59
completion_hash_update(HashTable * ht,char * arKey,uint nKeyLength,char * str)60 int completion_hash_update(HashTable *ht, char *arKey, uint nKeyLength,
61 char *str)
62 {
63 uint h, nIndex;
64
65 Bucket *p;
66
67 h = ht->pHashFunction(arKey, nKeyLength);
68 nIndex = h % ht->nTableSize;
69
70 if (nKeyLength <= 0) {
71 return FAILURE;
72 }
73 p = ht->arBuckets[nIndex];
74 while (p)
75 {
76 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
77 if (!memcmp(p->arKey, arKey, nKeyLength)) {
78 entry *n;
79
80 if (!(n = (entry *) alloc_root(&ht->mem_root,sizeof(entry))))
81 return FAILURE;
82 n->pNext = p->pData;
83 n->str = str;
84 p->pData = n;
85 p->count++;
86
87 return SUCCESS;
88 }
89 }
90 p = p->pNext;
91 }
92
93 if (!(p = (Bucket *) alloc_root(&ht->mem_root, sizeof(Bucket))))
94 return FAILURE;
95
96 p->arKey = arKey;
97 p->nKeyLength = nKeyLength;
98 p->h = h;
99
100 if (!(p->pData = (entry*) alloc_root(&ht->mem_root, sizeof(entry))))
101 return FAILURE;
102
103 p->pData->str = str;
104 p->pData->pNext = 0;
105 p->count = 1;
106
107 p->pNext = ht->arBuckets[nIndex];
108 ht->arBuckets[nIndex] = p;
109
110 return SUCCESS;
111 }
112
completion_hash_find(HashTable * ht,const char * arKey,uint nKeyLength)113 static Bucket *completion_hash_find(HashTable *ht, const char *arKey,
114 uint nKeyLength)
115 {
116 uint h, nIndex;
117 Bucket *p;
118
119 h = ht->pHashFunction(arKey, nKeyLength);
120 nIndex = h % ht->nTableSize;
121
122 p = ht->arBuckets[nIndex];
123 while (p)
124 {
125 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
126 if (!memcmp(p->arKey, arKey, nKeyLength)) {
127 return p;
128 }
129 }
130 p = p->pNext;
131 }
132 return (Bucket*) 0;
133 }
134
135
completion_hash_exists(HashTable * ht,char * arKey,uint nKeyLength)136 int completion_hash_exists(HashTable *ht, char *arKey, uint nKeyLength)
137 {
138 uint h, nIndex;
139 Bucket *p;
140
141 h = ht->pHashFunction(arKey, nKeyLength);
142 nIndex = h % ht->nTableSize;
143
144 p = ht->arBuckets[nIndex];
145 while (p)
146 {
147 if ((p->h == h) && (p->nKeyLength == nKeyLength))
148 {
149 if (!strcmp(p->arKey, arKey)) {
150 return 1;
151 }
152 }
153 p = p->pNext;
154 }
155 return 0;
156 }
157
find_all_matches(HashTable * ht,const char * str,uint length,uint * res_length)158 Bucket *find_all_matches(HashTable *ht, const char *str, uint length,
159 uint *res_length)
160 {
161 Bucket *b;
162
163 b = completion_hash_find(ht,str,length);
164 if (!b) {
165 *res_length = 0;
166 return (Bucket*) 0;
167 } else {
168 *res_length = length;
169 return b;
170 }
171 }
172
find_longest_match(HashTable * ht,char * str,uint length,uint * res_length)173 Bucket *find_longest_match(HashTable *ht, char *str, uint length,
174 uint *res_length)
175 {
176 Bucket *b,*return_b;
177 char *s;
178 uint count;
179 uint lm;
180
181 b = completion_hash_find(ht,str,length);
182 if (!b) {
183 *res_length = 0;
184 return (Bucket*) 0;
185 }
186
187 count = b->count;
188 lm = length;
189 s = b->pData->str;
190
191 return_b = b;
192 while (s[lm]!=0 && (b=completion_hash_find(ht,s,lm+1))) {
193 if (b->count<count) {
194 *res_length=lm;
195 return return_b;
196 }
197 return_b=b;
198 lm++;
199 }
200 *res_length=lm;
201 return return_b;
202 }
203
204
completion_hash_clean(HashTable * ht)205 void completion_hash_clean(HashTable *ht)
206 {
207 free_root(&ht->mem_root,MYF(0));
208 if (size_t s= ht->nTableSize)
209 bzero((char*) ht->arBuckets, s * sizeof(Bucket *));
210 }
211
212
completion_hash_free(HashTable * ht)213 void completion_hash_free(HashTable *ht)
214 {
215 completion_hash_clean(ht);
216 my_free(ht->arBuckets);
217 }
218
219
add_word(HashTable * ht,char * str)220 void add_word(HashTable *ht,char *str)
221 {
222 int i;
223 char *pos=str;
224 for (i=1; *pos; i++, pos++)
225 completion_hash_update(ht, str, i, str);
226 }
227