← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

  • Committer: Monty Taylor
  • Date: 2008-07-05 16:23:40 UTC
  • mto: This revision was merged to the branch mainline in revision 63.
  • Revision ID: monty@inaugust.com-20080705162340-an09yicpupdtwo2m
Fixed simple signdedness problem.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/hash.c
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 */
 
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 */
21
17
/* One of key_length or key_length_offset must be given */
22
18
/* Key length of 0 isn't allowed */
23
19
 
24
 
#include <drizzled/global.h>
25
 
#include CSTDINT_H
26
 
#include <mysys/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;
 
20
#include "mysys_priv.h"
 
21
#include <m_string.h>
 
22
#include <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
34
30
 
35
31
typedef struct st_hash_info {
36
 
  /* index to next key */
37
 
  uint32_t next;
38
 
  /* data for current entry */
39
 
  unsigned char *data;
 
32
  uint next;                                    /* index to next key */
 
33
  uchar *data;                                  /* data for current entry */
40
34
} HASH_LINK;
41
35
 
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);
46
 
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,
47
39
                   size_t length);
48
40
 
49
 
static uint32_t calc_hash(const HASH *hash, const unsigned char *key,
50
 
                          size_t length)
 
41
static uint calc_hash(const HASH *hash, const uchar *key, size_t length)
51
42
{
52
 
  uint32_t nr1=1, nr2=4;
53
 
  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
 
43
  ulong nr1=1, nr2=4;
 
44
  hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);
54
45
  return nr1;
55
46
}
56
47
 
57
 
bool
58
 
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
59
 
           uint32_t size, size_t key_offset, size_t key_length,
60
 
           hash_get_key get_key,
61
 
           hash_free_key free_element, uint32_t flags)
 
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
           hash_get_key get_key,
 
52
           void (*free_element)(void*),uint flags CALLER_INFO_PROTO)
62
53
{
 
54
  DBUG_ENTER("hash_init");
 
55
  DBUG_PRINT("enter",("hash: 0x%lx  size: %u", (long) hash, (uint) size));
 
56
 
63
57
  hash->records=0;
64
58
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
65
59
                               growth_size))
66
60
  {
67
 
    /* Allow call to hash_free */
68
 
    hash->free=0;
69
 
    return true;
 
61
    hash->free=0;                               /* Allow call to hash_free */
 
62
    DBUG_RETURN(1);
70
63
  }
71
64
  hash->key_offset=key_offset;
72
65
  hash->key_length=key_length;
75
68
  hash->free=free_element;
76
69
  hash->flags=flags;
77
70
  hash->charset=charset;
78
 
  return false;
 
71
  DBUG_RETURN(0);
79
72
}
80
73
 
81
74
 
83
76
  Call hash->free on all elements in hash.
84
77
 
85
78
  SYNOPSIS
86
 
  hash_free_elements()
87
 
  hash   hash table
 
79
    hash_free_elements()
 
80
    hash   hash table
88
81
 
89
82
  NOTES:
90
 
  Sets records to 0
 
83
    Sets records to 0
91
84
*/
92
85
 
93
86
static inline void hash_free_elements(HASH *hash)
107
100
  Free memory used by hash.
108
101
 
109
102
  SYNOPSIS
110
 
  hash_free()
111
 
  hash   the hash to delete elements of
 
103
    hash_free()
 
104
    hash   the hash to delete elements of
112
105
 
113
106
  NOTES: Hash can't be reused without calling hash_init again.
114
107
*/
115
108
 
116
109
void hash_free(HASH *hash)
117
110
{
 
111
  DBUG_ENTER("hash_free");
 
112
  DBUG_PRINT("enter",("hash: 0x%lx", (long) hash));
 
113
 
118
114
  hash_free_elements(hash);
119
115
  hash->free= 0;
120
116
  delete_dynamic(&hash->array);
121
 
  return;
 
117
  DBUG_VOID_RETURN;
122
118
}
123
119
 
124
120
 
126
122
  Delete all elements from the hash (the hash itself is to be reused).
127
123
 
128
124
  SYNOPSIS
129
 
  my_hash_reset()
130
 
  hash   the hash to delete elements of
 
125
    my_hash_reset()
 
126
    hash   the hash to delete elements of
131
127
*/
132
128
 
133
129
void my_hash_reset(HASH *hash)
134
130
{
 
131
  DBUG_ENTER("my_hash_reset");
 
132
  DBUG_PRINT("enter",("hash: 0x%lxd", (long) hash));
 
133
 
135
134
  hash_free_elements(hash);
136
135
  reset_dynamic(&hash->array);
137
136
  /* Set row pointers so that the hash can be reused at once */
138
137
  hash->blength= 1;
139
 
  return;
 
138
  DBUG_VOID_RETURN;
140
139
}
141
140
 
142
141
/* some helper functions */
143
142
 
144
143
/*
145
 
  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
146
145
  handle inline functions that are not defined as native types
147
146
*/
148
147
 
149
148
static inline char*
150
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
151
 
         bool first)
 
149
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
150
         my_bool first)
152
151
{
153
152
  if (hash->get_key)
154
153
    return (char*) (*hash->get_key)(record,length,first);
156
155
  return (char*) record+hash->key_offset;
157
156
}
158
157
 
159
 
/* Calculate pos according to keys */
 
158
        /* Calculate pos according to keys */
160
159
 
161
 
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)
162
161
{
163
162
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
164
163
  return (hashnr & ((buffmax >> 1) -1));
165
164
}
166
165
 
167
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
168
 
                              uint32_t buffmax, uint32_t maxlength)
 
166
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
167
                          uint buffmax, uint maxlength)
169
168
{
170
169
  size_t length;
171
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
170
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
172
171
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
173
172
}
174
173
 
175
174
 
176
175
 
 
176
/* for compilers which can not handle inline */
177
177
static
 
178
#if !defined(__USLC__) && !defined(__sgi)
178
179
inline
179
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
180
#endif
 
181
unsigned int rec_hashnr(HASH *hash,const uchar *record)
180
182
{
181
183
  size_t length;
182
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
184
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
183
185
  return calc_hash(hash,key,length);
184
186
}
185
187
 
186
188
 
187
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
188
 
                           size_t length)
 
189
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
189
190
{
190
191
  HASH_SEARCH_STATE state;
191
192
  return hash_first(hash, key, length, &state);
195
196
  Search after a record based on a key
196
197
 
197
198
  NOTE
198
 
  Assigns the number of the found record to HASH_SEARCH_STATE state
 
199
   Assigns the number of the found record to HASH_SEARCH_STATE state
199
200
*/
200
201
 
201
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
202
 
                          size_t length,
203
 
                          HASH_SEARCH_STATE *current_record)
 
202
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
 
203
                HASH_SEARCH_STATE *current_record)
204
204
{
205
205
  HASH_LINK *pos;
206
 
  uint32_t flag,idx;
 
206
  uint flag,idx;
 
207
  DBUG_ENTER("hash_first");
207
208
 
208
209
  flag=1;
209
210
  if (hash->records)
210
211
  {
211
212
    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
212
 
                  hash->blength,hash->records);
 
213
                    hash->blength,hash->records);
213
214
    do
214
215
    {
215
216
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
216
217
      if (!hashcmp(hash,pos,key,length))
217
218
      {
218
 
        *current_record= idx;
219
 
        return (pos->data);
 
219
        DBUG_PRINT("exit",("found key at %d",idx));
 
220
        *current_record= idx;
 
221
        DBUG_RETURN (pos->data);
220
222
      }
221
223
      if (flag)
222
224
      {
223
 
        /* Reset flag */
224
 
        flag=0;
225
 
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
226
 
          /* Wrong link */
227
 
          break;
 
225
        flag=0;                                 /* Reset flag */
 
226
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
227
          break;                                /* Wrong link */
228
228
      }
229
229
    }
230
230
    while ((idx=pos->next) != NO_RECORD);
231
231
  }
232
232
  *current_record= NO_RECORD;
233
 
  return(0);
 
233
  DBUG_RETURN(0);
234
234
}
235
235
 
236
 
/* Get next record with identical key */
237
 
/* 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 */
238
238
 
239
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
240
 
                         size_t length,
241
 
                         HASH_SEARCH_STATE *current_record)
 
239
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
 
240
               HASH_SEARCH_STATE *current_record)
242
241
{
243
242
  HASH_LINK *pos;
244
 
  uint32_t idx;
 
243
  uint idx;
245
244
 
246
245
  if (*current_record != NO_RECORD)
247
246
  {
251
250
      pos=data+idx;
252
251
      if (!hashcmp(hash,pos,key,length))
253
252
      {
254
 
        *current_record= idx;
255
 
        return pos->data;
 
253
        *current_record= idx;
 
254
        return pos->data;
256
255
      }
257
256
    }
258
257
    *current_record= NO_RECORD;
261
260
}
262
261
 
263
262
 
264
 
/* Change link from pos to new_link */
 
263
        /* Change link from pos to new_link */
265
264
 
266
 
static void movelink(HASH_LINK *array, uint32_t find,
267
 
                     uint32_t next_link, uint32_t newlink)
 
265
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
268
266
{
269
267
  HASH_LINK *old_link;
270
268
  do
280
278
  Compare a key in a record to a whole key. Return 0 if identical
281
279
 
282
280
  SYNOPSIS
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
 
281
    hashcmp()
 
282
    hash   hash table
 
283
    pos    position of hash record to use in comparison
 
284
    key    key for comparison
 
285
    length length of key
288
286
 
289
287
  NOTES:
290
 
  If length is 0, comparison is done using the length of the
291
 
  record being compared against.
 
288
    If length is 0, comparison is done using the length of the
 
289
    record being compared against.
292
290
 
293
291
  RETURN
294
 
  = 0  key of record == key
295
 
  != 0 key of record != key
296
 
*/
 
292
    = 0  key of record == key
 
293
    != 0 key of record != key
 
294
 */
297
295
 
298
 
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,
299
297
                   size_t length)
300
298
{
301
299
  size_t rec_keylength;
302
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
303
 
                                                    &rec_keylength,1);
 
300
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
304
301
  return ((length && length != rec_keylength) ||
305
 
          my_strnncoll(hash->charset, rec_key, rec_keylength,
306
 
                       key, rec_keylength));
 
302
          my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,
 
303
                       (uchar*) key, rec_keylength));
307
304
}
308
305
 
309
306
 
310
 
/* Write a hash-key to the hash-index */
 
307
        /* Write a hash-key to the hash-index */
311
308
 
312
 
bool my_hash_insert(HASH *info,const unsigned char *record)
 
309
my_bool my_hash_insert(HASH *info,const uchar *record)
313
310
{
314
311
  int flag;
315
312
  size_t idx;
316
 
  uint32_t halfbuff,hash_nr,first_index;
317
 
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
318
 
  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;
319
316
 
320
317
  if (HASH_UNIQUE & info->flags)
321
318
  {
322
 
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
 
319
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
323
320
    if (hash_search(info, key, idx))
324
 
      /* Duplicate entry */
325
 
      return(true);
 
321
      return(TRUE);                             /* Duplicate entry */
326
322
  }
327
323
 
328
324
  flag=0;
329
325
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
330
 
    /* No more memory */
331
 
    return(true);
 
326
    return(TRUE);                               /* No more memory */
332
327
 
333
328
  data=dynamic_element(&info->array,0,HASH_LINK*);
334
329
  halfbuff= info->blength >> 1;
335
330
 
336
331
  idx=first_index=info->records-halfbuff;
337
 
  /* If some records */
338
 
  if (idx != info->records)
 
332
  if (idx != info->records)                             /* If some records */
339
333
  {
340
334
    do
341
335
    {
342
336
      pos=data+idx;
343
337
      hash_nr=rec_hashnr(info,pos->data);
344
 
      /* First loop; Check if ok */
345
 
      if (flag == 0)
346
 
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
347
 
          break;
 
338
      if (flag == 0)                            /* First loop; Check if ok */
 
339
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
340
          break;
348
341
      if (!(hash_nr & halfbuff))
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
 
        }
 
342
      {                                         /* Key will not move */
 
343
        if (!(flag & LOWFIND))
 
344
        {
 
345
          if (flag & HIGHFIND)
 
346
          {
 
347
            flag=LOWFIND | HIGHFIND;
 
348
            /* key shall be moved to the current empty position */
 
349
            gpos=empty;
 
350
            ptr_to_rec=pos->data;
 
351
            empty=pos;                          /* This place is now free */
 
352
          }
 
353
          else
 
354
          {
 
355
            flag=LOWFIND | LOWUSED;             /* key isn't changed */
 
356
            gpos=pos;
 
357
            ptr_to_rec=pos->data;
 
358
          }
 
359
        }
 
360
        else
 
361
        {
 
362
          if (!(flag & LOWUSED))
 
363
          {
 
364
            /* Change link of previous LOW-key */
 
365
            gpos->data=ptr_to_rec;
 
366
            gpos->next= (uint) (pos-data);
 
367
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
 
368
          }
 
369
          gpos=pos;
 
370
          ptr_to_rec=pos->data;
 
371
        }
382
372
      }
383
373
      else
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
 
        }
 
374
      {                                         /* key will be moved */
 
375
        if (!(flag & HIGHFIND))
 
376
        {
 
377
          flag= (flag & LOWFIND) | HIGHFIND;
 
378
          /* key shall be moved to the last (empty) position */
 
379
          gpos2 = empty; empty=pos;
 
380
          ptr_to_rec2=pos->data;
 
381
        }
 
382
        else
 
383
        {
 
384
          if (!(flag & HIGHUSED))
 
385
          {
 
386
            /* Change link of previous hash-key and save */
 
387
            gpos2->data=ptr_to_rec2;
 
388
            gpos2->next=(uint) (pos-data);
 
389
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
 
390
          }
 
391
          gpos2=pos;
 
392
          ptr_to_rec2=pos->data;
 
393
        }
405
394
      }
406
395
    }
407
396
    while ((idx=pos->next) != NO_RECORD);
423
412
  pos=data+idx;
424
413
  if (pos == empty)
425
414
  {
426
 
    pos->data=(unsigned char*) record;
 
415
    pos->data=(uchar*) record;
427
416
    pos->next=NO_RECORD;
428
417
  }
429
418
  else
433
422
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
434
423
    if (pos == gpos)
435
424
    {
436
 
      pos->data=(unsigned char*) record;
 
425
      pos->data=(uchar*) record;
437
426
      pos->next=(uint) (empty - data);
438
427
    }
439
428
    else
440
429
    {
441
 
      pos->data=(unsigned char*) record;
 
430
      pos->data=(uchar*) record;
442
431
      pos->next=NO_RECORD;
443
432
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
444
433
    }
450
439
 
451
440
 
452
441
/******************************************************************************
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
 
 *****************************************************************************/
 
442
** Remove one record from hash-table. The record with the same record
 
443
** ptr is removed.
 
444
** if there is a free-function it's called for record if found
 
445
******************************************************************************/
457
446
 
458
 
bool hash_delete(HASH *hash,unsigned char *record)
 
447
my_bool hash_delete(HASH *hash,uchar *record)
459
448
{
460
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
449
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
461
450
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
 
451
  DBUG_ENTER("hash_delete");
462
452
  if (!hash->records)
463
 
    return(1);
 
453
    DBUG_RETURN(1);
464
454
 
465
455
  blength=hash->blength;
466
456
  data=dynamic_element(&hash->array,0,HASH_LINK*);
472
462
  {
473
463
    gpos=pos;
474
464
    if (pos->next == NO_RECORD)
475
 
      /* Key not found */
476
 
      return(1);
477
 
 
 
465
      DBUG_RETURN(1);                   /* Key not found */
478
466
    pos=data+pos->next;
479
467
  }
480
468
 
484
472
  /* Remove link to record */
485
473
  empty=pos; empty_index=(uint) (empty-data);
486
474
  if (gpos)
487
 
    /* unlink current ptr */
488
 
    gpos->next=pos->next;
 
475
    gpos->next=pos->next;               /* unlink current ptr */
489
476
  else if (pos->next != NO_RECORD)
490
477
  {
491
478
    empty=data+(empty_index=pos->next);
493
480
    pos->next=empty->next;
494
481
  }
495
482
 
496
 
  /* last key at wrong pos or no next link */
497
 
  if (empty == lastpos)
 
483
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
498
484
    goto exit;
499
485
 
500
486
  /* Move the last key (lastpos) */
501
487
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
502
488
  /* pos is where lastpos should be */
503
489
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
504
 
  /* Move to empty position. */
505
 
  if (pos == empty)
 
490
  if (pos == empty)                     /* Move to empty position. */
506
491
  {
507
492
    empty[0]=lastpos[0];
508
493
    goto exit;
535
520
  pos->next=empty_index;
536
521
 
537
522
exit:
538
 
  pop_dynamic(&hash->array);
 
523
  VOID(pop_dynamic(&hash->array));
539
524
  if (hash->free)
540
 
    (*hash->free)((unsigned char*) record);
541
 
  return(0);
 
525
    (*hash->free)((uchar*) record);
 
526
  DBUG_RETURN(0);
542
527
}
543
528
 
544
 
/*
545
 
  Update keys when record has changed.
546
 
  This is much more efficent than using a delete & insert.
547
 
*/
 
529
        /*
 
530
          Update keys when record has changed.
 
531
          This is much more efficent than using a delete & insert.
 
532
          */
548
533
 
549
 
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
550
 
                 size_t old_key_length)
 
534
my_bool hash_update(HASH *hash, uchar *record, uchar *old_key,
 
535
                    size_t old_key_length)
551
536
{
552
 
  uint32_t new_index,new_pos_index,blength,records,empty;
 
537
  uint new_index,new_pos_index,blength,records,empty;
553
538
  size_t idx;
554
539
  HASH_LINK org_link,*data,*previous,*pos;
555
 
 
 
540
  DBUG_ENTER("hash_update");
 
541
  
556
542
  if (HASH_UNIQUE & hash->flags)
557
543
  {
558
544
    HASH_SEARCH_STATE state;
559
 
    unsigned char *found,
560
 
      *new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
561
 
 
 
545
    uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);
562
546
    if ((found= hash_first(hash, new_key, idx, &state)))
563
547
    {
564
 
      do
 
548
      do 
565
549
      {
566
550
        if (found != record)
567
 
          return(1);            /* Duplicate entry */
568
 
      }
 
551
          DBUG_RETURN(1);               /* Duplicate entry */
 
552
      } 
569
553
      while ((found= hash_next(hash, new_key, idx, &state)));
570
554
    }
571
555
  }
576
560
  /* Search after record with key */
577
561
 
578
562
  idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?
579
 
                                         old_key_length :
580
 
                                         hash->key_length)),
581
 
                blength,records);
 
563
                                              old_key_length :
 
564
                                              hash->key_length)),
 
565
                  blength,records);
582
566
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
583
567
  if (idx == new_index)
584
 
    return(0);                  /* Nothing to do (No record check) */
 
568
    DBUG_RETURN(0);                     /* Nothing to do (No record check) */
585
569
  previous=0;
586
570
  for (;;)
587
571
  {
590
574
      break;
591
575
    previous=pos;
592
576
    if ((idx=pos->next) == NO_RECORD)
593
 
      return(1);                        /* Not found in links */
 
577
      DBUG_RETURN(1);                   /* Not found in links */
594
578
  }
595
579
  org_link= *pos;
596
580
  empty=idx;
626
610
      data[empty]= org_link;
627
611
    }
628
612
    data[empty].next= NO_RECORD;
629
 
    return(0);
 
613
    DBUG_RETURN(0);
630
614
  }
631
615
  pos=data+new_index;
632
616
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
643
627
    data[empty]=org_link;
644
628
    data[new_index].next=empty;
645
629
  }
646
 
  return(0);
 
630
  DBUG_RETURN(0);
647
631
}
648
632
 
649
633
 
650
 
unsigned char *hash_element(HASH *hash,uint32_t idx)
 
634
uchar *hash_element(HASH *hash,ulong idx)
651
635
{
652
636
  if (idx < hash->records)
653
637
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
660
644
  isn't changed
661
645
*/
662
646
 
663
 
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record,
664
 
                  unsigned char *new_row)
 
647
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)
665
648
{
666
649
  if (*current_record != NO_RECORD)            /* Safety */
667
650
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
668
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