← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.cc

  • Committer: Brian Aker
  • Date: 2009-07-11 19:23:04 UTC
  • mfrom: (1089.1.14 merge)
  • Revision ID: brian@gaz-20090711192304-ootijyl5yf9jq9kd
Merge Brian

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/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 <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;
30
34
 
31
35
typedef struct st_hash_info {
32
 
  uint next;                                    /* index to next key */
33
 
  uchar *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 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,
 
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,
39
47
                   size_t length);
40
48
 
41
 
static uint calc_hash(const HASH *hash, const uchar *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 uchar*) 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
 
_hash_init(HASH *hash,uint 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*),uint flags CALLER_INFO_PROTO)
 
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)
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)
132
142
/* some helper functions */
133
143
 
134
144
/*
135
 
  This function is char* instead of uchar* as HPUX11 compiler can't
 
145
  This function is char* instead of unsigned char* as HPUX11 compiler can't
136
146
  handle inline functions that are not defined as native types
137
147
*/
138
148
 
139
149
static inline char*
140
 
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
150
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
141
151
         bool first)
142
152
{
143
153
  if (hash->get_key)
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
 
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
 
161
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
152
162
{
153
163
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
154
164
  return (hashnr & ((buffmax >> 1) -1));
155
165
}
156
166
 
157
 
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
158
 
                          uint buffmax, uint maxlength)
 
167
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
168
                              uint32_t buffmax, uint32_t maxlength)
159
169
{
160
170
  size_t length;
161
 
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
 
171
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
162
172
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
163
173
}
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
 
unsigned int rec_hashnr(HASH *hash,const uchar *record)
 
179
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
173
180
{
174
181
  size_t length;
175
 
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
 
182
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
176
183
  return calc_hash(hash,key,length);
177
184
}
178
185
 
179
186
 
180
 
uchar* hash_search(const HASH *hash, const uchar *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
 
uchar* hash_first(const HASH *hash, const uchar *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
 
  uint flag,idx;
 
206
  uint32_t flag,idx;
198
207
 
199
208
  flag=1;
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
 
uchar* hash_next(const HASH *hash, const uchar *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
 
  uint idx;
 
244
  uint32_t idx;
233
245
 
234
246
  if (*current_record != NO_RECORD)
235
247
  {
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,uint find,uint next_link,uint 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
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
 
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
 
  uchar *rec_key= (uchar*) 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 uchar*) rec_key, rec_keylength,
292
 
                       (const uchar*) 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
 
bool my_hash_insert(HASH *info,const uchar *record)
 
312
bool my_hash_insert(HASH *info,const unsigned char *record)
299
313
{
300
314
  int flag;
301
315
  size_t idx;
302
 
  uint halfbuff,hash_nr,first_index;
303
 
  uchar *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
 
316
  uint32_t halfbuff,hash_nr,first_index;
 
317
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
304
318
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
305
319
 
306
320
  if (HASH_UNIQUE & info->flags)
307
321
  {
308
 
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
 
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= (uint32_t) (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=(uint32_t) (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);
401
423
  pos=data+idx;
402
424
  if (pos == empty)
403
425
  {
404
 
    pos->data=(uchar*) record;
 
426
    pos->data=(unsigned char*) record;
405
427
    pos->next=NO_RECORD;
406
428
  }
407
429
  else
411
433
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
412
434
    if (pos == gpos)
413
435
    {
414
 
      pos->data=(uchar*) record;
415
 
      pos->next=(uint) (empty - data);
 
436
      pos->data=(unsigned char*) record;
 
437
      pos->next=(uint32_t) (empty - data);
416
438
    }
417
439
    else
418
440
    {
419
 
      pos->data=(uchar*) record;
 
441
      pos->data=(unsigned char*) record;
420
442
      pos->next=NO_RECORD;
421
 
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
 
443
      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
422
444
    }
423
445
  }
424
446
  if (++info->records == info->blength)
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
 
bool hash_delete(HASH *hash,uchar *record)
 
458
bool hash_delete(HASH *hash,unsigned char *record)
437
459
{
438
 
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
460
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
439
461
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
440
462
  if (!hash->records)
441
463
    return(1);
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
 
458
482
  lastpos=data+hash->records;
459
483
 
460
484
  /* Remove link to record */
461
 
  empty=pos; empty_index=(uint) (empty-data);
 
485
  empty=pos; empty_index=(uint32_t) (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;
487
514
  {                                     /* pos is on wrong posit */
488
515
    empty[0]=pos[0];                    /* Save it here */
489
516
    pos[0]=lastpos[0];                  /* This should be here */
490
 
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
 
517
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
491
518
    goto exit;
492
519
  }
493
520
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
496
523
    if (pos2 != hash->records)
497
524
    {
498
525
      empty[0]=lastpos[0];
499
 
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
 
526
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
500
527
      goto exit;
501
528
    }
502
 
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
 
529
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
503
530
  }
504
531
  else idx= NO_RECORD;          /* Different positions merge */
505
532
 
508
535
  pos->next=empty_index;
509
536
 
510
537
exit:
511
 
  VOID(pop_dynamic(&hash->array));
 
538
  pop_dynamic(&hash->array);
512
539
  if (hash->free)
513
 
    (*hash->free)((uchar*) record);
 
540
    (*hash->free)((unsigned char*) record);
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
 
bool hash_update(HASH *hash, uchar *record, uchar *old_key,
523
 
                    size_t old_key_length)
 
549
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
 
550
                 size_t old_key_length)
524
551
{
525
 
  uint new_index,new_pos_index,blength,records,empty;
 
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
 
    uchar *found, *new_key= (uchar*) 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) */
618
647
}
619
648
 
620
649
 
621
 
uchar *hash_element(HASH *hash,uint32_t idx)
 
650
unsigned char *hash_element(HASH *hash,uint32_t idx)
622
651
{
623
652
  if (idx < hash->records)
624
653
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
631
660
  isn't changed
632
661
*/
633
662
 
634
 
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *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;