← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/my_hash.cc

  • Committer: Brian Aker
  • Date: 2010-01-27 18:58:12 UTC
  • Revision ID: brian@gaz-20100127185812-n62n0vwetnx8jrjy
Remove dead code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/my_hash.cc
1
 
/* Copyright (C) 2000 MySQL AB
2
 
 
3
 
   This program is free software; you can redistribute it and/or modify
4
 
   it under the terms of the GNU General Public License as published by
5
 
   the Free Software Foundation; version 2 of the License.
6
 
 
7
 
   This program is distributed in the hope that it will be useful,
8
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
9
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10
 
   GNU General Public License for more details.
11
 
 
12
 
   You should have received a copy of the GNU General Public License
13
 
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
 
 
16
 
/* The hash functions used for saveing keys */
 
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 
3
 *
 
4
 *  Copyright (C) 2008 Sun Microsystems
 
5
 *
 
6
 *  This program is free software; you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation; version 2 of the License.
 
9
 *
 
10
 *  This program is distributed in the hope that it will be useful,
 
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *  GNU General Public License for more details.
 
14
 *
 
15
 *  You should have received a copy of the GNU General Public License
 
16
 *  along with this program; if not, write to the Free Software
 
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 */
 
19
 
 
20
/* The hash functions used for saving keys */
17
21
/* One of key_length or key_length_offset must be given */
18
22
/* Key length of 0 isn't allowed */
19
23
 
20
 
#include "mysys_priv.h"
21
 
#include <mystrings/m_string.h>
22
 
#include <mystrings/m_ctype.h>
23
 
#include "hash.h"
24
 
 
25
 
#define NO_RECORD       ((uint) -1)
26
 
#define LOWFIND 1
27
 
#define LOWUSED 2
28
 
#define HIGHFIND 4
29
 
#define HIGHUSED 8
 
24
#include "config.h"
 
25
#include "drizzled/my_hash.h"
 
26
#include "drizzled/charset.h"
 
27
#include "drizzled/charset_info.h"
 
28
 
 
29
const uint32_t NO_RECORD= UINT32_MAX;
 
30
 
 
31
const int LOWFIND= 1;
 
32
const int LOWUSED= 2;
 
33
const int HIGHFIND= 4;
 
34
const int HIGHUSED= 8;
30
35
 
31
36
typedef struct st_hash_info {
32
 
  uint next;                                    /* index to next key */
33
 
  uchar *data;                                  /* data for current entry */
 
37
  /* index to next key */
 
38
  uint32_t next;
 
39
  /* data for current entry */
 
40
  unsigned char *data;
34
41
} HASH_LINK;
35
42
 
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,
 
43
static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax,
 
44
                          uint32_t maxlength);
 
45
static void movelink(HASH_LINK *array, uint32_t pos,
 
46
                     uint32_t next_link, uint32_t newlink);
 
47
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
39
48
                   size_t length);
40
49
 
41
 
static uint calc_hash(const HASH *hash, const uchar *key, size_t length)
 
50
static uint32_t calc_hash(const HASH *hash, const unsigned char *key,
 
51
                          size_t length)
42
52
{
43
53
  uint32_t nr1=1, nr2=4;
44
 
  hash->charset->coll->hash_sort(hash->charset,(const uchar*) key,length,&nr1,&nr2);
 
54
  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
45
55
  return nr1;
46
56
}
47
57
 
48
58
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)
 
59
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
 
60
           uint32_t size, size_t key_offset, size_t key_length,
 
61
           hash_get_key get_key,
 
62
           hash_free_key free_element, uint32_t flags)
53
63
{
54
64
  hash->records=0;
55
65
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
56
66
                               growth_size))
57
67
  {
58
 
    hash->free=0;                               /* Allow call to hash_free */
 
68
    /* Allow call to hash_free */
 
69
    hash->free=0;
59
70
    return true;
60
71
  }
61
72
  hash->key_offset=key_offset;
73
84
  Call hash->free on all elements in hash.
74
85
 
75
86
  SYNOPSIS
76
 
    hash_free_elements()
77
 
    hash   hash table
 
87
  hash_free_elements()
 
88
  hash   hash table
78
89
 
79
90
  NOTES:
80
 
    Sets records to 0
 
91
  Sets records to 0
81
92
*/
82
93
 
83
94
static inline void hash_free_elements(HASH *hash)
97
108
  Free memory used by hash.
98
109
 
99
110
  SYNOPSIS
100
 
    hash_free()
101
 
    hash   the hash to delete elements of
 
111
  hash_free()
 
112
  hash   the hash to delete elements of
102
113
 
103
114
  NOTES: Hash can't be reused without calling hash_init again.
104
115
*/
111
122
  return;
112
123
}
113
124
 
114
 
 
115
 
/*
116
 
  Delete all elements from the hash (the hash itself is to be reused).
117
 
 
118
 
  SYNOPSIS
119
 
    my_hash_reset()
120
 
    hash   the hash to delete elements of
121
 
*/
122
 
 
123
 
void my_hash_reset(HASH *hash)
124
 
{
125
 
  hash_free_elements(hash);
126
 
  reset_dynamic(&hash->array);
127
 
  /* Set row pointers so that the hash can be reused at once */
128
 
  hash->blength= 1;
129
 
  return;
130
 
}
131
 
 
132
125
/* some helper functions */
133
126
 
134
127
/*
135
 
  This function is char* instead of uchar* as HPUX11 compiler can't
 
128
  This function is char* instead of unsigned char* as HPUX11 compiler can't
136
129
  handle inline functions that are not defined as native types
137
130
*/
138
131
 
139
132
static inline char*
140
 
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
133
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
141
134
         bool first)
142
135
{
143
136
  if (hash->get_key)
146
139
  return (char*) record+hash->key_offset;
147
140
}
148
141
 
149
 
        /* Calculate pos according to keys */
 
142
/* Calculate pos according to keys */
150
143
 
151
 
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
 
144
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
152
145
{
153
146
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
154
147
  return (hashnr & ((buffmax >> 1) -1));
155
148
}
156
149
 
157
 
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
158
 
                          uint buffmax, uint maxlength)
 
150
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
151
                              uint32_t buffmax, uint32_t maxlength)
159
152
{
160
153
  size_t length;
161
 
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
 
154
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
162
155
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
163
156
}
164
157
 
165
158
 
166
159
 
167
 
/* for compilers which can not handle inline */
168
160
static
169
 
#if !defined(__USLC__) && !defined(__sgi)
170
161
inline
171
 
#endif
172
 
unsigned int rec_hashnr(HASH *hash,const uchar *record)
 
162
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
173
163
{
174
164
  size_t length;
175
 
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
 
165
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
176
166
  return calc_hash(hash,key,length);
177
167
}
178
168
 
179
169
 
180
 
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
 
170
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
 
171
                           size_t length)
181
172
{
182
173
  HASH_SEARCH_STATE state;
183
174
  return hash_first(hash, key, length, &state);
187
178
  Search after a record based on a key
188
179
 
189
180
  NOTE
190
 
   Assigns the number of the found record to HASH_SEARCH_STATE state
 
181
  Assigns the number of the found record to HASH_SEARCH_STATE state
191
182
*/
192
183
 
193
 
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
194
 
                HASH_SEARCH_STATE *current_record)
 
184
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
 
185
                          size_t length,
 
186
                          HASH_SEARCH_STATE *current_record)
195
187
{
196
188
  HASH_LINK *pos;
197
 
  uint flag,idx;
 
189
  uint32_t flag,idx;
198
190
 
199
191
  flag=1;
200
192
  if (hash->records)
201
193
  {
202
194
    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
203
 
                    hash->blength,hash->records);
 
195
                  hash->blength,hash->records);
204
196
    do
205
197
    {
206
198
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
207
199
      if (!hashcmp(hash,pos,key,length))
208
200
      {
209
 
        *current_record= idx;
210
 
        return (pos->data);
 
201
        *current_record= idx;
 
202
        return (pos->data);
211
203
      }
212
204
      if (flag)
213
205
      {
214
 
        flag=0;                                 /* Reset flag */
215
 
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
216
 
          break;                                /* Wrong link */
 
206
        /* Reset flag */
 
207
        flag=0;
 
208
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
209
          /* Wrong link */
 
210
          break;
217
211
      }
218
212
    }
219
213
    while ((idx=pos->next) != NO_RECORD);
222
216
  return(0);
223
217
}
224
218
 
225
 
        /* Get next record with identical key */
226
 
        /* Can only be called if previous calls was hash_search */
 
219
/* Get next record with identical key */
 
220
/* Can only be called if previous calls was hash_search */
227
221
 
228
 
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
229
 
               HASH_SEARCH_STATE *current_record)
 
222
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
 
223
                         size_t length,
 
224
                         HASH_SEARCH_STATE *current_record)
230
225
{
231
226
  HASH_LINK *pos;
232
 
  uint idx;
 
227
  uint32_t idx;
233
228
 
234
229
  if (*current_record != NO_RECORD)
235
230
  {
239
234
      pos=data+idx;
240
235
      if (!hashcmp(hash,pos,key,length))
241
236
      {
242
 
        *current_record= idx;
243
 
        return pos->data;
 
237
        *current_record= idx;
 
238
        return pos->data;
244
239
      }
245
240
    }
246
241
    *current_record= NO_RECORD;
249
244
}
250
245
 
251
246
 
252
 
        /* Change link from pos to new_link */
 
247
/* Change link from pos to new_link */
253
248
 
254
 
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
 
249
static void movelink(HASH_LINK *array, uint32_t find,
 
250
                     uint32_t next_link, uint32_t newlink)
255
251
{
256
252
  HASH_LINK *old_link;
257
253
  do
267
263
  Compare a key in a record to a whole key. Return 0 if identical
268
264
 
269
265
  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
 
266
  hashcmp()
 
267
  hash   hash table
 
268
  pos    position of hash record to use in comparison
 
269
  key    key for comparison
 
270
  length length of key
275
271
 
276
272
  NOTES:
277
 
    If length is 0, comparison is done using the length of the
278
 
    record being compared against.
 
273
  If length is 0, comparison is done using the length of the
 
274
  record being compared against.
279
275
 
280
276
  RETURN
281
 
    = 0  key of record == key
282
 
    != 0 key of record != key
283
 
 */
 
277
  = 0  key of record == key
 
278
  != 0 key of record != key
 
279
*/
284
280
 
285
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
 
281
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
286
282
                   size_t length)
287
283
{
288
284
  size_t rec_keylength;
289
 
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
 
285
  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
 
286
                                                    &rec_keylength,1);
290
287
  return ((length && length != rec_keylength) ||
291
 
          my_strnncoll(hash->charset, (const uchar*) rec_key, rec_keylength,
292
 
                       (const uchar*) key, rec_keylength));
 
288
          my_strnncoll(hash->charset, rec_key, rec_keylength,
 
289
                       key, rec_keylength));
293
290
}
294
291
 
295
292
 
296
 
        /* Write a hash-key to the hash-index */
 
293
/* Write a hash-key to the hash-index */
297
294
 
298
 
bool my_hash_insert(HASH *info,const uchar *record)
 
295
bool my_hash_insert(HASH *info,const unsigned char *record)
299
296
{
300
297
  int flag;
301
298
  size_t idx;
302
 
  uint halfbuff,hash_nr,first_index;
303
 
  uchar *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
 
299
  uint32_t halfbuff,hash_nr,first_index;
 
300
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
304
301
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
305
302
 
306
303
  if (HASH_UNIQUE & info->flags)
307
304
  {
308
 
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
 
305
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
309
306
    if (hash_search(info, key, idx))
310
 
      return(true);                             /* Duplicate entry */
 
307
      /* Duplicate entry */
 
308
      return(true);
311
309
  }
312
310
 
313
311
  flag=0;
314
312
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
315
 
    return(true);                               /* No more memory */
 
313
    /* No more memory */
 
314
    return(true);
316
315
 
317
316
  data=dynamic_element(&info->array,0,HASH_LINK*);
318
317
  halfbuff= info->blength >> 1;
319
318
 
320
 
  idx=first_index=info->records-halfbuff;
321
 
  if (idx != info->records)                             /* If some records */
 
319
  idx= first_index= info->records-halfbuff;
 
320
  /* If some records */
 
321
  if (idx != info->records)
322
322
  {
323
323
    do
324
324
    {
325
325
      pos=data+idx;
326
326
      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;
 
327
      /* First loop; Check if ok */
 
328
      if (flag == 0)
 
329
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
330
          break;
330
331
      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
 
        }
 
332
      {
 
333
        /* Key will not move */
 
334
        if (!(flag & LOWFIND))
 
335
        {
 
336
          if (flag & HIGHFIND)
 
337
          {
 
338
            flag=LOWFIND | HIGHFIND;
 
339
            /* key shall be moved to the current empty position */
 
340
            gpos=empty;
 
341
            ptr_to_rec=pos->data;
 
342
            /* This place is now free */
 
343
            empty=pos;
 
344
          }
 
345
          else
 
346
          {
 
347
            /* key isn't changed */
 
348
            flag=LOWFIND | LOWUSED;
 
349
            gpos=pos;
 
350
            ptr_to_rec=pos->data;
 
351
          }
 
352
        }
 
353
        else
 
354
        {
 
355
          if (!(flag & LOWUSED))
 
356
          {
 
357
            /* Change link of previous LOW-key */
 
358
            gpos->data=ptr_to_rec;
 
359
            gpos->next= (uint32_t) (pos-data);
 
360
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
 
361
          }
 
362
          gpos=pos;
 
363
          ptr_to_rec=pos->data;
 
364
        }
361
365
      }
362
366
      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
 
        }
 
367
      {
 
368
        /* key will be moved */
 
369
        if (!(flag & HIGHFIND))
 
370
        {
 
371
          flag= (flag & LOWFIND) | HIGHFIND;
 
372
          /* key shall be moved to the last (empty) position */
 
373
          gpos2 = empty; empty=pos;
 
374
          ptr_to_rec2=pos->data;
 
375
        }
 
376
        else
 
377
        {
 
378
          if (!(flag & HIGHUSED))
 
379
          {
 
380
            /* Change link of previous hash-key and save */
 
381
            gpos2->data=ptr_to_rec2;
 
382
            gpos2->next=(uint32_t) (pos-data);
 
383
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
 
384
          }
 
385
          gpos2=pos;
 
386
          ptr_to_rec2=pos->data;
 
387
        }
383
388
      }
384
389
    }
385
390
    while ((idx=pos->next) != NO_RECORD);
401
406
  pos=data+idx;
402
407
  if (pos == empty)
403
408
  {
404
 
    pos->data=(uchar*) record;
 
409
    pos->data=(unsigned char*) record;
405
410
    pos->next=NO_RECORD;
406
411
  }
407
412
  else
411
416
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
412
417
    if (pos == gpos)
413
418
    {
414
 
      pos->data=(uchar*) record;
415
 
      pos->next=(uint) (empty - data);
 
419
      pos->data=(unsigned char*) record;
 
420
      pos->next=(uint32_t) (empty - data);
416
421
    }
417
422
    else
418
423
    {
419
 
      pos->data=(uchar*) record;
 
424
      pos->data=(unsigned char*) record;
420
425
      pos->next=NO_RECORD;
421
 
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
 
426
      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
422
427
    }
423
428
  }
424
429
  if (++info->records == info->blength)
428
433
 
429
434
 
430
435
/******************************************************************************
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
 
******************************************************************************/
 
436
 ** Remove one record from hash-table. The record with the same record
 
437
 ** ptr is removed.
 
438
 ** if there is a free-function it's called for record if found
 
439
 *****************************************************************************/
435
440
 
436
 
bool hash_delete(HASH *hash,uchar *record)
 
441
bool hash_delete(HASH *hash,unsigned char *record)
437
442
{
438
 
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
443
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
439
444
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
440
445
  if (!hash->records)
441
446
    return(1);
450
455
  {
451
456
    gpos=pos;
452
457
    if (pos->next == NO_RECORD)
453
 
      return(1);                        /* Key not found */
 
458
      /* Key not found */
 
459
      return(1);
 
460
 
454
461
    pos=data+pos->next;
455
462
  }
456
463
 
458
465
  lastpos=data+hash->records;
459
466
 
460
467
  /* Remove link to record */
461
 
  empty=pos; empty_index=(uint) (empty-data);
 
468
  empty=pos; empty_index=(uint32_t) (empty-data);
462
469
  if (gpos)
463
 
    gpos->next=pos->next;               /* unlink current ptr */
 
470
    /* unlink current ptr */
 
471
    gpos->next=pos->next;
464
472
  else if (pos->next != NO_RECORD)
465
473
  {
466
474
    empty=data+(empty_index=pos->next);
468
476
    pos->next=empty->next;
469
477
  }
470
478
 
471
 
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
 
479
  /* last key at wrong pos or no next link */
 
480
  if (empty == lastpos)
472
481
    goto exit;
473
482
 
474
483
  /* Move the last key (lastpos) */
475
484
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
476
485
  /* pos is where lastpos should be */
477
486
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
478
 
  if (pos == empty)                     /* Move to empty position. */
 
487
  /* Move to empty position. */
 
488
  if (pos == empty)
479
489
  {
480
490
    empty[0]=lastpos[0];
481
491
    goto exit;
487
497
  {                                     /* pos is on wrong posit */
488
498
    empty[0]=pos[0];                    /* Save it here */
489
499
    pos[0]=lastpos[0];                  /* This should be here */
490
 
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
 
500
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
491
501
    goto exit;
492
502
  }
493
503
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
496
506
    if (pos2 != hash->records)
497
507
    {
498
508
      empty[0]=lastpos[0];
499
 
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
 
509
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
500
510
      goto exit;
501
511
    }
502
 
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
 
512
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
503
513
  }
504
514
  else idx= NO_RECORD;          /* Different positions merge */
505
515
 
508
518
  pos->next=empty_index;
509
519
 
510
520
exit:
511
 
  VOID(pop_dynamic(&hash->array));
 
521
  pop_dynamic(&hash->array);
512
522
  if (hash->free)
513
 
    (*hash->free)((uchar*) record);
514
 
  return(0);
515
 
}
516
 
 
517
 
        /*
518
 
          Update keys when record has changed.
519
 
          This is much more efficent than using a delete & insert.
520
 
          */
521
 
 
522
 
bool hash_update(HASH *hash, uchar *record, uchar *old_key,
523
 
                    size_t old_key_length)
524
 
{
525
 
  uint new_index,new_pos_index,blength,records,empty;
526
 
  size_t idx;
527
 
  HASH_LINK org_link,*data,*previous,*pos;
528
 
  
529
 
  if (HASH_UNIQUE & hash->flags)
530
 
  {
531
 
    HASH_SEARCH_STATE state;
532
 
    uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);
533
 
    if ((found= hash_first(hash, new_key, idx, &state)))
534
 
    {
535
 
      do 
536
 
      {
537
 
        if (found != record)
538
 
          return(1);            /* Duplicate entry */
539
 
      } 
540
 
      while ((found= hash_next(hash, new_key, idx, &state)));
541
 
    }
542
 
  }
543
 
 
544
 
  data=dynamic_element(&hash->array,0,HASH_LINK*);
545
 
  blength=hash->blength; records=hash->records;
546
 
 
547
 
  /* Search after record with key */
548
 
 
549
 
  idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?
550
 
                                              old_key_length :
551
 
                                              hash->key_length)),
552
 
                  blength,records);
553
 
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
554
 
  if (idx == new_index)
555
 
    return(0);                  /* Nothing to do (No record check) */
556
 
  previous=0;
557
 
  for (;;)
558
 
  {
559
 
 
560
 
    if ((pos= data+idx)->data == record)
561
 
      break;
562
 
    previous=pos;
563
 
    if ((idx=pos->next) == NO_RECORD)
564
 
      return(1);                        /* Not found in links */
565
 
  }
566
 
  org_link= *pos;
567
 
  empty=idx;
568
 
 
569
 
  /* Relink record from current chain */
570
 
 
571
 
  if (!previous)
572
 
  {
573
 
    if (pos->next != NO_RECORD)
574
 
    {
575
 
      empty=pos->next;
576
 
      *pos= data[pos->next];
577
 
    }
578
 
  }
579
 
  else
580
 
    previous->next=pos->next;           /* unlink pos */
581
 
 
582
 
  /* Move data to correct position */
583
 
  if (new_index == empty)
584
 
  {
585
 
    /*
586
 
      At this point record is unlinked from the old chain, thus it holds
587
 
      random position. By the chance this position is equal to position
588
 
      for the first element in the new chain. That means updated record
589
 
      is the only record in the new chain.
590
 
    */
591
 
    if (empty != idx)
592
 
    {
593
 
      /*
594
 
        Record was moved while unlinking it from the old chain.
595
 
        Copy data to a new position.
596
 
      */
597
 
      data[empty]= org_link;
598
 
    }
599
 
    data[empty].next= NO_RECORD;
600
 
    return(0);
601
 
  }
602
 
  pos=data+new_index;
603
 
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
604
 
  if (new_index != new_pos_index)
605
 
  {                                     /* Other record in wrong position */
606
 
    data[empty] = *pos;
607
 
    movelink(data,new_index,new_pos_index,empty);
608
 
    org_link.next=NO_RECORD;
609
 
    data[new_index]= org_link;
610
 
  }
611
 
  else
612
 
  {                                     /* Link in chain at right position */
613
 
    org_link.next=data[new_index].next;
614
 
    data[empty]=org_link;
615
 
    data[new_index].next=empty;
616
 
  }
617
 
  return(0);
618
 
}
619
 
 
620
 
 
621
 
uchar *hash_element(HASH *hash,uint32_t idx)
 
523
    (*hash->free)((unsigned char*) record);
 
524
  return(0);
 
525
}
 
526
 
 
527
unsigned char *hash_element(HASH *hash,uint32_t idx)
622
528
{
623
529
  if (idx < hash->records)
624
530
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
625
531
  return 0;
626
532
}
627
533
 
628
 
 
629
 
/*
630
 
  Replace old row with new row.  This should only be used when key
631
 
  isn't changed
632
 
*/
633
 
 
634
 
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)
635
 
{
636
 
  if (*current_record != NO_RECORD)            /* Safety */
637
 
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
638
 
}