1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates.
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(PSI_NOT_INSTRUMENTED,
52 nSize* sizeof(Bucket *),
53 MYF(MY_ZEROFILL | MY_WME));
54
55 if (!ht->arBuckets)
56 {
57 ht->initialized = 0;
58 return FAILURE;
59 }
60 init_alloc_root(PSI_NOT_INSTRUMENTED, &ht->mem_root, 8192, 0);
61 ht->pHashFunction = hashpjw;
62 ht->nTableSize = nSize;
63 ht->initialized = 1;
64 return SUCCESS;
65 }
66
67
completion_hash_update(HashTable * ht,char * arKey,uint nKeyLength,char * str)68 int completion_hash_update(HashTable *ht, char *arKey, uint nKeyLength,
69 char *str)
70 {
71 uint h, nIndex;
72
73 Bucket *p;
74
75 h = ht->pHashFunction(arKey, nKeyLength);
76 nIndex = h % ht->nTableSize;
77
78 if (nKeyLength <= 0) {
79 return FAILURE;
80 }
81 p = ht->arBuckets[nIndex];
82 while (p)
83 {
84 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
85 if (!memcmp(p->arKey, arKey, nKeyLength)) {
86 entry *n;
87
88 if (!(n = (entry *) alloc_root(&ht->mem_root,sizeof(entry))))
89 return FAILURE;
90 n->pNext = p->pData;
91 n->str = str;
92 p->pData = n;
93 p->count++;
94
95 return SUCCESS;
96 }
97 }
98 p = p->pNext;
99 }
100
101 if (!(p = (Bucket *) alloc_root(&ht->mem_root, sizeof(Bucket))))
102 return FAILURE;
103
104 p->arKey = arKey;
105 p->nKeyLength = nKeyLength;
106 p->h = h;
107
108 if (!(p->pData = (entry*) alloc_root(&ht->mem_root, sizeof(entry))))
109 return FAILURE;
110
111 p->pData->str = str;
112 p->pData->pNext = 0;
113 p->count = 1;
114
115 p->pNext = ht->arBuckets[nIndex];
116 ht->arBuckets[nIndex] = p;
117
118 return SUCCESS;
119 }
120
completion_hash_find(HashTable * ht,const char * arKey,uint nKeyLength)121 static Bucket *completion_hash_find(HashTable *ht, const char *arKey,
122 uint nKeyLength)
123 {
124 uint h, nIndex;
125 Bucket *p;
126
127 h = ht->pHashFunction(arKey, nKeyLength);
128 nIndex = h % ht->nTableSize;
129
130 p = ht->arBuckets[nIndex];
131 while (p)
132 {
133 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
134 if (!memcmp(p->arKey, arKey, nKeyLength)) {
135 return p;
136 }
137 }
138 p = p->pNext;
139 }
140 return (Bucket*) 0;
141 }
142
143
completion_hash_exists(HashTable * ht,char * arKey,uint nKeyLength)144 int completion_hash_exists(HashTable *ht, char *arKey, uint nKeyLength)
145 {
146 uint h, nIndex;
147 Bucket *p;
148
149 h = ht->pHashFunction(arKey, nKeyLength);
150 nIndex = h % ht->nTableSize;
151
152 p = ht->arBuckets[nIndex];
153 while (p)
154 {
155 if ((p->h == h) && (p->nKeyLength == nKeyLength))
156 {
157 if (!strcmp(p->arKey, arKey)) {
158 return 1;
159 }
160 }
161 p = p->pNext;
162 }
163 return 0;
164 }
165
find_all_matches(HashTable * ht,const char * str,uint length,uint * res_length)166 Bucket *find_all_matches(HashTable *ht, const char *str, uint length,
167 uint *res_length)
168 {
169 Bucket *b;
170
171 b = completion_hash_find(ht,str,length);
172 if (!b) {
173 *res_length = 0;
174 return (Bucket*) 0;
175 } else {
176 *res_length = length;
177 return b;
178 }
179 }
180
find_longest_match(HashTable * ht,char * str,uint length,uint * res_length)181 Bucket *find_longest_match(HashTable *ht, char *str, uint length,
182 uint *res_length)
183 {
184 Bucket *b,*return_b;
185 char *s;
186 uint count;
187 uint lm;
188
189 b = completion_hash_find(ht,str,length);
190 if (!b) {
191 *res_length = 0;
192 return (Bucket*) 0;
193 }
194
195 count = b->count;
196 lm = length;
197 s = b->pData->str;
198
199 return_b = b;
200 while (s[lm]!=0 && (b=completion_hash_find(ht,s,lm+1))) {
201 if (b->count<count) {
202 *res_length=lm;
203 return return_b;
204 }
205 return_b=b;
206 lm++;
207 }
208 *res_length=lm;
209 return return_b;
210 }
211
212
completion_hash_clean(HashTable * ht)213 void completion_hash_clean(HashTable *ht)
214 {
215 free_root(&ht->mem_root,MYF(0));
216 memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
217 }
218
219
completion_hash_free(HashTable * ht)220 void completion_hash_free(HashTable *ht)
221 {
222 completion_hash_clean(ht);
223 my_free(ht->arBuckets);
224 }
225
226
add_word(HashTable * ht,char * str)227 void add_word(HashTable *ht,char *str)
228 {
229 int i;
230 char *pos=str;
231 for (i=1; *pos; i++, pos++)
232 completion_hash_update(ht, str, i, str);
233 }
234