← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to client/completion_hash.cc

  • Committer: Brian Aker
  • Date: 2009-07-11 19:23:04 UTC
  • mfrom: (1089.1.14 merge)
  • Revision ID: brian@gaz-20090711192304-ootijyl5yf9jq9kd
Merge Brian

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 "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
 
}