520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
1 |
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
|
2 |
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
|
|
3 |
*
|
|
1999.6.1
by kalebral at gmail
update Copyright strings to a more common format to help with creating the master debian copyright file |
4 |
* Copyright (C) 2008 Sun Microsystems, Inc.
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
5 |
*
|
6 |
* This program is free software; you can redistribute it and/or modify
|
|
7 |
* it under the terms of the GNU General Public License as published by
|
|
8 |
* the Free Software Foundation; version 2 of the License.
|
|
9 |
*
|
|
10 |
* This program is distributed in the hope that it will be useful,
|
|
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
13 |
* GNU General Public License for more details.
|
|
14 |
*
|
|
15 |
* You should have received a copy of the GNU General Public License
|
|
16 |
* along with this program; if not, write to the Free Software
|
|
17 |
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
|
|
18 |
*/
|
|
19 |
||
20 |
/* The hash functions used for saving keys */
|
|
1
by brian
clean slate |
21 |
/* One of key_length or key_length_offset must be given */
|
22 |
/* Key length of 0 isn't allowed */
|
|
23 |
||
2173.2.1
by Monty Taylor
Fixes incorrect usage of include |
24 |
#include <config.h> |
25 |
#include <drizzled/my_hash.h> |
|
26 |
#include <drizzled/charset.h> |
|
27 |
#include <drizzled/charset_info.h> |
|
2221.7.5
by Olaf van der Spek
Refactor |
28 |
#include <vector> |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
29 |
|
2221.7.5
by Olaf van der Spek
Refactor |
30 |
namespace drizzled { |
1280.1.10
by Monty Taylor
Put everything in drizzled into drizzled namespace. |
31 |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
32 |
const uint32_t NO_RECORD= UINT32_MAX; |
33 |
||
34 |
const int LOWFIND= 1; |
|
35 |
const int LOWUSED= 2; |
|
36 |
const int HIGHFIND= 4; |
|
37 |
const int HIGHUSED= 8; |
|
1
by brian
clean slate |
38 |
|
2221.7.5
by Olaf van der Spek
Refactor |
39 |
static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength); |
40 |
static void movelink(HASH_LINK *array, uint32_t pos, uint32_t next_link, uint32_t newlink); |
|
41 |
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key, size_t length); |
|
42 |
||
43 |
static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length) |
|
1
by brian
clean slate |
44 |
{
|
290
by Brian Aker
Update for ulong change over. |
45 |
uint32_t nr1=1, nr2=4; |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
46 |
hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2); |
1
by brian
clean slate |
47 |
return nr1; |
48 |
}
|
|
49 |
||
2210.3.6
by Olaf van der Spek
Use push_back |
50 |
#define dynamic_element(array,array_index,type) ((type)((array)->buffer) +(array_index))
|
51 |
||
146
by Brian Aker
my_bool cleanup. |
52 |
bool
|
2254
by Brian Aker
Shift CHARSET_INFO to charset_info_st |
53 |
_hash_init(HASH *hash,uint32_t growth_size, const charset_info_st * const charset, |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
54 |
uint32_t size, size_t key_offset, size_t key_length, |
55 |
hash_get_key get_key, |
|
598.1.1
by Super-User
Fixed solaris build crap. |
56 |
hash_free_key free_element, uint32_t flags) |
1
by brian
clean slate |
57 |
{
|
58 |
hash->records=0; |
|
59 |
if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size, |
|
60 |
growth_size)) |
|
61 |
{
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
62 |
/* Allow call to hash_free */
|
63 |
hash->free=0; |
|
202.3.7
by Monty Taylor
Gettext error compiles and passes test! |
64 |
return true; |
1
by brian
clean slate |
65 |
}
|
66 |
hash->key_offset=key_offset; |
|
67 |
hash->key_length=key_length; |
|
68 |
hash->blength=1; |
|
69 |
hash->get_key=get_key; |
|
70 |
hash->free=free_element; |
|
71 |
hash->flags=flags; |
|
72 |
hash->charset=charset; |
|
202.3.7
by Monty Taylor
Gettext error compiles and passes test! |
73 |
return false; |
1
by brian
clean slate |
74 |
}
|
75 |
||
76 |
||
77 |
/*
|
|
78 |
Call hash->free on all elements in hash.
|
|
79 |
||
80 |
SYNOPSIS
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
81 |
hash_free_elements()
|
82 |
hash hash table
|
|
1
by brian
clean slate |
83 |
|
84 |
NOTES:
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
85 |
Sets records to 0
|
1
by brian
clean slate |
86 |
*/
|
87 |
||
88 |
static inline void hash_free_elements(HASH *hash) |
|
89 |
{
|
|
90 |
if (hash->free) |
|
91 |
{
|
|
92 |
HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*); |
|
93 |
HASH_LINK *end= data + hash->records; |
|
94 |
while (data < end) |
|
95 |
(*hash->free)((data++)->data); |
|
96 |
}
|
|
97 |
hash->records=0; |
|
98 |
}
|
|
99 |
||
100 |
||
101 |
/*
|
|
102 |
Free memory used by hash.
|
|
103 |
||
104 |
SYNOPSIS
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
105 |
hash_free()
|
106 |
hash the hash to delete elements of
|
|
1
by brian
clean slate |
107 |
|
108 |
NOTES: Hash can't be reused without calling hash_init again.
|
|
109 |
*/
|
|
110 |
||
111 |
void hash_free(HASH *hash) |
|
112 |
{
|
|
113 |
hash_free_elements(hash); |
|
114 |
hash->free= 0; |
|
115 |
delete_dynamic(&hash->array); |
|
116 |
}
|
|
117 |
||
118 |
/* some helper functions */
|
|
119 |
||
120 |
/*
|
|
481
by Brian Aker
Remove all of uchar. |
121 |
This function is char* instead of unsigned char* as HPUX11 compiler can't
|
1
by brian
clean slate |
122 |
handle inline functions that are not defined as native types
|
123 |
*/
|
|
124 |
||
125 |
static inline char* |
|
481
by Brian Aker
Remove all of uchar. |
126 |
hash_key(const HASH *hash, const unsigned char *record, size_t *length, |
146
by Brian Aker
my_bool cleanup. |
127 |
bool first) |
1
by brian
clean slate |
128 |
{
|
129 |
if (hash->get_key) |
|
130 |
return (char*) (*hash->get_key)(record,length,first); |
|
131 |
*length=hash->key_length; |
|
132 |
return (char*) record+hash->key_offset; |
|
133 |
}
|
|
134 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
135 |
/* Calculate pos according to keys */
|
1
by brian
clean slate |
136 |
|
482
by Brian Aker
Remove uint. |
137 |
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength) |
1
by brian
clean slate |
138 |
{
|
139 |
if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1)); |
|
140 |
return (hashnr & ((buffmax >> 1) -1)); |
|
141 |
}
|
|
142 |
||
482
by Brian Aker
Remove uint. |
143 |
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos, |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
144 |
uint32_t buffmax, uint32_t maxlength) |
1
by brian
clean slate |
145 |
{
|
146 |
size_t length; |
|
481
by Brian Aker
Remove all of uchar. |
147 |
unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0); |
1
by brian
clean slate |
148 |
return hash_mask(calc_hash(hash,key,length),buffmax,maxlength); |
149 |
}
|
|
150 |
||
151 |
||
152 |
||
153 |
static
|
|
154 |
inline
|
|
481
by Brian Aker
Remove all of uchar. |
155 |
unsigned int rec_hashnr(HASH *hash,const unsigned char *record) |
1
by brian
clean slate |
156 |
{
|
157 |
size_t length; |
|
481
by Brian Aker
Remove all of uchar. |
158 |
unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0); |
1
by brian
clean slate |
159 |
return calc_hash(hash,key,length); |
160 |
}
|
|
161 |
||
162 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
163 |
unsigned char* hash_search(const HASH *hash, const unsigned char *key, |
164 |
size_t length) |
|
1
by brian
clean slate |
165 |
{
|
166 |
HASH_SEARCH_STATE state; |
|
167 |
return hash_first(hash, key, length, &state); |
|
168 |
}
|
|
169 |
||
170 |
/*
|
|
171 |
Search after a record based on a key
|
|
172 |
||
173 |
NOTE
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
174 |
Assigns the number of the found record to HASH_SEARCH_STATE state
|
1
by brian
clean slate |
175 |
*/
|
176 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
177 |
unsigned char* hash_first(const HASH *hash, const unsigned char *key, |
178 |
size_t length, |
|
179 |
HASH_SEARCH_STATE *current_record) |
|
1
by brian
clean slate |
180 |
{
|
181 |
HASH_LINK *pos; |
|
482
by Brian Aker
Remove uint. |
182 |
uint32_t flag,idx; |
1
by brian
clean slate |
183 |
|
184 |
flag=1; |
|
185 |
if (hash->records) |
|
186 |
{
|
|
187 |
idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length), |
|
1138
by Brian Aker
Merge of Joe Daly's work |
188 |
hash->blength,hash->records); |
1
by brian
clean slate |
189 |
do
|
190 |
{
|
|
191 |
pos= dynamic_element(&hash->array,idx,HASH_LINK*); |
|
192 |
if (!hashcmp(hash,pos,key,length)) |
|
193 |
{
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
194 |
*current_record= idx; |
195 |
return (pos->data); |
|
1
by brian
clean slate |
196 |
}
|
197 |
if (flag) |
|
198 |
{
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
199 |
/* Reset flag */
|
200 |
flag=0; |
|
1138
by Brian Aker
Merge of Joe Daly's work |
201 |
if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx) |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
202 |
/* Wrong link */
|
203 |
break; |
|
1
by brian
clean slate |
204 |
}
|
205 |
}
|
|
206 |
while ((idx=pos->next) != NO_RECORD); |
|
207 |
}
|
|
208 |
*current_record= NO_RECORD; |
|
51.3.13
by Jay Pipes
Phase 1 removal of DBUG in mysys |
209 |
return(0); |
1
by brian
clean slate |
210 |
}
|
211 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
212 |
/* Get next record with identical key */
|
213 |
/* Can only be called if previous calls was hash_search */
|
|
1
by brian
clean slate |
214 |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
215 |
unsigned char* hash_next(const HASH *hash, const unsigned char *key, |
216 |
size_t length, |
|
217 |
HASH_SEARCH_STATE *current_record) |
|
1
by brian
clean slate |
218 |
{
|
219 |
HASH_LINK *pos; |
|
482
by Brian Aker
Remove uint. |
220 |
uint32_t idx; |
1
by brian
clean slate |
221 |
|
222 |
if (*current_record != NO_RECORD) |
|
223 |
{
|
|
224 |
HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*); |
|
225 |
for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next) |
|
226 |
{
|
|
227 |
pos=data+idx; |
|
228 |
if (!hashcmp(hash,pos,key,length)) |
|
229 |
{
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
230 |
*current_record= idx; |
231 |
return pos->data; |
|
1
by brian
clean slate |
232 |
}
|
233 |
}
|
|
234 |
*current_record= NO_RECORD; |
|
235 |
}
|
|
236 |
return 0; |
|
237 |
}
|
|
238 |
||
239 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
240 |
/* Change link from pos to new_link */
|
1
by brian
clean slate |
241 |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
242 |
static void movelink(HASH_LINK *array, uint32_t find, |
243 |
uint32_t next_link, uint32_t newlink) |
|
1
by brian
clean slate |
244 |
{
|
245 |
HASH_LINK *old_link; |
|
246 |
do
|
|
247 |
{
|
|
248 |
old_link=array+next_link; |
|
249 |
}
|
|
250 |
while ((next_link=old_link->next) != find); |
|
251 |
old_link->next= newlink; |
|
252 |
return; |
|
253 |
}
|
|
254 |
||
255 |
/*
|
|
256 |
Compare a key in a record to a whole key. Return 0 if identical
|
|
257 |
||
258 |
SYNOPSIS
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
259 |
hashcmp()
|
260 |
hash hash table
|
|
261 |
pos position of hash record to use in comparison
|
|
262 |
key key for comparison
|
|
263 |
length length of key
|
|
1
by brian
clean slate |
264 |
|
265 |
NOTES:
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
266 |
If length is 0, comparison is done using the length of the
|
267 |
record being compared against.
|
|
1
by brian
clean slate |
268 |
|
269 |
RETURN
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
270 |
= 0 key of record == key
|
271 |
!= 0 key of record != key
|
|
272 |
*/
|
|
1
by brian
clean slate |
273 |
|
481
by Brian Aker
Remove all of uchar. |
274 |
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key, |
1
by brian
clean slate |
275 |
size_t length) |
276 |
{
|
|
277 |
size_t rec_keylength; |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
278 |
unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data, |
279 |
&rec_keylength,1); |
|
1
by brian
clean slate |
280 |
return ((length && length != rec_keylength) || |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
281 |
my_strnncoll(hash->charset, rec_key, rec_keylength, |
282 |
key, rec_keylength)); |
|
1
by brian
clean slate |
283 |
}
|
284 |
||
285 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
286 |
/* Write a hash-key to the hash-index */
|
1
by brian
clean slate |
287 |
|
481
by Brian Aker
Remove all of uchar. |
288 |
bool my_hash_insert(HASH *info,const unsigned char *record) |
1
by brian
clean slate |
289 |
{
|
290 |
int flag; |
|
291 |
size_t idx; |
|
482
by Brian Aker
Remove uint. |
292 |
uint32_t halfbuff,hash_nr,first_index; |
481
by Brian Aker
Remove all of uchar. |
293 |
unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL; |
77.1.71
by Monty Taylor
Uninitialized use. |
294 |
HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos; |
1
by brian
clean slate |
295 |
|
296 |
if (HASH_UNIQUE & info->flags) |
|
297 |
{
|
|
481
by Brian Aker
Remove all of uchar. |
298 |
unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1); |
1
by brian
clean slate |
299 |
if (hash_search(info, key, idx)) |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
300 |
/* Duplicate entry */
|
301 |
return(true); |
|
1
by brian
clean slate |
302 |
}
|
303 |
||
304 |
flag=0; |
|
305 |
if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array))) |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
306 |
/* No more memory */
|
307 |
return(true); |
|
1
by brian
clean slate |
308 |
|
309 |
data=dynamic_element(&info->array,0,HASH_LINK*); |
|
1138
by Brian Aker
Merge of Joe Daly's work |
310 |
halfbuff= info->blength >> 1; |
1
by brian
clean slate |
311 |
|
1138
by Brian Aker
Merge of Joe Daly's work |
312 |
idx= first_index= info->records-halfbuff; |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
313 |
/* If some records */
|
314 |
if (idx != info->records) |
|
1
by brian
clean slate |
315 |
{
|
316 |
do
|
|
317 |
{
|
|
318 |
pos=data+idx; |
|
319 |
hash_nr=rec_hashnr(info,pos->data); |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
320 |
/* First loop; Check if ok */
|
321 |
if (flag == 0) |
|
1138
by Brian Aker
Merge of Joe Daly's work |
322 |
if (hash_mask(hash_nr,info->blength,info->records) != first_index) |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
323 |
break; |
1
by brian
clean slate |
324 |
if (!(hash_nr & halfbuff)) |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
325 |
{
|
326 |
/* Key will not move */
|
|
327 |
if (!(flag & LOWFIND)) |
|
328 |
{
|
|
329 |
if (flag & HIGHFIND) |
|
330 |
{
|
|
331 |
flag=LOWFIND | HIGHFIND; |
|
332 |
/* key shall be moved to the current empty position */
|
|
333 |
gpos=empty; |
|
334 |
ptr_to_rec=pos->data; |
|
335 |
/* This place is now free */
|
|
336 |
empty=pos; |
|
337 |
}
|
|
338 |
else
|
|
339 |
{
|
|
340 |
/* key isn't changed */
|
|
341 |
flag=LOWFIND | LOWUSED; |
|
342 |
gpos=pos; |
|
343 |
ptr_to_rec=pos->data; |
|
344 |
}
|
|
345 |
}
|
|
346 |
else
|
|
347 |
{
|
|
348 |
if (!(flag & LOWUSED)) |
|
349 |
{
|
|
350 |
/* Change link of previous LOW-key */
|
|
351 |
gpos->data=ptr_to_rec; |
|
895
by Brian Aker
Completion (?) of uint conversion. |
352 |
gpos->next= (uint32_t) (pos-data); |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
353 |
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED); |
354 |
}
|
|
355 |
gpos=pos; |
|
356 |
ptr_to_rec=pos->data; |
|
357 |
}
|
|
1
by brian
clean slate |
358 |
}
|
359 |
else
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
360 |
{
|
361 |
/* key will be moved */
|
|
362 |
if (!(flag & HIGHFIND)) |
|
363 |
{
|
|
364 |
flag= (flag & LOWFIND) | HIGHFIND; |
|
365 |
/* key shall be moved to the last (empty) position */
|
|
366 |
gpos2 = empty; empty=pos; |
|
367 |
ptr_to_rec2=pos->data; |
|
368 |
}
|
|
369 |
else
|
|
370 |
{
|
|
371 |
if (!(flag & HIGHUSED)) |
|
372 |
{
|
|
373 |
/* Change link of previous hash-key and save */
|
|
374 |
gpos2->data=ptr_to_rec2; |
|
895
by Brian Aker
Completion (?) of uint conversion. |
375 |
gpos2->next=(uint32_t) (pos-data); |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
376 |
flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED); |
377 |
}
|
|
378 |
gpos2=pos; |
|
379 |
ptr_to_rec2=pos->data; |
|
380 |
}
|
|
1
by brian
clean slate |
381 |
}
|
382 |
}
|
|
383 |
while ((idx=pos->next) != NO_RECORD); |
|
384 |
||
385 |
if ((flag & (LOWFIND | LOWUSED)) == LOWFIND) |
|
386 |
{
|
|
387 |
gpos->data=ptr_to_rec; |
|
388 |
gpos->next=NO_RECORD; |
|
389 |
}
|
|
390 |
if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND) |
|
391 |
{
|
|
392 |
gpos2->data=ptr_to_rec2; |
|
393 |
gpos2->next=NO_RECORD; |
|
394 |
}
|
|
395 |
}
|
|
396 |
/* Check if we are at the empty position */
|
|
397 |
||
1138
by Brian Aker
Merge of Joe Daly's work |
398 |
idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1); |
1
by brian
clean slate |
399 |
pos=data+idx; |
400 |
if (pos == empty) |
|
401 |
{
|
|
481
by Brian Aker
Remove all of uchar. |
402 |
pos->data=(unsigned char*) record; |
1
by brian
clean slate |
403 |
pos->next=NO_RECORD; |
404 |
}
|
|
405 |
else
|
|
406 |
{
|
|
407 |
/* Check if more records in same hash-nr family */
|
|
408 |
empty[0]=pos[0]; |
|
1138
by Brian Aker
Merge of Joe Daly's work |
409 |
gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1); |
1
by brian
clean slate |
410 |
if (pos == gpos) |
411 |
{
|
|
481
by Brian Aker
Remove all of uchar. |
412 |
pos->data=(unsigned char*) record; |
895
by Brian Aker
Completion (?) of uint conversion. |
413 |
pos->next=(uint32_t) (empty - data); |
1
by brian
clean slate |
414 |
}
|
415 |
else
|
|
416 |
{
|
|
481
by Brian Aker
Remove all of uchar. |
417 |
pos->data=(unsigned char*) record; |
1
by brian
clean slate |
418 |
pos->next=NO_RECORD; |
895
by Brian Aker
Completion (?) of uint conversion. |
419 |
movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data)); |
1
by brian
clean slate |
420 |
}
|
421 |
}
|
|
422 |
if (++info->records == info->blength) |
|
423 |
info->blength+= info->blength; |
|
424 |
return(0); |
|
425 |
}
|
|
426 |
||
427 |
||
428 |
/******************************************************************************
|
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
429 |
** Remove one record from hash-table. The record with the same record
|
430 |
** ptr is removed.
|
|
431 |
** if there is a free-function it's called for record if found
|
|
432 |
*****************************************************************************/
|
|
1
by brian
clean slate |
433 |
|
481
by Brian Aker
Remove all of uchar. |
434 |
bool hash_delete(HASH *hash,unsigned char *record) |
1
by brian
clean slate |
435 |
{
|
482
by Brian Aker
Remove uint. |
436 |
uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index; |
1
by brian
clean slate |
437 |
HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty; |
438 |
if (!hash->records) |
|
51.3.13
by Jay Pipes
Phase 1 removal of DBUG in mysys |
439 |
return(1); |
1
by brian
clean slate |
440 |
|
1138
by Brian Aker
Merge of Joe Daly's work |
441 |
blength=hash->blength; |
1
by brian
clean slate |
442 |
data=dynamic_element(&hash->array,0,HASH_LINK*); |
443 |
/* Search after record with key */
|
|
444 |
pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records); |
|
445 |
gpos = 0; |
|
446 |
||
447 |
while (pos->data != record) |
|
448 |
{
|
|
449 |
gpos=pos; |
|
450 |
if (pos->next == NO_RECORD) |
|
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
451 |
/* Key not found */
|
452 |
return(1); |
|
453 |
||
1
by brian
clean slate |
454 |
pos=data+pos->next; |
455 |
}
|
|
456 |
||
457 |
if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1; |
|
458 |
lastpos=data+hash->records; |
|
459 |
||
460 |
/* Remove link to record */
|
|
895
by Brian Aker
Completion (?) of uint conversion. |
461 |
empty=pos; empty_index=(uint32_t) (empty-data); |
1
by brian
clean slate |
462 |
if (gpos) |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
463 |
/* unlink current ptr */
|
464 |
gpos->next=pos->next; |
|
1
by brian
clean slate |
465 |
else if (pos->next != NO_RECORD) |
466 |
{
|
|
467 |
empty=data+(empty_index=pos->next); |
|
468 |
pos->data=empty->data; |
|
469 |
pos->next=empty->next; |
|
470 |
}
|
|
471 |
||
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
472 |
/* last key at wrong pos or no next link */
|
473 |
if (empty == lastpos) |
|
1
by brian
clean slate |
474 |
goto exit; |
475 |
||
476 |
/* Move the last key (lastpos) */
|
|
477 |
lastpos_hashnr=rec_hashnr(hash,lastpos->data); |
|
478 |
/* pos is where lastpos should be */
|
|
1138
by Brian Aker
Merge of Joe Daly's work |
479 |
pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records); |
520.7.1
by Monty Taylor
Moved hash.c to drizzled. |
480 |
/* Move to empty position. */
|
481 |
if (pos == empty) |
|
1
by brian
clean slate |
482 |
{
|
483 |
empty[0]=lastpos[0]; |
|
484 |
goto exit; |
|
485 |
}
|
|
486 |
pos_hashnr=rec_hashnr(hash,pos->data); |
|
487 |
/* pos3 is where the pos should be */
|
|
1138
by Brian Aker
Merge of Joe Daly's work |
488 |
pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records); |
1
by brian
clean slate |
489 |
if (pos != pos3) |
490 |
{ /* pos is on wrong posit */ |
|
491 |
empty[0]=pos[0]; /* Save it here */ |
|
492 |
pos[0]=lastpos[0]; /* This should be here */ |
|
895
by Brian Aker
Completion (?) of uint conversion. |
493 |
movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index); |
1
by brian
clean slate |
494 |
goto exit; |
495 |
}
|
|
496 |
pos2= hash_mask(lastpos_hashnr,blength,hash->records+1); |
|
497 |
if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1)) |
|
498 |
{ /* Identical key-positions */ |
|
499 |
if (pos2 != hash->records) |
|
500 |
{
|
|
501 |
empty[0]=lastpos[0]; |
|
895
by Brian Aker
Completion (?) of uint conversion. |
502 |
movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index); |
1
by brian
clean slate |
503 |
goto exit; |
504 |
}
|
|
895
by Brian Aker
Completion (?) of uint conversion. |
505 |
idx= (uint32_t) (pos-data); /* Link pos->next after lastpos */ |
1
by brian
clean slate |
506 |
}
|
507 |
else idx= NO_RECORD; /* Different positions merge */ |
|
508 |
||
509 |
empty[0]=lastpos[0]; |
|
510 |
movelink(data,idx,empty_index,pos->next); |
|
511 |
pos->next=empty_index; |
|
512 |
||
513 |
exit: |
|
398.1.10
by Monty Taylor
Actually removed VOID() this time. |
514 |
pop_dynamic(&hash->array); |
1
by brian
clean slate |
515 |
if (hash->free) |
481
by Brian Aker
Remove all of uchar. |
516 |
(*hash->free)((unsigned char*) record); |
51.3.13
by Jay Pipes
Phase 1 removal of DBUG in mysys |
517 |
return(0); |
1
by brian
clean slate |
518 |
}
|
519 |
||
481
by Brian Aker
Remove all of uchar. |
520 |
unsigned char *hash_element(HASH *hash,uint32_t idx) |
1
by brian
clean slate |
521 |
{
|
522 |
if (idx < hash->records) |
|
523 |
return dynamic_element(&hash->array,idx,HASH_LINK*)->data; |
|
524 |
return 0; |
|
525 |
}
|
|
526 |
||
1280.1.10
by Monty Taylor
Put everything in drizzled into drizzled namespace. |
527 |
} /* namespace drizzled */ |