← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

  • Committer: Stewart Smith
  • Date: 2008-07-13 06:56:15 UTC
  • mto: (210.1.1 drizzle)
  • mto: This revision was merged to the branch mainline in revision 211.
  • Revision ID: stewart@flamingspork.com-20080713065615-vzok75kgnnviokl9
Move MD5() into a UDF

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);
125
 
  return;
 
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;
126
139
}
127
140
 
128
141
/* some helper functions */
129
142
 
130
143
/*
131
 
  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
132
145
  handle inline functions that are not defined as native types
133
146
*/
134
147
 
135
148
static inline char*
136
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
137
 
         bool first)
 
149
hash_key(const HASH *hash, const uchar *record, size_t *length,
 
150
         my_bool first)
138
151
{
139
152
  if (hash->get_key)
140
153
    return (char*) (*hash->get_key)(record,length,first);
142
155
  return (char*) record+hash->key_offset;
143
156
}
144
157
 
145
 
/* Calculate pos according to keys */
 
158
        /* Calculate pos according to keys */
146
159
 
147
 
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)
148
161
{
149
162
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
150
163
  return (hashnr & ((buffmax >> 1) -1));
151
164
}
152
165
 
153
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
154
 
                              uint32_t buffmax, uint32_t maxlength)
 
166
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
167
                          uint buffmax, uint maxlength)
155
168
{
156
169
  size_t length;
157
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
170
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
158
171
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
159
172
}
160
173
 
161
174
 
162
175
 
 
176
/* for compilers which can not handle inline */
163
177
static
 
178
#if !defined(__USLC__) && !defined(__sgi)
164
179
inline
165
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
180
#endif
 
181
unsigned int rec_hashnr(HASH *hash,const uchar *record)
166
182
{
167
183
  size_t length;
168
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
184
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
169
185
  return calc_hash(hash,key,length);
170
186
}
171
187
 
172
188
 
173
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key,
174
 
                           size_t length)
 
189
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
175
190
{
176
191
  HASH_SEARCH_STATE state;
177
192
  return hash_first(hash, key, length, &state);
181
196
  Search after a record based on a key
182
197
 
183
198
  NOTE
184
 
  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
185
200
*/
186
201
 
187
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key,
188
 
                          size_t length,
189
 
                          HASH_SEARCH_STATE *current_record)
 
202
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
 
203
                HASH_SEARCH_STATE *current_record)
190
204
{
191
205
  HASH_LINK *pos;
192
 
  uint32_t flag,idx;
 
206
  uint flag,idx;
 
207
  DBUG_ENTER("hash_first");
193
208
 
194
209
  flag=1;
195
210
  if (hash->records)
196
211
  {
197
212
    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
198
 
                  hash->blength,hash->records);
 
213
                    hash->blength,hash->records);
199
214
    do
200
215
    {
201
216
      pos= dynamic_element(&hash->array,idx,HASH_LINK*);
202
217
      if (!hashcmp(hash,pos,key,length))
203
218
      {
204
 
        *current_record= idx;
205
 
        return (pos->data);
 
219
        DBUG_PRINT("exit",("found key at %d",idx));
 
220
        *current_record= idx;
 
221
        DBUG_RETURN (pos->data);
206
222
      }
207
223
      if (flag)
208
224
      {
209
 
        /* Reset flag */
210
 
        flag=0;
211
 
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
212
 
          /* Wrong link */
213
 
          break;
 
225
        flag=0;                                 /* Reset flag */
 
226
        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
 
227
          break;                                /* Wrong link */
214
228
      }
215
229
    }
216
230
    while ((idx=pos->next) != NO_RECORD);
217
231
  }
218
232
  *current_record= NO_RECORD;
219
 
  return(0);
 
233
  DBUG_RETURN(0);
220
234
}
221
235
 
222
 
/* Get next record with identical key */
223
 
/* 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 */
224
238
 
225
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
226
 
                         size_t length,
227
 
                         HASH_SEARCH_STATE *current_record)
 
239
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
 
240
               HASH_SEARCH_STATE *current_record)
228
241
{
229
242
  HASH_LINK *pos;
230
 
  uint32_t idx;
 
243
  uint idx;
231
244
 
232
245
  if (*current_record != NO_RECORD)
233
246
  {
237
250
      pos=data+idx;
238
251
      if (!hashcmp(hash,pos,key,length))
239
252
      {
240
 
        *current_record= idx;
241
 
        return pos->data;
 
253
        *current_record= idx;
 
254
        return pos->data;
242
255
      }
243
256
    }
244
257
    *current_record= NO_RECORD;
247
260
}
248
261
 
249
262
 
250
 
/* Change link from pos to new_link */
 
263
        /* Change link from pos to new_link */
251
264
 
252
 
static void movelink(HASH_LINK *array, uint32_t find,
253
 
                     uint32_t next_link, uint32_t newlink)
 
265
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
254
266
{
255
267
  HASH_LINK *old_link;
256
268
  do
266
278
  Compare a key in a record to a whole key. Return 0 if identical
267
279
 
268
280
  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
 
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
274
286
 
275
287
  NOTES:
276
 
  If length is 0, comparison is done using the length of the
277
 
  record being compared against.
 
288
    If length is 0, comparison is done using the length of the
 
289
    record being compared against.
278
290
 
279
291
  RETURN
280
 
  = 0  key of record == key
281
 
  != 0 key of record != key
282
 
*/
 
292
    = 0  key of record == key
 
293
    != 0 key of record != key
 
294
 */
283
295
 
284
 
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,
285
297
                   size_t length)
286
298
{
287
299
  size_t rec_keylength;
288
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
289
 
                                                    &rec_keylength,1);
 
300
  uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);
290
301
  return ((length && length != rec_keylength) ||
291
 
          my_strnncoll(hash->charset, rec_key, rec_keylength,
292
 
                       key, rec_keylength));
 
302
          my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,
 
303
                       (uchar*) key, rec_keylength));
293
304
}
294
305
 
295
306
 
296
 
/* Write a hash-key to the hash-index */
 
307
        /* Write a hash-key to the hash-index */
297
308
 
298
 
bool my_hash_insert(HASH *info,const unsigned char *record)
 
309
my_bool my_hash_insert(HASH *info,const uchar *record)
299
310
{
300
311
  int flag;
301
312
  size_t idx;
302
 
  uint32_t halfbuff,hash_nr,first_index;
303
 
  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
 
313
  uint halfbuff,hash_nr,first_index;
 
314
  uchar *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
304
315
  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
305
316
 
306
317
  if (HASH_UNIQUE & info->flags)
307
318
  {
308
 
    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
 
319
    uchar *key= (uchar*) hash_key(info, record, &idx, 1);
309
320
    if (hash_search(info, key, idx))
310
 
      /* Duplicate entry */
311
 
      return(true);
 
321
      return(TRUE);                             /* Duplicate entry */
312
322
  }
313
323
 
314
324
  flag=0;
315
325
  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
316
 
    /* No more memory */
317
 
    return(true);
 
326
    return(TRUE);                               /* No more memory */
318
327
 
319
328
  data=dynamic_element(&info->array,0,HASH_LINK*);
320
329
  halfbuff= info->blength >> 1;
321
330
 
322
 
  idx= first_index= info->records-halfbuff;
323
 
  /* If some records */
324
 
  if (idx != info->records)
 
331
  idx=first_index=info->records-halfbuff;
 
332
  if (idx != info->records)                             /* If some records */
325
333
  {
326
334
    do
327
335
    {
328
336
      pos=data+idx;
329
337
      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;
 
338
      if (flag == 0)                            /* First loop; Check if ok */
 
339
        if (hash_mask(hash_nr,info->blength,info->records) != first_index)
 
340
          break;
334
341
      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
 
        }
 
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
        }
368
372
      }
369
373
      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
 
        }
 
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
        }
391
394
      }
392
395
    }
393
396
    while ((idx=pos->next) != NO_RECORD);
409
412
  pos=data+idx;
410
413
  if (pos == empty)
411
414
  {
412
 
    pos->data=(unsigned char*) record;
 
415
    pos->data=(uchar*) record;
413
416
    pos->next=NO_RECORD;
414
417
  }
415
418
  else
419
422
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
420
423
    if (pos == gpos)
421
424
    {
422
 
      pos->data=(unsigned char*) record;
423
 
      pos->next=(uint32_t) (empty - data);
 
425
      pos->data=(uchar*) record;
 
426
      pos->next=(uint) (empty - data);
424
427
    }
425
428
    else
426
429
    {
427
 
      pos->data=(unsigned char*) record;
 
430
      pos->data=(uchar*) record;
428
431
      pos->next=NO_RECORD;
429
 
      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));
430
433
    }
431
434
  }
432
435
  if (++info->records == info->blength)
436
439
 
437
440
 
438
441
/******************************************************************************
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
 
 *****************************************************************************/
 
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
******************************************************************************/
443
446
 
444
 
bool hash_delete(HASH *hash,unsigned char *record)
 
447
my_bool hash_delete(HASH *hash,uchar *record)
445
448
{
446
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
449
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
447
450
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
 
451
  DBUG_ENTER("hash_delete");
448
452
  if (!hash->records)
449
 
    return(1);
 
453
    DBUG_RETURN(1);
450
454
 
451
455
  blength=hash->blength;
452
456
  data=dynamic_element(&hash->array,0,HASH_LINK*);
458
462
  {
459
463
    gpos=pos;
460
464
    if (pos->next == NO_RECORD)
461
 
      /* Key not found */
462
 
      return(1);
463
 
 
 
465
      DBUG_RETURN(1);                   /* Key not found */
464
466
    pos=data+pos->next;
465
467
  }
466
468
 
468
470
  lastpos=data+hash->records;
469
471
 
470
472
  /* Remove link to record */
471
 
  empty=pos; empty_index=(uint32_t) (empty-data);
 
473
  empty=pos; empty_index=(uint) (empty-data);
472
474
  if (gpos)
473
 
    /* unlink current ptr */
474
 
    gpos->next=pos->next;
 
475
    gpos->next=pos->next;               /* unlink current ptr */
475
476
  else if (pos->next != NO_RECORD)
476
477
  {
477
478
    empty=data+(empty_index=pos->next);
479
480
    pos->next=empty->next;
480
481
  }
481
482
 
482
 
  /* last key at wrong pos or no next link */
483
 
  if (empty == lastpos)
 
483
  if (empty == lastpos)                 /* last key at wrong pos or no next link */
484
484
    goto exit;
485
485
 
486
486
  /* Move the last key (lastpos) */
487
487
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
488
488
  /* pos is where lastpos should be */
489
489
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
490
 
  /* Move to empty position. */
491
 
  if (pos == empty)
 
490
  if (pos == empty)                     /* Move to empty position. */
492
491
  {
493
492
    empty[0]=lastpos[0];
494
493
    goto exit;
500
499
  {                                     /* pos is on wrong posit */
501
500
    empty[0]=pos[0];                    /* Save it here */
502
501
    pos[0]=lastpos[0];                  /* This should be here */
503
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
 
502
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
504
503
    goto exit;
505
504
  }
506
505
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
509
508
    if (pos2 != hash->records)
510
509
    {
511
510
      empty[0]=lastpos[0];
512
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
 
511
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
513
512
      goto exit;
514
513
    }
515
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
 
514
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
516
515
  }
517
516
  else idx= NO_RECORD;          /* Different positions merge */
518
517
 
521
520
  pos->next=empty_index;
522
521
 
523
522
exit:
524
 
  pop_dynamic(&hash->array);
 
523
  VOID(pop_dynamic(&hash->array));
525
524
  if (hash->free)
526
 
    (*hash->free)((unsigned char*) record);
527
 
  return(0);
528
 
}
529
 
 
530
 
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)
531
635
{
532
636
  if (idx < hash->records)
533
637
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
534
638
  return 0;
535
639
}
536
640
 
537
 
} /* 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