← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

Removed DBUG symbols and fixed TRUE/FALSE

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/hash.c
18
18
/* Key length of 0 isn't allowed */
19
19
 
20
20
#include "mysys_priv.h"
21
 
#include <mystrings/m_string.h>
22
 
#include <mystrings/m_ctype.h>
 
21
#include <m_string.h>
 
22
#include <m_ctype.h>
23
23
#include "hash.h"
24
24
 
25
25
#define NO_RECORD       ((uint) -1)
29
29
#define HIGHUSED 8
30
30
 
31
31
typedef struct st_hash_info {
32
 
  uint32_t next;                                        /* index to next key */
33
 
  unsigned char *data;                                  /* data for current entry */
 
32
  uint next;                                    /* index to next key */
 
33
  uchar *data;                                  /* data for current entry */
34
34
} HASH_LINK;
35
35
 
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);
38
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
 
36
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength);
 
37
static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink);
 
38
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
39
39
                   size_t length);
40
40
 
41
 
static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length)
 
41
static uint calc_hash(const HASH *hash, const uchar *key, size_t length)
42
42
{
43
 
  uint32_t nr1=1, nr2=4;
44
 
  hash->charset->coll->hash_sort(hash->charset,(const unsigned char*) key,length,&nr1,&nr2);
 
43
  ulong nr1=1, nr2=4;
 
44
  hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);
45
45
  return nr1;
46
46
}
47
47
 
48
 
bool
49
 
_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,
 
48
my_bool
 
49
_hash_init(HASH *hash,uint growth_size, CHARSET_INFO *charset,
 
50
           ulong size, size_t key_offset, size_t key_length,
51
51
           hash_get_key get_key,
52
 
           void (*free_element)(void*),uint32_t flags CALLER_INFO_PROTO)
 
52
           void (*free_element)(void*),uint flags CALLER_INFO_PROTO)
53
53
{
 
54
  DBUG_ENTER("hash_init");
 
55
  DBUG_PRINT("enter",("hash: 0x%lx  size: %u", (long) hash, (uint) size));
 
56
 
54
57
  hash->records=0;
55
58
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
56
59
                               growth_size))
57
60
  {
58
61
    hash->free=0;                               /* Allow call to hash_free */
59
 
    return true;
 
62
    DBUG_RETURN(1);
60
63
  }
61
64
  hash->key_offset=key_offset;
62
65
  hash->key_length=key_length;
65
68
  hash->free=free_element;
66
69
  hash->flags=flags;
67
70
  hash->charset=charset;
68
 
  return false;
 
71
  DBUG_RETURN(0);
69
72
}
70
73
 
71
74
 
105
108
 
106
109
void hash_free(HASH *hash)
107
110
{
 
111
  DBUG_ENTER("hash_free");
 
112
  DBUG_PRINT("enter",("hash: 0x%lx", (long) hash));
 
113
 
108
114
  hash_free_elements(hash);
109
115
  hash->free= 0;
110
116
  delete_dynamic(&hash->array);
111
 
  return;
 
117
  DBUG_VOID_RETURN;
112
118
}
113
119
 
114
120
 
122
128
 
123
129
void my_hash_reset(HASH *hash)
124
130
{
 
131
  DBUG_ENTER("my_hash_reset");
 
132
  DBUG_PRINT("enter",("hash: 0x%lxd", (long) hash));
 
133
 
125
134
  hash_free_elements(hash);
126
135
  reset_dynamic(&hash->array);
127
136
  /* Set row pointers so that the hash can be reused at once */
128
137
  hash->blength= 1;
129
 
  return;
 
138
  DBUG_VOID_RETURN;
130
139
}
131
140
 
132
141
/* some helper functions */
133
142
 
134
143
/*
135
 
  This function is char* instead of unsigned char* as HPUX11 compiler can't
 
144
  This function is char* instead of uchar* as HPUX11 compiler can't
136
145
  handle inline functions that are not defined as native types
137
146
*/
138
147
 
139
148
static inline char*
140
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
141
 
         bool first)
 
149
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
150
         my_bool first)
142
151
{
143
152
  if (hash->get_key)
144
153
    return (char*) (*hash->get_key)(record,length,first);
148
157
 
149
158
        /* Calculate pos according to keys */
150
159
 
151
 
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
 
160
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
152
161
{
153
162
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
154
163
  return (hashnr & ((buffmax >> 1) -1));
155
164
}
156
165
 
157
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
158
 
                          uint32_t buffmax, uint32_t maxlength)
 
166
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
167
                          uint buffmax, uint maxlength)
159
168
{
160
169
  size_t length;
161
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
170
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
162
171
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
163
172
}
164
173
 
169
178
#if !defined(__USLC__) && !defined(__sgi)
170
179
inline
171
180
#endif
172
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
181
unsigned int rec_hashnr(HASH *hash,const uchar *record)
173
182
{
174
183
  size_t length;
175
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
184
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
176
185
  return calc_hash(hash,key,length);
177
186
}
178
187
 
179
188
 
180
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key, size_t length)
 
189
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
181
190
{
182
191
  HASH_SEARCH_STATE state;
183
192
  return hash_first(hash, key, length, &state);
190
199
   Assigns the number of the found record to HASH_SEARCH_STATE state
191
200
*/
192
201
 
193
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key, size_t length,
 
202
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
194
203
                HASH_SEARCH_STATE *current_record)
195
204
{
196
205
  HASH_LINK *pos;
197
 
  uint32_t flag,idx;
 
206
  uint flag,idx;
 
207
  DBUG_ENTER("hash_first");
198
208
 
199
209
  flag=1;
200
210
  if (hash->records)
206
216
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
207
217
      if (!hashcmp(hash,pos,key,length))
208
218
      {
 
219
        DBUG_PRINT("exit",("found key at %d",idx));
209
220
        *current_record= idx;
210
 
        return (pos->data);
 
221
        DBUG_RETURN (pos->data);
211
222
      }
212
223
      if (flag)
213
224
      {
219
230
    while ((idx=pos->next) != NO_RECORD);
220
231
  }
221
232
  *current_record= NO_RECORD;
222
 
  return(0);
 
233
  DBUG_RETURN(0);
223
234
}
224
235
 
225
236
        /* Get next record with identical key */
226
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,
 
239
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
229
240
               HASH_SEARCH_STATE *current_record)
230
241
{
231
242
  HASH_LINK *pos;
232
 
  uint32_t idx;
 
243
  uint idx;
233
244
 
234
245
  if (*current_record != NO_RECORD)
235
246
  {
251
262
 
252
263
        /* Change link from pos to new_link */
253
264
 
254
 
static void movelink(HASH_LINK *array,uint32_t find,uint32_t next_link,uint32_t newlink)
 
265
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
255
266
{
256
267
  HASH_LINK *old_link;
257
268
  do
282
293
    != 0 key of record != key
283
294
 */
284
295
 
285
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
 
296
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
286
297
                   size_t length)
287
298
{
288
299
  size_t rec_keylength;
289
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash,pos->data,&rec_keylength,1);
 
300
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
290
301
  return ((length && length != rec_keylength) ||
291
 
          my_strnncoll(hash->charset, (const unsigned char*) rec_key, rec_keylength,
292
 
                       (const unsigned char*) key, rec_keylength));
 
302
          my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,
 
303
                       (uchar*) key, rec_keylength));
293
304
}
294
305
 
295
306
 
296
307
        /* Write a hash-key to the hash-index */
297
308
 
298
 
bool my_hash_insert(HASH *info,const unsigned char *record)
 
309
my_bool my_hash_insert(HASH *info,const uchar *record)
299
310
{
300
311
  int flag;
301
312
  size_t idx;
302
 
  uint32_t halfbuff,hash_nr,first_index;
303
 
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
304
 
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
 
313
  uint halfbuff,hash_nr,first_index;
 
314
  uchar *ptr_to_rec,*ptr_to_rec2;
 
315
  HASH_LINK *data,*empty,*gpos,*gpos2,*pos;
305
316
 
306
317
  if (HASH_UNIQUE & info->flags)
307
318
  {
308
 
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
 
319
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
309
320
    if (hash_search(info, key, idx))
310
 
      return(true);                             /* Duplicate entry */
 
321
      return(TRUE);                             /* Duplicate entry */
311
322
  }
312
323
 
313
324
  flag=0;
314
325
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
315
 
    return(true);                               /* No more memory */
 
326
    return(TRUE);                               /* No more memory */
316
327
 
317
328
  data=dynamic_element(&info->array,0,HASH_LINK*);
318
329
  halfbuff= info->blength >> 1;
401
412
  pos=data+idx;
402
413
  if (pos == empty)
403
414
  {
404
 
    pos->data=(unsigned char*) record;
 
415
    pos->data=(uchar*) record;
405
416
    pos->next=NO_RECORD;
406
417
  }
407
418
  else
411
422
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
412
423
    if (pos == gpos)
413
424
    {
414
 
      pos->data=(unsigned char*) record;
 
425
      pos->data=(uchar*) record;
415
426
      pos->next=(uint) (empty - data);
416
427
    }
417
428
    else
418
429
    {
419
 
      pos->data=(unsigned char*) record;
 
430
      pos->data=(uchar*) record;
420
431
      pos->next=NO_RECORD;
421
432
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
422
433
    }
433
444
** if there is a free-function it's called for record if found
434
445
******************************************************************************/
435
446
 
436
 
bool hash_delete(HASH *hash,unsigned char *record)
 
447
my_bool hash_delete(HASH *hash,uchar *record)
437
448
{
438
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
449
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
439
450
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
 
451
  DBUG_ENTER("hash_delete");
440
452
  if (!hash->records)
441
 
    return(1);
 
453
    DBUG_RETURN(1);
442
454
 
443
455
  blength=hash->blength;
444
456
  data=dynamic_element(&hash->array,0,HASH_LINK*);
450
462
  {
451
463
    gpos=pos;
452
464
    if (pos->next == NO_RECORD)
453
 
      return(1);                        /* Key not found */
 
465
      DBUG_RETURN(1);                   /* Key not found */
454
466
    pos=data+pos->next;
455
467
  }
456
468
 
508
520
  pos->next=empty_index;
509
521
 
510
522
exit:
511
 
  pop_dynamic(&hash->array);
 
523
  VOID(pop_dynamic(&hash->array));
512
524
  if (hash->free)
513
 
    (*hash->free)((unsigned char*) record);
514
 
  return(0);
 
525
    (*hash->free)((uchar*) record);
 
526
  DBUG_RETURN(0);
515
527
}
516
528
 
517
529
        /*
519
531
          This is much more efficent than using a delete & insert.
520
532
          */
521
533
 
522
 
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
 
534
my_bool hash_update(HASH *hash, uchar *record, uchar *old_key,
523
535
                    size_t old_key_length)
524
536
{
525
 
  uint32_t new_index,new_pos_index,blength,records,empty;
 
537
  uint new_index,new_pos_index,blength,records,empty;
526
538
  size_t idx;
527
539
  HASH_LINK org_link,*data,*previous,*pos;
 
540
  DBUG_ENTER("hash_update");
528
541
  
529
542
  if (HASH_UNIQUE & hash->flags)
530
543
  {
531
544
    HASH_SEARCH_STATE state;
532
 
    unsigned char *found, *new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
 
545
    uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);
533
546
    if ((found= hash_first(hash, new_key, idx, &state)))
534
547
    {
535
548
      do 
536
549
      {
537
550
        if (found != record)
538
 
          return(1);            /* Duplicate entry */
 
551
          DBUG_RETURN(1);               /* Duplicate entry */
539
552
      } 
540
553
      while ((found= hash_next(hash, new_key, idx, &state)));
541
554
    }
552
565
                  blength,records);
553
566
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
554
567
  if (idx == new_index)
555
 
    return(0);                  /* Nothing to do (No record check) */
 
568
    DBUG_RETURN(0);                     /* Nothing to do (No record check) */
556
569
  previous=0;
557
570
  for (;;)
558
571
  {
561
574
      break;
562
575
    previous=pos;
563
576
    if ((idx=pos->next) == NO_RECORD)
564
 
      return(1);                        /* Not found in links */
 
577
      DBUG_RETURN(1);                   /* Not found in links */
565
578
  }
566
579
  org_link= *pos;
567
580
  empty=idx;
597
610
      data[empty]= org_link;
598
611
    }
599
612
    data[empty].next= NO_RECORD;
600
 
    return(0);
 
613
    DBUG_RETURN(0);
601
614
  }
602
615
  pos=data+new_index;
603
616
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
614
627
    data[empty]=org_link;
615
628
    data[new_index].next=empty;
616
629
  }
617
 
  return(0);
 
630
  DBUG_RETURN(0);
618
631
}
619
632
 
620
633
 
621
 
unsigned char *hash_element(HASH *hash,uint32_t idx)
 
634
uchar *hash_element(HASH *hash,ulong idx)
622
635
{
623
636
  if (idx < hash->records)
624
637
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
631
644
  isn't changed
632
645
*/
633
646
 
634
 
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, unsigned char *new_row)
 
647
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)
635
648
{
636
649
  if (*current_record != NO_RECORD)            /* Safety */
637
650
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
638
651
}
 
652
 
 
653
 
 
654
#ifndef DBUG_OFF
 
655
 
 
656
my_bool hash_check(HASH *hash)
 
657
{
 
658
  int error;
 
659
  uint i,rec_link,found,max_links,seek,links,idx;
 
660
  uint records,blength;
 
661
  HASH_LINK *data,*hash_info;
 
662
 
 
663
  records=hash->records; blength=hash->blength;
 
664
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
665
  error=0;
 
666
 
 
667
  for (i=found=max_links=seek=0 ; i < records ; i++)
 
668
  {
 
669
    if (hash_rec_mask(hash,data+i,blength,records) == i)
 
670
    {
 
671
      found++; seek++; links=1;
 
672
      for (idx=data[i].next ;
 
673
           idx != NO_RECORD && found < records + 1;
 
674
           idx=hash_info->next)
 
675
      {
 
676
        if (idx >= records)
 
677
        {
 
678
          DBUG_PRINT("error",
 
679
                     ("Found pointer outside array to %d from link starting at %d",
 
680
                      idx,i));
 
681
          error=1;
 
682
        }
 
683
        hash_info=data+idx;
 
684
        seek+= ++links;
 
685
        if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i)
 
686
        {
 
687
          DBUG_PRINT("error",
 
688
                     ("Record in wrong link at %d: Start %d  Record: 0x%lx  Record-link %d",
 
689
                      idx, i, (long) hash_info->data, rec_link));
 
690
          error=1;
 
691
        }
 
692
        else
 
693
          found++;
 
694
      }
 
695
      if (links > max_links) max_links=links;
 
696
    }
 
697
  }
 
698
  if (found != records)
 
699
  {
 
700
    DBUG_PRINT("error",("Found %u of %u records", found, records));
 
701
    error=1;
 
702
  }
 
703
  if (records)
 
704
    DBUG_PRINT("info",
 
705
               ("records: %u   seeks: %d   max links: %d   hitrate: %.2f",
 
706
                records,seek,max_links,(float) seek / (float) records));
 
707
  return error;
 
708
}
 
709
#endif