← Back to branch summary

~maria-captains/mariadb-native-client/trunk

« back to all changes in this revision

Viewing changes to libmysql/hash.c

  • Committer: ghost
  • Date: 2011-10-10 11:01:17 UTC
  • Revision ID: ghost@work-20111010110117-a2zv9mgwavp0iw0a
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
libmysql/hash.c
 
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
 
2
   
 
3
   This library is free software; you can redistribute it and/or
 
4
   modify it under the terms of the GNU Library General Public
 
5
   License as published by the Free Software Foundation; either
 
6
   version 2 of the License, or (at your option) any later version.
 
7
   
 
8
   This library is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
11
   Library General Public License for more details.
 
12
   
 
13
   You should have received a copy of the GNU Library General Public
 
14
   License along with this library; if not, write to the Free
 
15
   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 
16
   MA 02111-1307, USA */
 
17
 
 
18
/* The hash functions used for saveing keys */
 
19
/* One of key_length or key_length_offset must be given */
 
20
/* Key length of 0 isn't allowed */
 
21
 
 
22
#include "mysys_priv.h"
 
23
#include <m_string.h>
 
24
#include <m_ctype.h>
 
25
#include "hash.h"
 
26
 
 
27
#define NO_RECORD       ((uint) -1)
 
28
#define LOWFIND 1
 
29
#define LOWUSED 2
 
30
#define HIGHFIND 4
 
31
#define HIGHUSED 8
 
32
 
 
33
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength);
 
34
static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink);
 
35
static uint calc_hashnr(const byte *key,uint length);
 
36
static uint calc_hashnr_caseup(const byte *key,uint length);
 
37
static int hashcmp(HASH *hash,HASH_LINK *pos,const byte *key,uint length);
 
38
 
 
39
 
 
40
my_bool _hash_init(HASH *hash,uint size,uint key_offset,uint key_length,
 
41
                  hash_get_key get_key,
 
42
                  void (*free_element)(void*),uint flags CALLER_INFO_PROTO)
 
43
{
 
44
  DBUG_ENTER("hash_init");
 
45
  DBUG_PRINT("enter",("hash: %lx  size: %d",hash,size));
 
46
 
 
47
  hash->records=0;
 
48
  if (my_init_dynamic_array_ci(&hash->array,sizeof(HASH_LINK),size,0))
 
49
  {
 
50
    hash->free=0;                               /* Allow call to hash_free */
 
51
    DBUG_RETURN(TRUE);
 
52
  }
 
53
  hash->key_offset=key_offset;
 
54
  hash->key_length=key_length;
 
55
  hash->blength=1;
 
56
  hash->current_record= NO_RECORD;              /* For the future */
 
57
  hash->get_key=get_key;
 
58
  hash->free=free_element;
 
59
  hash->flags=flags;
 
60
  if (flags & HASH_CASE_INSENSITIVE)
 
61
    hash->calc_hashnr=calc_hashnr_caseup;
 
62
  else
 
63
    hash->calc_hashnr=calc_hashnr;
 
64
  DBUG_RETURN(0);
 
65
}
 
66
 
 
67
 
 
68
void hash_free(HASH *hash)
 
69
{
 
70
  DBUG_ENTER("hash_free");
 
71
  if (hash->free)
 
72
  {
 
73
    uint i,records;
 
74
    HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
 
75
    for (i=0,records=hash->records ; i < records ; i++)
 
76
      (*hash->free)(data[i].data);
 
77
    hash->free=0;
 
78
  }
 
79
  delete_dynamic(&hash->array);
 
80
  hash->records=0;
 
81
  DBUG_VOID_RETURN;
 
82
}
 
83
 
 
84
        /* some helper functions */
 
85
 
 
86
/*
 
87
  This function is char* instead of byte* as HPUX11 compiler can't
 
88
  handle inline functions that are not defined as native types
 
89
*/
 
90
 
 
91
inline char*
 
92
hash_key(HASH *hash,const byte *record,uint *length,my_bool first)
 
93
{
 
94
  if (hash->get_key)
 
95
    return (*hash->get_key)(record,length,first);
 
96
  *length=hash->key_length;
 
97
  return (byte*) record+hash->key_offset;
 
98
}
 
99
 
 
100
        /* Calculate pos according to keys */
 
101
 
 
102
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
 
103
{
 
104
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
 
105
  return (hashnr & ((buffmax >> 1) -1));
 
106
}
 
107
 
 
108
static uint hash_rec_mask(HASH *hash,HASH_LINK *pos,uint buffmax,
 
109
                          uint maxlength)
 
110
{
 
111
  uint length;
 
112
  byte *key= (byte*) hash_key(hash,pos->data,&length,0);
 
113
  return hash_mask((*hash->calc_hashnr)(key,length),buffmax,maxlength);
 
114
}
 
115
 
 
116
#ifndef NEW_HASH_FUNCTION
 
117
 
 
118
        /* Calc hashvalue for a key */
 
119
 
 
120
static uint calc_hashnr(const byte *key,uint length)
 
121
{
 
122
  register uint nr=1, nr2=4;
 
123
  while (length--)
 
124
  {
 
125
    nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);
 
126
    nr2+=3;
 
127
  }
 
128
  return((uint) nr);
 
129
}
 
130
 
 
131
        /* Calc hashvalue for a key, case indepenently */
 
132
 
 
133
static uint calc_hashnr_caseup(const byte *key,uint length)
 
134
{
 
135
  register uint nr=1, nr2=4;
 
136
  while (length--)
 
137
  {
 
138
    nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8);
 
139
    nr2+=3;
 
140
  }
 
141
  return((uint) nr);
 
142
}
 
143
 
 
144
#else
 
145
 
 
146
/*
 
147
 * Fowler/Noll/Vo hash
 
148
 *
 
149
 * The basis of the hash algorithm was taken from an idea sent by email to the
 
150
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 
151
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 
152
 * later improved on their algorithm.
 
153
 *
 
154
 * The magic is in the interesting relationship between the special prime
 
155
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 
156
 *
 
157
 * This hash produces the fewest collisions of any function that we've seen so
 
158
 * far, and works well on both numbers and strings.
 
159
 */
 
160
 
 
161
uint calc_hashnr(const byte *key, uint len)
 
162
{
 
163
  const byte *end=key+len;
 
164
  uint hash;
 
165
  for (hash = 0; key < end; key++)
 
166
  {
 
167
    hash *= 16777619;
 
168
    hash ^= (uint) *(uchar*) key;
 
169
  }
 
170
  return (hash);
 
171
}
 
172
 
 
173
uint calc_hashnr_caseup(const byte *key, uint len)
 
174
{
 
175
  const byte *end=key+len;
 
176
  uint hash;
 
177
  for (hash = 0; key < end; key++)
 
178
  {
 
179
    hash *= 16777619;
 
180
    hash ^= (uint) (uchar) toupper(*key);
 
181
  }
 
182
  return (hash);
 
183
}
 
184
 
 
185
#endif
 
186
 
 
187
 
 
188
#ifndef __SUNPRO_C                              /* SUNPRO can't handle this */
 
189
inline
 
190
#endif
 
191
unsigned int rec_hashnr(HASH *hash,const byte *record)
 
192
{
 
193
  uint length;
 
194
  byte *key= (byte*) hash_key(hash,record,&length,0);
 
195
  return (*hash->calc_hashnr)(key,length);
 
196
}
 
197
 
 
198
 
 
199
        /* Search after a record based on a key */
 
200
        /* Sets info->current_ptr to found record */
 
201
 
 
202
gptr hash_search(HASH *hash,const byte *key,uint length)
 
203
{
 
204
  HASH_LINK *pos;
 
205
  uint flag,idx;
 
206
  DBUG_ENTER("hash_search");
 
207
 
 
208
  flag=1;
 
209
  if (hash->records)
 
210
  {
 
211
    idx=hash_mask((*hash->calc_hashnr)(key,length ? length :
 
212
                                         hash->key_length),
 
213
                    hash->blength,hash->records);
 
214
    do
 
215
    {
 
216
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
 
217
      if (!hashcmp(hash,pos,key,length))
 
218
      {
 
219
        DBUG_PRINT("exit",("found key at %d",idx));
 
220
        hash->current_record= idx;
 
221
        DBUG_RETURN (pos->data);
 
222
      }
 
223
      if (flag)
 
224
      {
 
225
        flag=0;                                 /* Reset flag */
 
226
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
227
          break;                                /* Wrong link */
 
228
      }
 
229
    }
 
230
    while ((idx=pos->next) != NO_RECORD);
 
231
  }
 
232
  hash->current_record= NO_RECORD;
 
233
  DBUG_RETURN(0);
 
234
}
 
235
 
 
236
        /* Get next record with identical key */
 
237
        /* Can only be called if previous calls was hash_search */
 
238
 
 
239
gptr hash_next(HASH *hash,const byte *key,uint length)
 
240
{
 
241
  HASH_LINK *pos;
 
242
  uint idx;
 
243
 
 
244
  if (hash->current_record != NO_RECORD)
 
245
  {
 
246
    HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
 
247
    for (idx=data[hash->current_record].next; idx != NO_RECORD ; idx=pos->next)
 
248
    {
 
249
      pos=data+idx;
 
250
      if (!hashcmp(hash,pos,key,length))
 
251
      {
 
252
        hash->current_record= idx;
 
253
        return pos->data;
 
254
      }
 
255
    }
 
256
    hash->current_record=NO_RECORD;
 
257
  }
 
258
  return 0;
 
259
}
 
260
 
 
261
 
 
262
        /* Change link from pos to new_link */
 
263
 
 
264
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
 
265
{
 
266
  HASH_LINK *old_link;
 
267
  do
 
268
  {
 
269
    old_link=array+next_link;
 
270
  }
 
271
  while ((next_link=old_link->next) != find);
 
272
  old_link->next= newlink;
 
273
  return;
 
274
}
 
275
 
 
276
        /* Compare a key in a record to a whole key. Return 0 if identical */
 
277
 
 
278
static int hashcmp(HASH *hash,HASH_LINK *pos,const byte *key,uint length)
 
279
{
 
280
  uint rec_keylength;
 
281
  byte *rec_key= (byte*) hash_key(hash,pos->data,&rec_keylength,1);
 
282
  return (length && length != rec_keylength) ||
 
283
    (hash->flags & HASH_CASE_INSENSITIVE ?
 
284
     my_casecmp(rec_key,key,rec_keylength) :
 
285
     memcmp(rec_key,key,rec_keylength));
 
286
}
 
287
 
 
288
 
 
289
        /* Write a hash-key to the hash-index */
 
290
 
 
291
my_bool hash_insert(HASH *info,const byte *record)
 
292
{
 
293
  int flag;
 
294
  uint halfbuff,hash_nr,first_index,idx;
 
295
  byte *ptr_to_rec,*ptr_to_rec2;
 
296
  HASH_LINK *data,*empty,*gpos,*gpos2,*pos;
 
297
 
 
298
  LINT_INIT(gpos); LINT_INIT(gpos2);
 
299
  LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2);
 
300
 
 
301
  flag=0;
 
302
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
 
303
    return(TRUE);                               /* No more memory */
 
304
 
 
305
  info->current_record= NO_RECORD;
 
306
  data=dynamic_element(&info->array,0,HASH_LINK*);
 
307
  halfbuff= info->blength >> 1;
 
308
 
 
309
  idx=first_index=info->records-halfbuff;
 
310
  if (idx != info->records)                             /* If some records */
 
311
  {
 
312
    do
 
313
    {
 
314
      pos=data+idx;
 
315
      hash_nr=rec_hashnr(info,pos->data);
 
316
      if (flag == 0)                            /* First loop; Check if ok */
 
317
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
318
          break;
 
319
      if (!(hash_nr & halfbuff))
 
320
      {                                         /* Key will not move */
 
321
        if (!(flag & LOWFIND))
 
322
        {
 
323
          if (flag & HIGHFIND)
 
324
          {
 
325
            flag=LOWFIND | HIGHFIND;
 
326
            /* key shall be moved to the current empty position */
 
327
            gpos=empty;
 
328
            ptr_to_rec=pos->data;
 
329
            empty=pos;                          /* This place is now free */
 
330
          }
 
331
          else
 
332
          {
 
333
            flag=LOWFIND | LOWUSED;             /* key isn't changed */
 
334
            gpos=pos;
 
335
            ptr_to_rec=pos->data;
 
336
          }
 
337
        }
 
338
        else
 
339
        {
 
340
          if (!(flag & LOWUSED))
 
341
          {
 
342
            /* Change link of previous LOW-key */
 
343
            gpos->data=ptr_to_rec;
 
344
            gpos->next=(uint) (pos-data);
 
345
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
 
346
          }
 
347
          gpos=pos;
 
348
          ptr_to_rec=pos->data;
 
349
        }
 
350
      }
 
351
      else
 
352
      {                                         /* key will be moved */
 
353
        if (!(flag & HIGHFIND))
 
354
        {
 
355
          flag= (flag & LOWFIND) | HIGHFIND;
 
356
          /* key shall be moved to the last (empty) position */
 
357
          gpos2 = empty; empty=pos;
 
358
          ptr_to_rec2=pos->data;
 
359
        }
 
360
        else
 
361
        {
 
362
          if (!(flag & HIGHUSED))
 
363
          {
 
364
            /* Change link of previous hash-key and save */
 
365
            gpos2->data=ptr_to_rec2;
 
366
            gpos2->next=(uint) (pos-data);
 
367
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
 
368
          }
 
369
          gpos2=pos;
 
370
          ptr_to_rec2=pos->data;
 
371
        }
 
372
      }
 
373
    }
 
374
    while ((idx=pos->next) != NO_RECORD);
 
375
 
 
376
    if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
 
377
    {
 
378
      gpos->data=ptr_to_rec;
 
379
      gpos->next=NO_RECORD;
 
380
    }
 
381
    if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
 
382
    {
 
383
      gpos2->data=ptr_to_rec2;
 
384
      gpos2->next=NO_RECORD;
 
385
    }
 
386
  }
 
387
  /* Check if we are at the empty position */
 
388
 
 
389
  idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
 
390
  pos=data+idx;
 
391
  if (pos == empty)
 
392
  {
 
393
    pos->data=(byte*) record;
 
394
    pos->next=NO_RECORD;
 
395
  }
 
396
  else
 
397
  {
 
398
    /* Check if more records in same hash-nr family */
 
399
    empty[0]=pos[0];
 
400
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
 
401
    if (pos == gpos)
 
402
    {
 
403
      pos->data=(byte*) record;
 
404
      pos->next=(uint) (empty - data);
 
405
    }
 
406
    else
 
407
    {
 
408
      pos->data=(byte*) record;
 
409
      pos->next=NO_RECORD;
 
410
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
 
411
    }
 
412
  }
 
413
  if (++info->records == info->blength)
 
414
    info->blength+= info->blength;
 
415
  return(0);
 
416
}
 
417
 
 
418
 
 
419
/******************************************************************************
 
420
** Remove one record from hash-table. The record with the same record
 
421
** ptr is removed.
 
422
** if there is a free-function it's called for record if found
 
423
******************************************************************************/
 
424
 
 
425
my_bool hash_delete(HASH *hash,byte *record)
 
426
{
 
427
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
428
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
 
429
  DBUG_ENTER("hash_delete");
 
430
  if (!hash->records)
 
431
    DBUG_RETURN(1);
 
432
 
 
433
  blength=hash->blength;
 
434
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
435
  /* Search after record with key */
 
436
  pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records);
 
437
  gpos = 0;
 
438
 
 
439
  while (pos->data != record)
 
440
  {
 
441
    gpos=pos;
 
442
    if (pos->next == NO_RECORD)
 
443
      DBUG_RETURN(1);                   /* Key not found */
 
444
    pos=data+pos->next;
 
445
  }
 
446
 
 
447
  if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;
 
448
  hash->current_record= NO_RECORD;
 
449
  lastpos=data+hash->records;
 
450
 
 
451
  /* Remove link to record */
 
452
  empty=pos; empty_index=(uint) (empty-data);
 
453
  if (gpos)
 
454
    gpos->next=pos->next;               /* unlink current ptr */
 
455
  else if (pos->next != NO_RECORD)
 
456
  {
 
457
    empty=data+(empty_index=pos->next);
 
458
    pos->data=empty->data;
 
459
    pos->next=empty->next;
 
460
  }
 
461
 
 
462
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
 
463
    goto exit;
 
464
 
 
465
  /* Move the last key (lastpos) */
 
466
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
 
467
  /* pos is where lastpos should be */
 
468
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
 
469
  if (pos == empty)                     /* Move to empty position. */
 
470
  {
 
471
    empty[0]=lastpos[0];
 
472
    goto exit;
 
473
  }
 
474
  pos_hashnr=rec_hashnr(hash,pos->data);
 
475
  /* pos3 is where the pos should be */
 
476
  pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records);
 
477
  if (pos != pos3)
 
478
  {                                     /* pos is on wrong posit */
 
479
    empty[0]=pos[0];                    /* Save it here */
 
480
    pos[0]=lastpos[0];                  /* This should be here */
 
481
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
 
482
    goto exit;
 
483
  }
 
484
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
 
485
  if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1))
 
486
  {                                     /* Identical key-positions */
 
487
    if (pos2 != hash->records)
 
488
    {
 
489
      empty[0]=lastpos[0];
 
490
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
 
491
      goto exit;
 
492
    }
 
493
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
 
494
  }
 
495
  else idx= NO_RECORD;          /* Different positions merge */
 
496
 
 
497
  empty[0]=lastpos[0];
 
498
  movelink(data,idx,empty_index,pos->next);
 
499
  pos->next=empty_index;
 
500
 
 
501
exit:
 
502
  VOID(pop_dynamic(&hash->array));
 
503
  if (hash->free)
 
504
    (*hash->free)((byte*) record);
 
505
  DBUG_RETURN(0);
 
506
}
 
507
 
 
508
        /*
 
509
          Update keys when record has changed.
 
510
          This is much more efficent than using a delete & insert.
 
511
          */
 
512
 
 
513
my_bool hash_update(HASH *hash,byte *record,byte *old_key,uint old_key_length)
 
514
{
 
515
  uint idx,new_index,new_pos_index,blength,records,empty;
 
516
  HASH_LINK org_link,*data,*previous,*pos;
 
517
  DBUG_ENTER("hash_update");
 
518
 
 
519
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
520
  blength=hash->blength; records=hash->records;
 
521
 
 
522
  /* Search after record with key */
 
523
 
 
524
  idx=hash_mask((*hash->calc_hashnr)(old_key,(old_key_length ?
 
525
                                                old_key_length :
 
526
                                                hash->key_length)),
 
527
                  blength,records);
 
528
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
 
529
  if (idx == new_index)
 
530
    DBUG_RETURN(0);                     /* Nothing to do (No record check) */
 
531
  previous=0;
 
532
  for (;;)
 
533
  {
 
534
 
 
535
    if ((pos= data+idx)->data == record)
 
536
      break;
 
537
    previous=pos;
 
538
    if ((idx=pos->next) == NO_RECORD)
 
539
      DBUG_RETURN(1);                   /* Not found in links */
 
540
  }
 
541
  hash->current_record= NO_RECORD;
 
542
  org_link= *pos;
 
543
  empty=idx;
 
544
 
 
545
  /* Relink record from current chain */
 
546
 
 
547
  if (!previous)
 
548
  {
 
549
    if (pos->next != NO_RECORD)
 
550
    {
 
551
      empty=pos->next;
 
552
      *pos= data[pos->next];
 
553
    }
 
554
  }
 
555
  else
 
556
    previous->next=pos->next;           /* unlink pos */
 
557
 
 
558
  /* Move data to correct position */
 
559
  pos=data+new_index;
 
560
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
 
561
  if (new_index != new_pos_index)
 
562
  {                                     /* Other record in wrong position */
 
563
    data[empty] = *pos;
 
564
    movelink(data,new_index,new_pos_index,empty);
 
565
    org_link.next=NO_RECORD;
 
566
    data[new_index]= org_link;
 
567
  }
 
568
  else
 
569
  {                                     /* Link in chain at right position */
 
570
    org_link.next=data[new_index].next;
 
571
    data[empty]=org_link;
 
572
    data[new_index].next=empty;
 
573
  }
 
574
  DBUG_RETURN(0);
 
575
}
 
576
 
 
577
 
 
578
byte *hash_element(HASH *hash,uint idx)
 
579
{
 
580
  if (idx < hash->records)
 
581
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
 
582
  return 0;
 
583
}
 
584
 
 
585
 
 
586
#ifndef DBUG_OFF
 
587
 
 
588
my_bool hash_check(HASH *hash)
 
589
{
 
590
  int error;
 
591
  uint i,rec_link,found,max_links,seek,links,idx;
 
592
  uint records,blength;
 
593
  HASH_LINK *data,*hash_info;
 
594
 
 
595
  records=hash->records; blength=hash->blength;
 
596
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
597
  error=0;
 
598
 
 
599
  for (i=found=max_links=seek=0 ; i < records ; i++)
 
600
  {
 
601
    if (hash_rec_mask(hash,data+i,blength,records) == i)
 
602
    {
 
603
      found++; seek++; links=1;
 
604
      for (idx=data[i].next ;
 
605
           idx != NO_RECORD && found < records + 1;
 
606
           idx=hash_info->next)
 
607
      {
 
608
        if (idx >= records)
 
609
        {
 
610
          DBUG_PRINT("error",
 
611
                     ("Found pointer outside array to %d from link starting at %d",
 
612
                      idx,i));
 
613
          error=1;
 
614
        }
 
615
        hash_info=data+idx;
 
616
        seek+= ++links;
 
617
        if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i)
 
618
        {
 
619
          DBUG_PRINT("error",
 
620
                     ("Record in wrong link at %d: Start %d  Record: %lx  Record-link %d", idx,i,hash_info->data,rec_link));
 
621
          error=1;
 
622
        }
 
623
        else
 
624
          found++;
 
625
      }
 
626
      if (links > max_links) max_links=links;
 
627
    }
 
628
  }
 
629
  if (found != records)
 
630
  {
 
631
    DBUG_PRINT("error",("Found %ld of %ld records"));
 
632
    error=1;
 
633
  }
 
634
  if (records)
 
635
    DBUG_PRINT("info",
 
636
               ("records: %ld   seeks: %d   max links: %d   hitrate: %.2f",
 
637
                records,seek,max_links,(float) seek / (float) records));
 
638
  return error;
 
639
}
 
640
#endif