← 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-01-21 23:38:47 UTC
  • mto: This revision was merged to the branch mainline in revision 801.
  • Revision ID: brian@tangent.org-20090121233847-jzjpp910j73ch3tw
Factor test-run for binlog removal

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
}