« back to all changes in this revision
Viewing changes to drizzled/hash.cc
- browse files at revision 520.4.33
- compare with another revision
- compare with revision 1219
- download diff
- download tarball
- view history from revision 520.4.33
- Committer: Monty Taylor
- Date: 2008-10-30 05:54:51 UTC
- mfrom: (520.7.1 fix-headers)
- mto: (520.4.35 devel) (572.1.1 devel) (575.1.1 devel)
- mto: This revision was merged to the branch mainline in revision 572.
- Revision ID: monty@inaugust.com-20081030055451-og38p1taojwzm78o
Merged from fix-headers.
- files renamed:
- mysys/hash.c => drizzled/hash.cc
- mysys/hash.h => drizzled/hash.h
- files modified:
- client/drizzledump.cc
added
removed
drizzled/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
/* The hash functions used for saveing keys */
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
*
4
* Copyright (C) 2008 Sun Microsystems
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 */
17
21
/* One of key_length or key_length_offset must be given */
18
22
/* Key length of 0 isn't allowed */
19
23
20
#include "mysys_priv.h"
21
#include <mystrings/m_string.h>
22
#include <mystrings/m_ctype.h>
23
#include "hash.h"
24
25
#define NO_RECORD ((uint) -1)
26
#define LOWFIND 1
27
#define LOWUSED 2
28
#define HIGHFIND 4
29
#define HIGHUSED 8
24
#include <config.h>
25
#include <drizzled/definitions.h>
26
#include <drizzled/hash.h>
27
28
const uint32_t NO_RECORD= UINT32_MAX;
29
30
const int LOWFIND= 1;
31
const int LOWUSED= 2;
32
const int HIGHFIND= 4;
33
const int HIGHUSED= 8;
30
34
31
35
typedef struct st_hash_info {
32
uint32_t next; /* index to next key */
33
unsigned char *data; /* data for current entry */
36
/* index to next key */
37
uint32_t next;
38
/* data for current entry */
39
unsigned char *data;
34
40
} HASH_LINK;
35
41
36
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength);
37
static void movelink(HASH_LINK *array,uint32_t pos,uint32_t next_link,uint32_t newlink);
42
static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax,
43
uint32_t maxlength);
44
static void movelink(HASH_LINK *array, uint32_t pos,
45
uint32_t next_link, uint32_t newlink);
38
46
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
39
47
size_t length);
40
48
41
static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length)
49
static uint32_t calc_hash(const HASH *hash, const unsigned char *key,
50
size_t length)
42
51
{
43
52
uint32_t nr1=1, nr2=4;
44
hash->charset->coll->hash_sort(hash->charset,(const unsigned char*) key,length,&nr1,&nr2);
53
hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
45
54
return nr1;
46
55
}
47
56
48
57
bool
49
58
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
50
uint32_t size, size_t key_offset, size_t key_length,
51
hash_get_key get_key,
52
void (*free_element)(void*),uint32_t flags CALLER_INFO_PROTO)
59
uint32_t size, size_t key_offset, size_t key_length,
60
hash_get_key get_key,
61
void (*free_element)(void*),uint32_t flags CALLER_INFO_PROTO)
53
62
{
54
63
hash->records=0;
55
64
if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
56
65
growth_size))
57
66
{
58
hash->free=0; /* Allow call to hash_free */
67
/* Allow call to hash_free */
68
hash->free=0;
59
69
return true;
60
70
}
61
71
hash->key_offset=key_offset;
73
83
Call hash->free on all elements in hash.
74
84
75
85
SYNOPSIS
76
hash_free_elements()
77
hash hash table
86
hash_free_elements()
87
hash hash table
78
88
79
89
NOTES:
80
Sets records to 0
90
Sets records to 0
81
91
*/
82
92
83
93
static inline void hash_free_elements(HASH *hash)
97
107
Free memory used by hash.
98
108
99
109
SYNOPSIS
100
hash_free()
101
hash the hash to delete elements of
110
hash_free()
111
hash the hash to delete elements of
102
112
103
113
NOTES: Hash can't be reused without calling hash_init again.
104
114
*/
116
126
Delete all elements from the hash (the hash itself is to be reused).
117
127
118
128
SYNOPSIS
119
my_hash_reset()
120
hash the hash to delete elements of
129
my_hash_reset()
130
hash the hash to delete elements of
121
131
*/
122
132
123
133
void my_hash_reset(HASH *hash)
146
156
return (char*) record+hash->key_offset;
147
157
}
148
158
149
/* Calculate pos according to keys */
159
/* Calculate pos according to keys */
150
160
151
161
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
152
162
{
155
165
}
156
166
157
167
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
158
uint32_t buffmax, uint32_t maxlength)
168
uint32_t buffmax, uint32_t maxlength)
159
169
{
160
170
size_t length;
161
171
unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
164
174
165
175
166
176
167
/* for compilers which can not handle inline */
168
177
static
169
#if !defined(__USLC__) && !defined(__sgi)
170
178
inline
171
#endif
172
179
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
173
180
{
174
181
size_t length;
177
184
}
178
185
179
186
180
unsigned char* hash_search(const HASH *hash, const unsigned char *key, size_t length)
187
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
188
size_t length)
181
189
{
182
190
HASH_SEARCH_STATE state;
183
191
return hash_first(hash, key, length, &state);
187
195
Search after a record based on a key
188
196
189
197
NOTE
190
Assigns the number of the found record to HASH_SEARCH_STATE state
198
Assigns the number of the found record to HASH_SEARCH_STATE state
191
199
*/
192
200
193
unsigned char* hash_first(const HASH *hash, const unsigned char *key, size_t length,
194
HASH_SEARCH_STATE *current_record)
201
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
202
size_t length,
203
HASH_SEARCH_STATE *current_record)
195
204
{
196
205
HASH_LINK *pos;
197
206
uint32_t flag,idx;
200
209
if (hash->records)
201
210
{
202
211
idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
203
hash->blength,hash->records);
212
hash->blength,hash->records);
204
213
do
205
214
{
206
215
pos= dynamic_element(&hash->array,idx,HASH_LINK*);
207
216
if (!hashcmp(hash,pos,key,length))
208
217
{
209
*current_record= idx;
210
return (pos->data);
218
*current_record= idx;
219
return (pos->data);
211
220
}
212
221
if (flag)
213
222
{
214
flag=0; /* Reset flag */
215
if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
216
break; /* Wrong link */
223
/* Reset flag */
224
flag=0;
225
if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
226
/* Wrong link */
227
break;
217
228
}
218
229
}
219
230
while ((idx=pos->next) != NO_RECORD);
222
233
return(0);
223
234
}
224
235
225
/* Get next record with identical key */
226
/* Can only be called if previous calls was hash_search */
236
/* Get next record with identical key */
237
/* Can only be called if previous calls was hash_search */
227
238
228
unsigned char* hash_next(const HASH *hash, const unsigned char *key, size_t length,
229
HASH_SEARCH_STATE *current_record)
239
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
240
size_t length,
241
HASH_SEARCH_STATE *current_record)
230
242
{
231
243
HASH_LINK *pos;
232
244
uint32_t idx;
239
251
pos=data+idx;
240
252
if (!hashcmp(hash,pos,key,length))
241
253
{
242
*current_record= idx;
243
return pos->data;
254
*current_record= idx;
255
return pos->data;
244
256
}
245
257
}
246
258
*current_record= NO_RECORD;
249
261
}
250
262
251
263
252
/* Change link from pos to new_link */
264
/* Change link from pos to new_link */
253
265
254
static void movelink(HASH_LINK *array,uint32_t find,uint32_t next_link,uint32_t newlink)
266
static void movelink(HASH_LINK *array, uint32_t find,
267
uint32_t next_link, uint32_t newlink)
255
268
{
256
269
HASH_LINK *old_link;
257
270
do
267
280
Compare a key in a record to a whole key. Return 0 if identical
268
281
269
282
SYNOPSIS
270
hashcmp()
271
hash hash table
272
pos position of hash record to use in comparison
273
key key for comparison
274
length length of key
283
hashcmp()
284
hash hash table
285
pos position of hash record to use in comparison
286
key key for comparison
287
length length of key
275
288
276
289
NOTES:
277
If length is 0, comparison is done using the length of the
278
record being compared against.
290
If length is 0, comparison is done using the length of the
291
record being compared against.
279
292
280
293
RETURN
281
= 0 key of record == key
282
!= 0 key of record != key
283
*/
294
= 0 key of record == key
295
!= 0 key of record != key
296
*/
284
297
285
298
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
286
299
size_t length)
287
300
{
288
301
size_t rec_keylength;
289
unsigned char *rec_key= (unsigned char*) hash_key(hash,pos->data,&rec_keylength,1);
302
unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
303
&rec_keylength,1);
290
304
return ((length && length != rec_keylength) ||
291
my_strnncoll(hash->charset, (const unsigned char*) rec_key, rec_keylength,
292
(const unsigned char*) key, rec_keylength));
305
my_strnncoll(hash->charset, rec_key, rec_keylength,
306
key, rec_keylength));
293
307
}
294
308
295
309
296
/* Write a hash-key to the hash-index */
310
/* Write a hash-key to the hash-index */
297
311
298
312
bool my_hash_insert(HASH *info,const unsigned char *record)
299
313
{
307
321
{
308
322
unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
309
323
if (hash_search(info, key, idx))
310
return(true); /* Duplicate entry */
324
/* Duplicate entry */
325
return(true);
311
326
}
312
327
313
328
flag=0;
314
329
if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
315
return(true); /* No more memory */
330
/* No more memory */
331
return(true);
316
332
317
333
data=dynamic_element(&info->array,0,HASH_LINK*);
318
334
halfbuff= info->blength >> 1;
319
335
320
336
idx=first_index=info->records-halfbuff;
321
if (idx != info->records) /* If some records */
337
/* If some records */
338
if (idx != info->records)
322
339
{
323
340
do
324
341
{
325
342
pos=data+idx;
326
343
hash_nr=rec_hashnr(info,pos->data);
327
if (flag == 0) /* First loop; Check if ok */
328
if (hash_mask(hash_nr,info->blength,info->records) != first_index)
329
break;
344
/* First loop; Check if ok */
345
if (flag == 0)
346
if (hash_mask(hash_nr,info->blength,info->records) != first_index)
347
break;
330
348
if (!(hash_nr & halfbuff))
331
{ /* Key will not move */
332
if (!(flag & LOWFIND))
333
{
334
if (flag & HIGHFIND)
335
{
336
flag=LOWFIND | HIGHFIND;
337
/* key shall be moved to the current empty position */
338
gpos=empty;
339
ptr_to_rec=pos->data;
340
empty=pos; /* This place is now free */
341
}
342
else
343
{
344
flag=LOWFIND | LOWUSED; /* key isn't changed */
345
gpos=pos;
346
ptr_to_rec=pos->data;
347
}
348
}
349
else
350
{
351
if (!(flag & LOWUSED))
352
{
353
/* Change link of previous LOW-key */
354
gpos->data=ptr_to_rec;
355
gpos->next= (uint) (pos-data);
356
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
357
}
358
gpos=pos;
359
ptr_to_rec=pos->data;
360
}
349
{
350
/* Key will not move */
351
if (!(flag & LOWFIND))
352
{
353
if (flag & HIGHFIND)
354
{
355
flag=LOWFIND | HIGHFIND;
356
/* key shall be moved to the current empty position */
357
gpos=empty;
358
ptr_to_rec=pos->data;
359
/* This place is now free */
360
empty=pos;
361
}
362
else
363
{
364
/* key isn't changed */
365
flag=LOWFIND | LOWUSED;
366
gpos=pos;
367
ptr_to_rec=pos->data;
368
}
369
}
370
else
371
{
372
if (!(flag & LOWUSED))
373
{
374
/* Change link of previous LOW-key */
375
gpos->data=ptr_to_rec;
376
gpos->next= (uint) (pos-data);
377
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
378
}
379
gpos=pos;
380
ptr_to_rec=pos->data;
381
}
361
382
}
362
383
else
363
{ /* key will be moved */
364
if (!(flag & HIGHFIND))
365
{
366
flag= (flag & LOWFIND) | HIGHFIND;
367
/* key shall be moved to the last (empty) position */
368
gpos2 = empty; empty=pos;
369
ptr_to_rec2=pos->data;
370
}
371
else
372
{
373
if (!(flag & HIGHUSED))
374
{
375
/* Change link of previous hash-key and save */
376
gpos2->data=ptr_to_rec2;
377
gpos2->next=(uint) (pos-data);
378
flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
379
}
380
gpos2=pos;
381
ptr_to_rec2=pos->data;
382
}
384
{
385
/* key will be moved */
386
if (!(flag & HIGHFIND))
387
{
388
flag= (flag & LOWFIND) | HIGHFIND;
389
/* key shall be moved to the last (empty) position */
390
gpos2 = empty; empty=pos;
391
ptr_to_rec2=pos->data;
392
}
393
else
394
{
395
if (!(flag & HIGHUSED))
396
{
397
/* Change link of previous hash-key and save */
398
gpos2->data=ptr_to_rec2;
399
gpos2->next=(uint) (pos-data);
400
flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
401
}
402
gpos2=pos;
403
ptr_to_rec2=pos->data;
404
}
383
405
}
384
406
}
385
407
while ((idx=pos->next) != NO_RECORD);
428
450
429
451
430
452
/******************************************************************************
431
** Remove one record from hash-table. The record with the same record
432
** ptr is removed.
433
** if there is a free-function it's called for record if found
434
******************************************************************************/
453
** Remove one record from hash-table. The record with the same record
454
** ptr is removed.
455
** if there is a free-function it's called for record if found
456
*****************************************************************************/
435
457
436
458
bool hash_delete(HASH *hash,unsigned char *record)
437
459
{
450
472
{
451
473
gpos=pos;
452
474
if (pos->next == NO_RECORD)
453
return(1); /* Key not found */
475
/* Key not found */
476
return(1);
477
454
478
pos=data+pos->next;
455
479
}
456
480
460
484
/* Remove link to record */
461
485
empty=pos; empty_index=(uint) (empty-data);
462
486
if (gpos)
463
gpos->next=pos->next; /* unlink current ptr */
487
/* unlink current ptr */
488
gpos->next=pos->next;
464
489
else if (pos->next != NO_RECORD)
465
490
{
466
491
empty=data+(empty_index=pos->next);
468
493
pos->next=empty->next;
469
494
}
470
495
471
if (empty == lastpos) /* last key at wrong pos or no next link */
496
/* last key at wrong pos or no next link */
497
if (empty == lastpos)
472
498
goto exit;
473
499
474
500
/* Move the last key (lastpos) */
475
501
lastpos_hashnr=rec_hashnr(hash,lastpos->data);
476
502
/* pos is where lastpos should be */
477
503
pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
478
if (pos == empty) /* Move to empty position. */
504
/* Move to empty position. */
505
if (pos == empty)
479
506
{
480
507
empty[0]=lastpos[0];
481
508
goto exit;
514
541
return(0);
515
542
}
516
543
517
/*
518
Update keys when record has changed.
519
This is much more efficent than using a delete & insert.
520
*/
544
/*
545
Update keys when record has changed.
546
This is much more efficent than using a delete & insert.
547
*/
521
548
522
549
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
523
size_t old_key_length)
550
size_t old_key_length)
524
551
{
525
552
uint32_t new_index,new_pos_index,blength,records,empty;
526
553
size_t idx;
527
554
HASH_LINK org_link,*data,*previous,*pos;
528
555
529
556
if (HASH_UNIQUE & hash->flags)
530
557
{
531
558
HASH_SEARCH_STATE state;
532
unsigned char *found, *new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
559
unsigned char *found,
560
*new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
561
533
562
if ((found= hash_first(hash, new_key, idx, &state)))
534
563
{
535
do
564
do
536
565
{
537
566
if (found != record)
538
567
return(1); /* Duplicate entry */
539
}
568
}
540
569
while ((found= hash_next(hash, new_key, idx, &state)));
541
570
}
542
571
}
547
576
/* Search after record with key */
548
577
549
578
idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?
550
old_key_length :
551
hash->key_length)),
552
blength,records);
579
old_key_length :
580
hash->key_length)),
581
blength,records);
553
582
new_index=hash_mask(rec_hashnr(hash,record),blength,records);
554
583
if (idx == new_index)
555
584
return(0); /* Nothing to do (No record check) */
631
660
isn't changed
632
661
*/
633
662
634
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, unsigned char *new_row)
663
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record,
664
unsigned char *new_row)
635
665
{
636
666
if (*current_record != NO_RECORD) /* Safety */
637
667
dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
Loggerhead is a web-based interface for Breezy
Version: 2.0.1