← Back to branch summary

~linuxjedi/drizzle/trunk-bug-667053

« back to all changes in this revision

Viewing changes to client/completion_hash.cc

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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