← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to client/completion_hash.c

  • Committer: Andy Lester
  • Date: 2008-08-09 05:23:39 UTC
  • mto: (266.1.29 use-replace-funcs)
  • mto: This revision was merged to the branch mainline in revision 287.
  • Revision ID: andy@petdance.com-20080809052339-iafoesszmesweq6b
use NULL, not 0

Show diffs side-by-side

added added

removed removed

Lines of Context:
client/completion_hash.c
 
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. Changed also to use my_malloc/my_free
 
21
 */
 
22
 
 
23
#include "client_priv.h"
 
24
#include <mystrings/m_string.h>
 
25
#undef SAFEMALLOC                               // Speed things up
 
26
#include "completion_hash.h"
 
27
 
 
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
 
 
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, 8192, 0);
 
53
  ht->pHashFunction = hashpjw;
 
54
  ht->nTableSize = nSize;
 
55
  ht->initialized = 1;
 
56
  return SUCCESS;
 
57
}
 
58
 
 
59
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
205
void completion_hash_clean(HashTable *ht)
 
206
{
 
207
  free_root(&ht->mem_root,MYF(0));
 
208
  memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
 
209
}
 
210
 
 
211
 
 
212
void completion_hash_free(HashTable *ht)
 
213
{
 
214
  completion_hash_clean(ht);
 
215
  my_free(ht->arBuckets, MYF(0));
 
216
}
 
217
 
 
218
 
 
219
void 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
}