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-1301 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
28uint 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
42int 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
60int 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
113static 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
136int 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
158Bucket *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
173Bucket *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
205void completion_hash_clean(HashTable *ht)
206{
207 free_root(&ht->mem_root,MYF(0));
208 bzero((char*) ht->arBuckets,ht->nTableSize*sizeof(Bucket *));
209}
210
211
212void completion_hash_free(HashTable *ht)
213{
214 completion_hash_clean(ht);
215 my_free(ht->arBuckets);
216}
217
218
219void add_word(HashTable *ht,char *str)
220{
221 int i;
222 char *pos=str;
223 for (i=1; *pos; i++, pos++)
224 completion_hash_update(ht, str, i, str);
225}
226