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