← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

Renamed more stuff to drizzle.

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 <m_string.h>
 
22
#include <m_ctype.h>
 
23
#include "hash.h"
 
24
 
 
25
#define NO_RECORD       ((uint) -1)
 
26
#define LOWFIND 1
 
27
#define LOWUSED 2
 
28
#define HIGHFIND 4
 
29
#define HIGHUSED 8
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
 
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)
 
48
my_bool
 
49
_hash_init(HASH *hash,uint growth_size, CHARSET_INFO *charset,
 
50
           ulong size, size_t key_offset, size_t key_length,
 
51
           hash_get_key get_key,
 
52
           void (*free_element)(void*),uint flags CALLER_INFO_PROTO)
66
53
{
 
54
  DBUG_ENTER("hash_init");
 
55
  DBUG_PRINT("enter",("hash: 0x%lx  size: %u", (long) hash, (uint) size));
 
56
 
67
57
  hash->records=0;
68
58
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
69
59
                               growth_size))
70
60
  {
71
 
    /* Allow call to hash_free */
72
 
    hash->free=0;
73
 
    return true;
 
61
    hash->free=0;                               /* Allow call to hash_free */
 
62
    DBUG_RETURN(1);
74
63
  }
75
64
  hash->key_offset=key_offset;
76
65
  hash->key_length=key_length;
79
68
  hash->free=free_element;
80
69
  hash->flags=flags;
81
70
  hash->charset=charset;
82
 
  return false;
 
71
  DBUG_RETURN(0);
83
72
}
84
73
 
85
74
 
87
76
  Call hash->free on all elements in hash.
88
77
 
89
78
  SYNOPSIS
90
 
  hash_free_elements()
91
 
  hash   hash table
 
79
    hash_free_elements()
 
80
    hash   hash table
92
81
 
93
82
  NOTES:
94
 
  Sets records to 0
 
83
    Sets records to 0
95
84
*/
96
85
 
97
86
static inline void hash_free_elements(HASH *hash)
111
100
  Free memory used by hash.
112
101
 
113
102
  SYNOPSIS
114
 
  hash_free()
115
 
  hash   the hash to delete elements of
 
103
    hash_free()
 
104
    hash   the hash to delete elements of
116
105
 
117
106
  NOTES: Hash can't be reused without calling hash_init again.
118
107
*/
119
108
 
120
109
void hash_free(HASH *hash)
121
110
{
 
111
  DBUG_ENTER("hash_free");
 
112
  DBUG_PRINT("enter",("hash: 0x%lx", (long) hash));
 
113
 
122
114
  hash_free_elements(hash);
123
115
  hash->free= 0;
124
116
  delete_dynamic(&hash->array);
 
117
  DBUG_VOID_RETURN;
 
118
}
 
119
 
 
120
 
 
121
/*
 
122
  Delete all elements from the hash (the hash itself is to be reused).
 
123
 
 
124
  SYNOPSIS
 
125
    my_hash_reset()
 
126
    hash   the hash to delete elements of
 
127
*/
 
128
 
 
129
void my_hash_reset(HASH *hash)
 
130
{
 
131
  DBUG_ENTER("my_hash_reset");
 
132
  DBUG_PRINT("enter",("hash: 0x%lxd", (long) hash));
 
133
 
 
134
  hash_free_elements(hash);
 
135
  reset_dynamic(&hash->array);
 
136
  /* Set row pointers so that the hash can be reused at once */
 
137
  hash->blength= 1;
 
138
  DBUG_VOID_RETURN;
125
139
}
126
140
 
127
141
/* some helper functions */
128
142
 
129
143
/*
130
 
  This function is char* instead of unsigned char* as HPUX11 compiler can't
 
144
  This function is char* instead of uchar* as HPUX11 compiler can't
131
145
  handle inline functions that are not defined as native types
132
146
*/
133
147
 
134
148
static inline char*
135
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
136
 
         bool first)
 
149
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
150
         my_bool first)
137
151
{
138
152
  if (hash->get_key)
139
153
    return (char*) (*hash->get_key)(record,length,first);
141
155
  return (char*) record+hash->key_offset;
142
156
}
143
157
 
144
 
/* Calculate pos according to keys */
 
158
        /* Calculate pos according to keys */
145
159
 
146
 
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
 
160
static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
147
161
{
148
162
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
149
163
  return (hashnr & ((buffmax >> 1) -1));
150
164
}
151
165
 
152
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
153
 
                              uint32_t buffmax, uint32_t maxlength)
 
166
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
167
                          uint buffmax, uint maxlength)
154
168
{
155
169
  size_t length;
156
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
170
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
157
171
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
158
172
}
159
173
 
160
174
 
161
175
 
 
176
/* for compilers which can not handle inline */
162
177
static
 
178
#if !defined(__USLC__) && !defined(__sgi)
163
179
inline
164
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
180
#endif
 
181
unsigned int rec_hashnr(HASH *hash,const uchar *record)
165
182
{
166
183
  size_t length;
167
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
184
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
168
185
  return calc_hash(hash,key,length);
169
186
}
170
187
 
171
188
 
172
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
173
 
                           size_t length)
 
189
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
174
190
{
175
191
  HASH_SEARCH_STATE state;
176
192
  return hash_first(hash, key, length, &state);
180
196
  Search after a record based on a key
181
197
 
182
198
  NOTE
183
 
  Assigns the number of the found record to HASH_SEARCH_STATE state
 
199
   Assigns the number of the found record to HASH_SEARCH_STATE state
184
200
*/
185
201
 
186
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
187
 
                          size_t length,
188
 
                          HASH_SEARCH_STATE *current_record)
 
202
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
 
203
                HASH_SEARCH_STATE *current_record)
189
204
{
190
205
  HASH_LINK *pos;
191
 
  uint32_t flag,idx;
 
206
  uint flag,idx;
 
207
  DBUG_ENTER("hash_first");
192
208
 
193
209
  flag=1;
194
210
  if (hash->records)
195
211
  {
196
212
    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
197
 
                  hash->blength,hash->records);
 
213
                    hash->blength,hash->records);
198
214
    do
199
215
    {
200
216
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
201
217
      if (!hashcmp(hash,pos,key,length))
202
218
      {
203
 
        *current_record= idx;
204
 
        return (pos->data);
 
219
        DBUG_PRINT("exit",("found key at %d",idx));
 
220
        *current_record= idx;
 
221
        DBUG_RETURN (pos->data);
205
222
      }
206
223
      if (flag)
207
224
      {
208
 
        /* Reset flag */
209
 
        flag=0;
210
 
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
211
 
          /* Wrong link */
212
 
          break;
 
225
        flag=0;                                 /* Reset flag */
 
226
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
227
          break;                                /* Wrong link */
213
228
      }
214
229
    }
215
230
    while ((idx=pos->next) != NO_RECORD);
216
231
  }
217
232
  *current_record= NO_RECORD;
218
 
  return(0);
 
233
  DBUG_RETURN(0);
219
234
}
220
235
 
221
 
/* Get next record with identical key */
222
 
/* 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 */
223
238
 
224
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
225
 
                         size_t length,
226
 
                         HASH_SEARCH_STATE *current_record)
 
239
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
 
240
               HASH_SEARCH_STATE *current_record)
227
241
{
228
242
  HASH_LINK *pos;
229
 
  uint32_t idx;
 
243
  uint idx;
230
244
 
231
245
  if (*current_record != NO_RECORD)
232
246
  {
236
250
      pos=data+idx;
237
251
      if (!hashcmp(hash,pos,key,length))
238
252
      {
239
 
        *current_record= idx;
240
 
        return pos->data;
 
253
        *current_record= idx;
 
254
        return pos->data;
241
255
      }
242
256
    }
243
257
    *current_record= NO_RECORD;
246
260
}
247
261
 
248
262
 
249
 
/* Change link from pos to new_link */
 
263
        /* Change link from pos to new_link */
250
264
 
251
 
static void movelink(HASH_LINK *array, uint32_t find,
252
 
                     uint32_t next_link, uint32_t newlink)
 
265
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
253
266
{
254
267
  HASH_LINK *old_link;
255
268
  do
265
278
  Compare a key in a record to a whole key. Return 0 if identical
266
279
 
267
280
  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
 
281
    hashcmp()
 
282
    hash   hash table
 
283
    pos    position of hash record to use in comparison
 
284
    key    key for comparison
 
285
    length length of key
273
286
 
274
287
  NOTES:
275
 
  If length is 0, comparison is done using the length of the
276
 
  record being compared against.
 
288
    If length is 0, comparison is done using the length of the
 
289
    record being compared against.
277
290
 
278
291
  RETURN
279
 
  = 0  key of record == key
280
 
  != 0 key of record != key
281
 
*/
 
292
    = 0  key of record == key
 
293
    != 0 key of record != key
 
294
 */
282
295
 
283
 
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
 
296
static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
284
297
                   size_t length)
285
298
{
286
299
  size_t rec_keylength;
287
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
288
 
                                                    &rec_keylength,1);
 
300
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
289
301
  return ((length && length != rec_keylength) ||
290
 
          my_strnncoll(hash->charset, rec_key, rec_keylength,
291
 
                       key, rec_keylength));
 
302
          my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,
 
303
                       (uchar*) key, rec_keylength));
292
304
}
293
305
 
294
306
 
295
 
/* Write a hash-key to the hash-index */
 
307
        /* Write a hash-key to the hash-index */
296
308
 
297
 
bool my_hash_insert(HASH *info,const unsigned char *record)
 
309
my_bool my_hash_insert(HASH *info,const uchar *record)
298
310
{
299
311
  int flag;
300
312
  size_t idx;
301
 
  uint32_t halfbuff,hash_nr,first_index;
302
 
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
303
 
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
 
313
  uint halfbuff,hash_nr,first_index;
 
314
  uchar *ptr_to_rec,*ptr_to_rec2;
 
315
  HASH_LINK *data,*empty,*gpos,*gpos2,*pos;
304
316
 
305
317
  if (HASH_UNIQUE & info->flags)
306
318
  {
307
 
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
 
319
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
308
320
    if (hash_search(info, key, idx))
309
 
      /* Duplicate entry */
310
 
      return(true);
 
321
      return(TRUE);                             /* Duplicate entry */
311
322
  }
312
323
 
313
324
  flag=0;
314
325
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
315
 
    /* No more memory */
316
 
    return(true);
 
326
    return(TRUE);                               /* No more memory */
317
327
 
318
328
  data=dynamic_element(&info->array,0,HASH_LINK*);
319
329
  halfbuff= info->blength >> 1;
320
330
 
321
 
  idx= first_index= info->records-halfbuff;
322
 
  /* If some records */
323
 
  if (idx != info->records)
 
331
  idx=first_index=info->records-halfbuff;
 
332
  if (idx != info->records)                             /* If some records */
324
333
  {
325
334
    do
326
335
    {
327
336
      pos=data+idx;
328
337
      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;
 
338
      if (flag == 0)                            /* First loop; Check if ok */
 
339
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
340
          break;
333
341
      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
 
        }
 
342
      {                                         /* Key will not move */
 
343
        if (!(flag & LOWFIND))
 
344
        {
 
345
          if (flag & HIGHFIND)
 
346
          {
 
347
            flag=LOWFIND | HIGHFIND;
 
348
            /* key shall be moved to the current empty position */
 
349
            gpos=empty;
 
350
            ptr_to_rec=pos->data;
 
351
            empty=pos;                          /* This place is now free */
 
352
          }
 
353
          else
 
354
          {
 
355
            flag=LOWFIND | LOWUSED;             /* key isn't changed */
 
356
            gpos=pos;
 
357
            ptr_to_rec=pos->data;
 
358
          }
 
359
        }
 
360
        else
 
361
        {
 
362
          if (!(flag & LOWUSED))
 
363
          {
 
364
            /* Change link of previous LOW-key */
 
365
            gpos->data=ptr_to_rec;
 
366
            gpos->next= (uint) (pos-data);
 
367
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
 
368
          }
 
369
          gpos=pos;
 
370
          ptr_to_rec=pos->data;
 
371
        }
367
372
      }
368
373
      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
 
        }
 
374
      {                                         /* key will be moved */
 
375
        if (!(flag & HIGHFIND))
 
376
        {
 
377
          flag= (flag & LOWFIND) | HIGHFIND;
 
378
          /* key shall be moved to the last (empty) position */
 
379
          gpos2 = empty; empty=pos;
 
380
          ptr_to_rec2=pos->data;
 
381
        }
 
382
        else
 
383
        {
 
384
          if (!(flag & HIGHUSED))
 
385
          {
 
386
            /* Change link of previous hash-key and save */
 
387
            gpos2->data=ptr_to_rec2;
 
388
            gpos2->next=(uint) (pos-data);
 
389
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
 
390
          }
 
391
          gpos2=pos;
 
392
          ptr_to_rec2=pos->data;
 
393
        }
390
394
      }
391
395
    }
392
396
    while ((idx=pos->next) != NO_RECORD);
408
412
  pos=data+idx;
409
413
  if (pos == empty)
410
414
  {
411
 
    pos->data=(unsigned char*) record;
 
415
    pos->data=(uchar*) record;
412
416
    pos->next=NO_RECORD;
413
417
  }
414
418
  else
418
422
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
419
423
    if (pos == gpos)
420
424
    {
421
 
      pos->data=(unsigned char*) record;
422
 
      pos->next=(uint32_t) (empty - data);
 
425
      pos->data=(uchar*) record;
 
426
      pos->next=(uint) (empty - data);
423
427
    }
424
428
    else
425
429
    {
426
 
      pos->data=(unsigned char*) record;
 
430
      pos->data=(uchar*) record;
427
431
      pos->next=NO_RECORD;
428
 
      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
 
432
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
429
433
    }
430
434
  }
431
435
  if (++info->records == info->blength)
435
439
 
436
440
 
437
441
/******************************************************************************
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
 
 *****************************************************************************/
 
442
** Remove one record from hash-table. The record with the same record
 
443
** ptr is removed.
 
444
** if there is a free-function it's called for record if found
 
445
******************************************************************************/
442
446
 
443
 
bool hash_delete(HASH *hash,unsigned char *record)
 
447
my_bool hash_delete(HASH *hash,uchar *record)
444
448
{
445
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
449
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
446
450
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
 
451
  DBUG_ENTER("hash_delete");
447
452
  if (!hash->records)
448
 
    return(1);
 
453
    DBUG_RETURN(1);
449
454
 
450
455
  blength=hash->blength;
451
456
  data=dynamic_element(&hash->array,0,HASH_LINK*);
457
462
  {
458
463
    gpos=pos;
459
464
    if (pos->next == NO_RECORD)
460
 
      /* Key not found */
461
 
      return(1);
462
 
 
 
465
      DBUG_RETURN(1);                   /* Key not found */
463
466
    pos=data+pos->next;
464
467
  }
465
468
 
467
470
  lastpos=data+hash->records;
468
471
 
469
472
  /* Remove link to record */
470
 
  empty=pos; empty_index=(uint32_t) (empty-data);
 
473
  empty=pos; empty_index=(uint) (empty-data);
471
474
  if (gpos)
472
 
    /* unlink current ptr */
473
 
    gpos->next=pos->next;
 
475
    gpos->next=pos->next;               /* unlink current ptr */
474
476
  else if (pos->next != NO_RECORD)
475
477
  {
476
478
    empty=data+(empty_index=pos->next);
478
480
    pos->next=empty->next;
479
481
  }
480
482
 
481
 
  /* last key at wrong pos or no next link */
482
 
  if (empty == lastpos)
 
483
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
483
484
    goto exit;
484
485
 
485
486
  /* Move the last key (lastpos) */
486
487
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
487
488
  /* pos is where lastpos should be */
488
489
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
489
 
  /* Move to empty position. */
490
 
  if (pos == empty)
 
490
  if (pos == empty)                     /* Move to empty position. */
491
491
  {
492
492
    empty[0]=lastpos[0];
493
493
    goto exit;
499
499
  {                                     /* pos is on wrong posit */
500
500
    empty[0]=pos[0];                    /* Save it here */
501
501
    pos[0]=lastpos[0];                  /* This should be here */
502
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
 
502
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
503
503
    goto exit;
504
504
  }
505
505
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
508
508
    if (pos2 != hash->records)
509
509
    {
510
510
      empty[0]=lastpos[0];
511
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
 
511
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
512
512
      goto exit;
513
513
    }
514
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
 
514
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
515
515
  }
516
516
  else idx= NO_RECORD;          /* Different positions merge */
517
517
 
520
520
  pos->next=empty_index;
521
521
 
522
522
exit:
523
 
  pop_dynamic(&hash->array);
 
523
  VOID(pop_dynamic(&hash->array));
524
524
  if (hash->free)
525
 
    (*hash->free)((unsigned char*) record);
526
 
  return(0);
527
 
}
528
 
 
529
 
unsigned char *hash_element(HASH *hash,uint32_t idx)
 
525
    (*hash->free)((uchar*) record);
 
526
  DBUG_RETURN(0);
 
527
}
 
528
 
 
529
        /*
 
530
          Update keys when record has changed.
 
531
          This is much more efficent than using a delete & insert.
 
532
          */
 
533
 
 
534
my_bool hash_update(HASH *hash, uchar *record, uchar *old_key,
 
535
                    size_t old_key_length)
 
536
{
 
537
  uint new_index,new_pos_index,blength,records,empty;
 
538
  size_t idx;
 
539
  HASH_LINK org_link,*data,*previous,*pos;
 
540
  DBUG_ENTER("hash_update");
 
541
  
 
542
  if (HASH_UNIQUE & hash->flags)
 
543
  {
 
544
    HASH_SEARCH_STATE state;
 
545
    uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);
 
546
    if ((found= hash_first(hash, new_key, idx, &state)))
 
547
    {
 
548
      do 
 
549
      {
 
550
        if (found != record)
 
551
          DBUG_RETURN(1);               /* Duplicate entry */
 
552
      } 
 
553
      while ((found= hash_next(hash, new_key, idx, &state)));
 
554
    }
 
555
  }
 
556
 
 
557
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
558
  blength=hash->blength; records=hash->records;
 
559
 
 
560
  /* Search after record with key */
 
561
 
 
562
  idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?
 
563
                                              old_key_length :
 
564
                                              hash->key_length)),
 
565
                  blength,records);
 
566
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
 
567
  if (idx == new_index)
 
568
    DBUG_RETURN(0);                     /* Nothing to do (No record check) */
 
569
  previous=0;
 
570
  for (;;)
 
571
  {
 
572
 
 
573
    if ((pos= data+idx)->data == record)
 
574
      break;
 
575
    previous=pos;
 
576
    if ((idx=pos->next) == NO_RECORD)
 
577
      DBUG_RETURN(1);                   /* Not found in links */
 
578
  }
 
579
  org_link= *pos;
 
580
  empty=idx;
 
581
 
 
582
  /* Relink record from current chain */
 
583
 
 
584
  if (!previous)
 
585
  {
 
586
    if (pos->next != NO_RECORD)
 
587
    {
 
588
      empty=pos->next;
 
589
      *pos= data[pos->next];
 
590
    }
 
591
  }
 
592
  else
 
593
    previous->next=pos->next;           /* unlink pos */
 
594
 
 
595
  /* Move data to correct position */
 
596
  if (new_index == empty)
 
597
  {
 
598
    /*
 
599
      At this point record is unlinked from the old chain, thus it holds
 
600
      random position. By the chance this position is equal to position
 
601
      for the first element in the new chain. That means updated record
 
602
      is the only record in the new chain.
 
603
    */
 
604
    if (empty != idx)
 
605
    {
 
606
      /*
 
607
        Record was moved while unlinking it from the old chain.
 
608
        Copy data to a new position.
 
609
      */
 
610
      data[empty]= org_link;
 
611
    }
 
612
    data[empty].next= NO_RECORD;
 
613
    DBUG_RETURN(0);
 
614
  }
 
615
  pos=data+new_index;
 
616
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
 
617
  if (new_index != new_pos_index)
 
618
  {                                     /* Other record in wrong position */
 
619
    data[empty] = *pos;
 
620
    movelink(data,new_index,new_pos_index,empty);
 
621
    org_link.next=NO_RECORD;
 
622
    data[new_index]= org_link;
 
623
  }
 
624
  else
 
625
  {                                     /* Link in chain at right position */
 
626
    org_link.next=data[new_index].next;
 
627
    data[empty]=org_link;
 
628
    data[new_index].next=empty;
 
629
  }
 
630
  DBUG_RETURN(0);
 
631
}
 
632
 
 
633
 
 
634
uchar *hash_element(HASH *hash,ulong idx)
530
635
{
531
636
  if (idx < hash->records)
532
637
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
533
638
  return 0;
534
639
}
535
640
 
536
 
} /* namespace drizzled */
 
641
 
 
642
/*
 
643
  Replace old row with new row.  This should only be used when key
 
644
  isn't changed
 
645
*/
 
646
 
 
647
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)
 
648
{
 
649
  if (*current_record != NO_RECORD)            /* Safety */
 
650
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
 
651
}
 
652
 
 
653
 
 
654
#ifndef DBUG_OFF
 
655
 
 
656
my_bool hash_check(HASH *hash)
 
657
{
 
658
  int error;
 
659
  uint i,rec_link,found,max_links,seek,links,idx;
 
660
  uint records,blength;
 
661
  HASH_LINK *data,*hash_info;
 
662
 
 
663
  records=hash->records; blength=hash->blength;
 
664
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
665
  error=0;
 
666
 
 
667
  for (i=found=max_links=seek=0 ; i < records ; i++)
 
668
  {
 
669
    if (hash_rec_mask(hash,data+i,blength,records) == i)
 
670
    {
 
671
      found++; seek++; links=1;
 
672
      for (idx=data[i].next ;
 
673
           idx != NO_RECORD && found < records + 1;
 
674
           idx=hash_info->next)
 
675
      {
 
676
        if (idx >= records)
 
677
        {
 
678
          DBUG_PRINT("error",
 
679
                     ("Found pointer outside array to %d from link starting at %d",
 
680
                      idx,i));
 
681
          error=1;
 
682
        }
 
683
        hash_info=data+idx;
 
684
        seek+= ++links;
 
685
        if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i)
 
686
        {
 
687
          DBUG_PRINT("error",
 
688
                     ("Record in wrong link at %d: Start %d  Record: 0x%lx  Record-link %d",
 
689
                      idx, i, (long) hash_info->data, rec_link));
 
690
          error=1;
 
691
        }
 
692
        else
 
693
          found++;
 
694
      }
 
695
      if (links > max_links) max_links=links;
 
696
    }
 
697
  }
 
698
  if (found != records)
 
699
  {
 
700
    DBUG_PRINT("error",("Found %u of %u records", found, records));
 
701
    error=1;
 
702
  }
 
703
  if (records)
 
704
    DBUG_PRINT("info",
 
705
               ("records: %u   seeks: %d   max links: %d   hitrate: %.2f",
 
706
                records,seek,max_links,(float) seek / (float) records));
 
707
  return error;
 
708
}
 
709
#endif