← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

Fixed sql_builtin.cc.in... stupid generated files.

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