← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

Cleanup around SAFEMALLOC

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 "config.h"
25
 
#include "drizzled/my_hash.h"
26
 
#include "drizzled/charset.h"
27
 
#include "drizzled/charset_info.h"
28
 
 
29
 
namespace drizzled
30
 
{
31
 
 
32
 
const uint32_t NO_RECORD= UINT32_MAX;
33
 
 
34
 
const int LOWFIND= 1;
35
 
const int LOWUSED= 2;
36
 
const int HIGHFIND= 4;
37
 
const int HIGHUSED= 8;
 
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
38
30
 
39
31
typedef struct st_hash_info {
40
 
  /* index to next key */
41
 
  uint32_t next;
42
 
  /* data for current entry */
43
 
  unsigned char *data;
 
32
  uint next;                                    /* index to next key */
 
33
  uchar *data;                                  /* data for current entry */
44
34
} HASH_LINK;
45
35
 
46
 
static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax,
47
 
                          uint32_t maxlength);
48
 
static void movelink(HASH_LINK *array, uint32_t pos,
49
 
                     uint32_t next_link, uint32_t newlink);
50
 
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,
51
39
                   size_t length);
52
40
 
53
 
static uint32_t calc_hash(const HASH *hash, const unsigned char *key,
54
 
                          size_t length)
 
41
static uint calc_hash(const HASH *hash, const uchar *key, size_t length)
55
42
{
56
43
  uint32_t nr1=1, nr2=4;
57
 
  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
 
44
  hash->charset->coll->hash_sort(hash->charset,(const uchar*) key,length,&nr1,&nr2);
58
45
  return nr1;
59
46
}
60
47
 
61
48
bool
62
 
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
63
 
           uint32_t size, size_t key_offset, size_t key_length,
64
 
           hash_get_key get_key,
65
 
           hash_free_key free_element, uint32_t flags)
 
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)
66
53
{
67
54
  hash->records=0;
68
55
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
69
56
                               growth_size))
70
57
  {
71
 
    /* Allow call to hash_free */
72
 
    hash->free=0;
 
58
    hash->free=0;                               /* Allow call to hash_free */
73
59
    return true;
74
60
  }
75
61
  hash->key_offset=key_offset;
87
73
  Call hash->free on all elements in hash.
88
74
 
89
75
  SYNOPSIS
90
 
  hash_free_elements()
91
 
  hash   hash table
 
76
    hash_free_elements()
 
77
    hash   hash table
92
78
 
93
79
  NOTES:
94
 
  Sets records to 0
 
80
    Sets records to 0
95
81
*/
96
82
 
97
83
static inline void hash_free_elements(HASH *hash)
111
97
  Free memory used by hash.
112
98
 
113
99
  SYNOPSIS
114
 
  hash_free()
115
 
  hash   the hash to delete elements of
 
100
    hash_free()
 
101
    hash   the hash to delete elements of
116
102
 
117
103
  NOTES: Hash can't be reused without calling hash_init again.
118
104
*/
125
111
  return;
126
112
}
127
113
 
 
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
 
128
132
/* some helper functions */
129
133
 
130
134
/*
131
 
  This function is char* instead of unsigned char* as HPUX11 compiler can't
 
135
  This function is char* instead of uchar* as HPUX11 compiler can't
132
136
  handle inline functions that are not defined as native types
133
137
*/
134
138
 
135
139
static inline char*
136
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
 
140
hash_key(const HASH *hash, const uchar *record, size_t *length,
137
141
         bool first)
138
142
{
139
143
  if (hash->get_key)
142
146
  return (char*) record+hash->key_offset;
143
147
}
144
148
 
145
 
/* Calculate pos according to keys */
 
149
        /* Calculate pos according to keys */
146
150
 
147
 
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
 
151
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
148
152
{
149
153
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
150
154
  return (hashnr & ((buffmax >> 1) -1));
151
155
}
152
156
 
153
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
154
 
                              uint32_t buffmax, uint32_t maxlength)
 
157
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
158
                          uint buffmax, uint maxlength)
155
159
{
156
160
  size_t length;
157
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
161
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
158
162
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
159
163
}
160
164
 
161
165
 
162
166
 
 
167
/* for compilers which can not handle inline */
163
168
static
 
169
#if !defined(__USLC__) && !defined(__sgi)
164
170
inline
165
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
171
#endif
 
172
unsigned int rec_hashnr(HASH *hash,const uchar *record)
166
173
{
167
174
  size_t length;
168
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
175
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
169
176
  return calc_hash(hash,key,length);
170
177
}
171
178
 
172
179
 
173
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
174
 
                           size_t length)
 
180
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
175
181
{
176
182
  HASH_SEARCH_STATE state;
177
183
  return hash_first(hash, key, length, &state);
181
187
  Search after a record based on a key
182
188
 
183
189
  NOTE
184
 
  Assigns the number of the found record to HASH_SEARCH_STATE state
 
190
   Assigns the number of the found record to HASH_SEARCH_STATE state
185
191
*/
186
192
 
187
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
188
 
                          size_t length,
189
 
                          HASH_SEARCH_STATE *current_record)
 
193
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
 
194
                HASH_SEARCH_STATE *current_record)
190
195
{
191
196
  HASH_LINK *pos;
192
 
  uint32_t flag,idx;
 
197
  uint flag,idx;
193
198
 
194
199
  flag=1;
195
200
  if (hash->records)
196
201
  {
197
202
    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
198
 
                  hash->blength,hash->records);
 
203
                    hash->blength,hash->records);
199
204
    do
200
205
    {
201
206
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
202
207
      if (!hashcmp(hash,pos,key,length))
203
208
      {
204
 
        *current_record= idx;
205
 
        return (pos->data);
 
209
        *current_record= idx;
 
210
        return (pos->data);
206
211
      }
207
212
      if (flag)
208
213
      {
209
 
        /* Reset flag */
210
 
        flag=0;
211
 
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
212
 
          /* Wrong link */
213
 
          break;
 
214
        flag=0;                                 /* Reset flag */
 
215
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
216
          break;                                /* Wrong link */
214
217
      }
215
218
    }
216
219
    while ((idx=pos->next) != NO_RECORD);
219
222
  return(0);
220
223
}
221
224
 
222
 
/* Get next record with identical key */
223
 
/* Can only be called if previous calls was hash_search */
 
225
        /* Get next record with identical key */
 
226
        /* Can only be called if previous calls was hash_search */
224
227
 
225
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
226
 
                         size_t length,
227
 
                         HASH_SEARCH_STATE *current_record)
 
228
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
 
229
               HASH_SEARCH_STATE *current_record)
228
230
{
229
231
  HASH_LINK *pos;
230
 
  uint32_t idx;
 
232
  uint idx;
231
233
 
232
234
  if (*current_record != NO_RECORD)
233
235
  {
237
239
      pos=data+idx;
238
240
      if (!hashcmp(hash,pos,key,length))
239
241
      {
240
 
        *current_record= idx;
241
 
        return pos->data;
 
242
        *current_record= idx;
 
243
        return pos->data;
242
244
      }
243
245
    }
244
246
    *current_record= NO_RECORD;
247
249
}
248
250
 
249
251
 
250
 
/* Change link from pos to new_link */
 
252
        /* Change link from pos to new_link */
251
253
 
252
 
static void movelink(HASH_LINK *array, uint32_t find,
253
 
                     uint32_t next_link, uint32_t newlink)
 
254
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
254
255
{
255
256
  HASH_LINK *old_link;
256
257
  do
266
267
  Compare a key in a record to a whole key. Return 0 if identical
267
268
 
268
269
  SYNOPSIS
269
 
  hashcmp()
270
 
  hash   hash table
271
 
  pos    position of hash record to use in comparison
272
 
  key    key for comparison
273
 
  length length of key
 
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
274
275
 
275
276
  NOTES:
276
 
  If length is 0, comparison is done using the length of the
277
 
  record being compared against.
 
277
    If length is 0, comparison is done using the length of the
 
278
    record being compared against.
278
279
 
279
280
  RETURN
280
 
  = 0  key of record == key
281
 
  != 0 key of record != key
282
 
*/
 
281
    = 0  key of record == key
 
282
    != 0 key of record != key
 
283
 */
283
284
 
284
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
 
285
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
285
286
                   size_t length)
286
287
{
287
288
  size_t rec_keylength;
288
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
289
 
                                                    &rec_keylength,1);
 
289
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
290
290
  return ((length && length != rec_keylength) ||
291
 
          my_strnncoll(hash->charset, rec_key, rec_keylength,
292
 
                       key, rec_keylength));
 
291
          my_strnncoll(hash->charset, (const uchar*) rec_key, rec_keylength,
 
292
                       (const uchar*) key, rec_keylength));
293
293
}
294
294
 
295
295
 
296
 
/* Write a hash-key to the hash-index */
 
296
        /* Write a hash-key to the hash-index */
297
297
 
298
 
bool my_hash_insert(HASH *info,const unsigned char *record)
 
298
bool my_hash_insert(HASH *info,const uchar *record)
299
299
{
300
300
  int flag;
301
301
  size_t idx;
302
 
  uint32_t halfbuff,hash_nr,first_index;
303
 
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
 
302
  uint halfbuff,hash_nr,first_index;
 
303
  uchar *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
304
304
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
305
305
 
306
306
  if (HASH_UNIQUE & info->flags)
307
307
  {
308
 
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
 
308
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
309
309
    if (hash_search(info, key, idx))
310
 
      /* Duplicate entry */
311
 
      return(true);
 
310
      return(true);                             /* Duplicate entry */
312
311
  }
313
312
 
314
313
  flag=0;
315
314
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
316
 
    /* No more memory */
317
 
    return(true);
 
315
    return(true);                               /* No more memory */
318
316
 
319
317
  data=dynamic_element(&info->array,0,HASH_LINK*);
320
318
  halfbuff= info->blength >> 1;
321
319
 
322
 
  idx= first_index= info->records-halfbuff;
323
 
  /* If some records */
324
 
  if (idx != info->records)
 
320
  idx=first_index=info->records-halfbuff;
 
321
  if (idx != info->records)                             /* If some records */
325
322
  {
326
323
    do
327
324
    {
328
325
      pos=data+idx;
329
326
      hash_nr=rec_hashnr(info,pos->data);
330
 
      /* First loop; Check if ok */
331
 
      if (flag == 0)
332
 
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
333
 
          break;
 
327
      if (flag == 0)                            /* First loop; Check if ok */
 
328
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
329
          break;
334
330
      if (!(hash_nr & halfbuff))
335
 
      {
336
 
        /* Key will not move */
337
 
        if (!(flag & LOWFIND))
338
 
        {
339
 
          if (flag & HIGHFIND)
340
 
          {
341
 
            flag=LOWFIND | HIGHFIND;
342
 
            /* key shall be moved to the current empty position */
343
 
            gpos=empty;
344
 
            ptr_to_rec=pos->data;
345
 
            /* This place is now free */
346
 
            empty=pos;
347
 
          }
348
 
          else
349
 
          {
350
 
            /* key isn't changed */
351
 
            flag=LOWFIND | LOWUSED;
352
 
            gpos=pos;
353
 
            ptr_to_rec=pos->data;
354
 
          }
355
 
        }
356
 
        else
357
 
        {
358
 
          if (!(flag & LOWUSED))
359
 
          {
360
 
            /* Change link of previous LOW-key */
361
 
            gpos->data=ptr_to_rec;
362
 
            gpos->next= (uint32_t) (pos-data);
363
 
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
364
 
          }
365
 
          gpos=pos;
366
 
          ptr_to_rec=pos->data;
367
 
        }
 
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
        }
368
361
      }
369
362
      else
370
 
      {
371
 
        /* key will be moved */
372
 
        if (!(flag & HIGHFIND))
373
 
        {
374
 
          flag= (flag & LOWFIND) | HIGHFIND;
375
 
          /* key shall be moved to the last (empty) position */
376
 
          gpos2 = empty; empty=pos;
377
 
          ptr_to_rec2=pos->data;
378
 
        }
379
 
        else
380
 
        {
381
 
          if (!(flag & HIGHUSED))
382
 
          {
383
 
            /* Change link of previous hash-key and save */
384
 
            gpos2->data=ptr_to_rec2;
385
 
            gpos2->next=(uint32_t) (pos-data);
386
 
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
387
 
          }
388
 
          gpos2=pos;
389
 
          ptr_to_rec2=pos->data;
390
 
        }
 
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
        }
391
383
      }
392
384
    }
393
385
    while ((idx=pos->next) != NO_RECORD);
409
401
  pos=data+idx;
410
402
  if (pos == empty)
411
403
  {
412
 
    pos->data=(unsigned char*) record;
 
404
    pos->data=(uchar*) record;
413
405
    pos->next=NO_RECORD;
414
406
  }
415
407
  else
419
411
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
420
412
    if (pos == gpos)
421
413
    {
422
 
      pos->data=(unsigned char*) record;
423
 
      pos->next=(uint32_t) (empty - data);
 
414
      pos->data=(uchar*) record;
 
415
      pos->next=(uint) (empty - data);
424
416
    }
425
417
    else
426
418
    {
427
 
      pos->data=(unsigned char*) record;
 
419
      pos->data=(uchar*) record;
428
420
      pos->next=NO_RECORD;
429
 
      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
 
421
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
430
422
    }
431
423
  }
432
424
  if (++info->records == info->blength)
436
428
 
437
429
 
438
430
/******************************************************************************
439
 
 ** Remove one record from hash-table. The record with the same record
440
 
 ** ptr is removed.
441
 
 ** if there is a free-function it's called for record if found
442
 
 *****************************************************************************/
 
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
******************************************************************************/
443
435
 
444
 
bool hash_delete(HASH *hash,unsigned char *record)
 
436
bool hash_delete(HASH *hash,uchar *record)
445
437
{
446
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
438
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
447
439
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
448
440
  if (!hash->records)
449
441
    return(1);
458
450
  {
459
451
    gpos=pos;
460
452
    if (pos->next == NO_RECORD)
461
 
      /* Key not found */
462
 
      return(1);
463
 
 
 
453
      return(1);                        /* Key not found */
464
454
    pos=data+pos->next;
465
455
  }
466
456
 
468
458
  lastpos=data+hash->records;
469
459
 
470
460
  /* Remove link to record */
471
 
  empty=pos; empty_index=(uint32_t) (empty-data);
 
461
  empty=pos; empty_index=(uint) (empty-data);
472
462
  if (gpos)
473
 
    /* unlink current ptr */
474
 
    gpos->next=pos->next;
 
463
    gpos->next=pos->next;               /* unlink current ptr */
475
464
  else if (pos->next != NO_RECORD)
476
465
  {
477
466
    empty=data+(empty_index=pos->next);
479
468
    pos->next=empty->next;
480
469
  }
481
470
 
482
 
  /* last key at wrong pos or no next link */
483
 
  if (empty == lastpos)
 
471
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
484
472
    goto exit;
485
473
 
486
474
  /* Move the last key (lastpos) */
487
475
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
488
476
  /* pos is where lastpos should be */
489
477
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
490
 
  /* Move to empty position. */
491
 
  if (pos == empty)
 
478
  if (pos == empty)                     /* Move to empty position. */
492
479
  {
493
480
    empty[0]=lastpos[0];
494
481
    goto exit;
500
487
  {                                     /* pos is on wrong posit */
501
488
    empty[0]=pos[0];                    /* Save it here */
502
489
    pos[0]=lastpos[0];                  /* This should be here */
503
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
 
490
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
504
491
    goto exit;
505
492
  }
506
493
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
509
496
    if (pos2 != hash->records)
510
497
    {
511
498
      empty[0]=lastpos[0];
512
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
 
499
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
513
500
      goto exit;
514
501
    }
515
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
 
502
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
516
503
  }
517
504
  else idx= NO_RECORD;          /* Different positions merge */
518
505
 
521
508
  pos->next=empty_index;
522
509
 
523
510
exit:
524
 
  pop_dynamic(&hash->array);
 
511
  VOID(pop_dynamic(&hash->array));
525
512
  if (hash->free)
526
 
    (*hash->free)((unsigned char*) record);
527
 
  return(0);
528
 
}
529
 
 
530
 
unsigned char *hash_element(HASH *hash,uint32_t idx)
 
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)
531
622
{
532
623
  if (idx < hash->records)
533
624
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
534
625
  return 0;
535
626
}
536
627
 
537
 
} /* namespace drizzled */
 
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
}