← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to client/completion_hash.cc

Merged in trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
client/completion_hash.cc
1
 
/* Copyright (C) 2000 MySQL AB
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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.
21
 
 */
22
 
 
23
 
#include "client_priv.h"
24
 
#include <mystrings/m_string.h>
25
 
#include "completion_hash.h"
26
 
 
27
 
uint hashpjw(const char *arKey, uint nKeyLength)
28
 
{
29
 
  uint h = 0, g, i;
30
 
 
31
 
  for (i = 0; i < nKeyLength; i++) {
32
 
    h = (h << 4) + arKey[i];
33
 
    if ((g = (h & 0xF0000000))) {
34
 
      h = h ^ (g >> 24);
35
 
      h = h ^ g;
36
 
    }
37
 
  }
38
 
  return h;
39
 
}
40
 
 
41
 
int completion_hash_init(HashTable *ht, uint nSize)
42
 
{
43
 
  ht->arBuckets = (Bucket **) malloc(nSize* sizeof(Bucket *));
44
 
  memset(ht->arBuckets, 0, nSize* sizeof(Bucket *));
45
 
 
46
 
  if (!ht->arBuckets)
47
 
  {
48
 
    ht->initialized = 0;
49
 
    return FAILURE;
50
 
  }
51
 
  init_alloc_root(&ht->mem_root, 8192, 0);
52
 
  ht->pHashFunction = hashpjw;
53
 
  ht->nTableSize = nSize;
54
 
  ht->initialized = 1;
55
 
  return SUCCESS;
56
 
}
57
 
 
58
 
 
59
 
int completion_hash_update(HashTable *ht, char *arKey, uint nKeyLength,
60
 
                           char *str)
61
 
{
62
 
  uint h, nIndex;
63
 
 
64
 
  Bucket *p;
65
 
 
66
 
  h = ht->pHashFunction(arKey, nKeyLength);
67
 
  nIndex = h % ht->nTableSize;
68
 
 
69
 
  if (nKeyLength <= 0) {
70
 
    return FAILURE;
71
 
  }
72
 
  p = ht->arBuckets[nIndex];
73
 
  while (p)
74
 
  {
75
 
    if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
76
 
      if (!memcmp(p->arKey, arKey, nKeyLength)) {
77
 
        entry *n;
78
 
 
79
 
        if (!(n = (entry *) alloc_root(&ht->mem_root,sizeof(entry))))
80
 
          return FAILURE;
81
 
        n->pNext = p->pData;
82
 
        n->str = str;
83
 
        p->pData = n;
84
 
        p->count++;
85
 
 
86
 
        return SUCCESS;
87
 
      }
88
 
    }
89
 
    p = p->pNext;
90
 
  }
91
 
 
92
 
  if (!(p = (Bucket *) alloc_root(&ht->mem_root, sizeof(Bucket))))
93
 
    return FAILURE;
94
 
 
95
 
  p->arKey = arKey;
96
 
  p->nKeyLength = nKeyLength;
97
 
  p->h = h;
98
 
 
99
 
  if (!(p->pData = (entry*) alloc_root(&ht->mem_root, sizeof(entry))))
100
 
    return FAILURE;
101
 
 
102
 
  p->pData->str = str;
103
 
  p->pData->pNext = 0;
104
 
  p->count = 1;
105
 
 
106
 
  p->pNext = ht->arBuckets[nIndex];
107
 
  ht->arBuckets[nIndex] = p;
108
 
 
109
 
  return SUCCESS;
110
 
}
111
 
 
112
 
static Bucket *completion_hash_find(HashTable *ht, const char *arKey,
113
 
                                    uint nKeyLength)
114
 
{
115
 
  uint h, nIndex;
116
 
  Bucket *p;
117
 
 
118
 
  h = ht->pHashFunction(arKey, nKeyLength);
119
 
  nIndex = h % ht->nTableSize;
120
 
 
121
 
  p = ht->arBuckets[nIndex];
122
 
  while (p)
123
 
  {
124
 
    if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
125
 
      if (!memcmp(p->arKey, arKey, nKeyLength)) {
126
 
        return p;
127
 
      }
128
 
    }
129
 
    p = p->pNext;
130
 
  }
131
 
  return (Bucket*) 0;
132
 
}
133
 
 
134
 
 
135
 
int completion_hash_exists(HashTable *ht, char *arKey, uint nKeyLength)
136
 
{
137
 
  uint h, nIndex;
138
 
  Bucket *p;
139
 
 
140
 
  h = ht->pHashFunction(arKey, nKeyLength);
141
 
  nIndex = h % ht->nTableSize;
142
 
 
143
 
  p = ht->arBuckets[nIndex];
144
 
  while (p)
145
 
  {
146
 
    if ((p->h == h) && (p->nKeyLength == nKeyLength))
147
 
    {
148
 
      if (!strcmp(p->arKey, arKey)) {
149
 
        return 1;
150
 
      }
151
 
    }
152
 
    p = p->pNext;
153
 
  }
154
 
  return 0;
155
 
}
156
 
 
157
 
Bucket *find_all_matches(HashTable *ht, const char *str, uint length,
158
 
                         uint *res_length)
159
 
{
160
 
  Bucket *b;
161
 
 
162
 
  b = completion_hash_find(ht,str,length);
163
 
  if (!b) {
164
 
    *res_length = 0;
165
 
    return (Bucket*) 0;
166
 
  } else {
167
 
    *res_length = length;
168
 
    return b;
169
 
  }
170
 
}
171
 
 
172
 
Bucket *find_longest_match(HashTable *ht, char *str, uint length,
173
 
                           uint *res_length)
174
 
{
175
 
  Bucket *b,*return_b;
176
 
  char *s;
177
 
  uint count;
178
 
  uint lm;
179
 
 
180
 
  b = completion_hash_find(ht,str,length);
181
 
  if (!b) {
182
 
    *res_length = 0;
183
 
    return (Bucket*) 0;
184
 
  }
185
 
 
186
 
  count = b->count;
187
 
  lm = length;
188
 
  s = b->pData->str;
189
 
 
190
 
  return_b = b;
191
 
  while (s[lm]!=0 && (b=completion_hash_find(ht,s,lm+1))) {
192
 
    if (b->count<count) {
193
 
      *res_length=lm;
194
 
      return return_b;
195
 
    }
196
 
    return_b=b;
197
 
    lm++;
198
 
  }
199
 
  *res_length=lm;
200
 
  return return_b;
201
 
}
202
 
 
203
 
 
204
 
void completion_hash_clean(HashTable *ht)
205
 
{
206
 
  free_root(&ht->mem_root,MYF(0));
207
 
  memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
208
 
}
209
 
 
210
 
 
211
 
void completion_hash_free(HashTable *ht)
212
 
{
213
 
  completion_hash_clean(ht);
214
 
  free(ht->arBuckets);
215
 
}
216
 
 
217
 
 
218
 
void add_word(HashTable *ht,char *str)
219
 
{
220
 
  int i;
221
 
  char *pos=str;
222
 
  for (i=1; *pos; i++, pos++)
223
 
    completion_hash_update(ht, str, i, str);
224
 
}