← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.c

  • Committer: Monty Taylor
  • Date: 2008-09-05 22:55:50 UTC
  • mfrom: (373.1.9 stl-client-progs)
  • Revision ID: monty@inaugust.com-20080905225550-zco374c9s7kxwqyb
Merged removal of DYNAMIC_STRING.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/hash.c
29
29
#define HIGHUSED 8
30
30
 
31
31
typedef struct st_hash_info {
32
 
  uint32_t next;                                        /* index to next key */
33
 
  unsigned char *data;                                  /* data for current entry */
 
32
  uint next;                                    /* index to next key */
 
33
  uchar *data;                                  /* data for current entry */
34
34
} HASH_LINK;
35
35
 
36
 
static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength);
37
 
static void movelink(HASH_LINK *array,uint32_t pos,uint32_t next_link,uint32_t newlink);
38
 
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,
39
39
                   size_t length);
40
40
 
41
 
static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length)
 
41
static uint calc_hash(const HASH *hash, const uchar *key, size_t length)
42
42
{
43
43
  uint32_t nr1=1, nr2=4;
44
 
  hash->charset->coll->hash_sort(hash->charset,(const unsigned char*) key,length,&nr1,&nr2);
 
44
  hash->charset->coll->hash_sort(hash->charset,(const uchar*) key,length,&nr1,&nr2);
45
45
  return nr1;
46
46
}
47
47
 
48
48
bool
49
 
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
 
49
_hash_init(HASH *hash,uint growth_size, const CHARSET_INFO * const charset,
50
50
           uint32_t size, size_t key_offset, size_t key_length,
51
51
           hash_get_key get_key,
52
 
           void (*free_element)(void*),uint32_t flags CALLER_INFO_PROTO)
 
52
           void (*free_element)(void*),uint flags CALLER_INFO_PROTO)
53
53
{
54
54
  hash->records=0;
55
55
  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,
132
132
/* some helper functions */
133
133
 
134
134
/*
135
 
  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
136
136
  handle inline functions that are not defined as native types
137
137
*/
138
138
 
139
139
static inline char*
140
 
hash_key(const HASH *hash, const unsigned char *record, size_t *length,
 
140
hash_key(const HASH *hash, const uchar *record, size_t *length,
141
141
         bool first)
142
142
{
143
143
  if (hash->get_key)
148
148
 
149
149
        /* Calculate pos according to keys */
150
150
 
151
 
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)
152
152
{
153
153
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
154
154
  return (hashnr & ((buffmax >> 1) -1));
155
155
}
156
156
 
157
 
static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
158
 
                          uint32_t buffmax, uint32_t maxlength)
 
157
static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,
 
158
                          uint buffmax, uint maxlength)
159
159
{
160
160
  size_t length;
161
 
  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
 
161
  uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);
162
162
  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
163
163
}
164
164
 
169
169
#if !defined(__USLC__) && !defined(__sgi)
170
170
inline
171
171
#endif
172
 
unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
 
172
unsigned int rec_hashnr(HASH *hash,const uchar *record)
173
173
{
174
174
  size_t length;
175
 
  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
 
175
  uchar *key= (uchar*) hash_key(hash,record,&length,0);
176
176
  return calc_hash(hash,key,length);
177
177
}
178
178
 
179
179
 
180
 
unsigned char* hash_search(const HASH *hash, const unsigned char *key, size_t length)
 
180
uchar* hash_search(const HASH *hash, const uchar *key, size_t length)
181
181
{
182
182
  HASH_SEARCH_STATE state;
183
183
  return hash_first(hash, key, length, &state);
190
190
   Assigns the number of the found record to HASH_SEARCH_STATE state
191
191
*/
192
192
 
193
 
unsigned char* hash_first(const HASH *hash, const unsigned char *key, size_t length,
 
193
uchar* hash_first(const HASH *hash, const uchar *key, size_t length,
194
194
                HASH_SEARCH_STATE *current_record)
195
195
{
196
196
  HASH_LINK *pos;
197
 
  uint32_t flag,idx;
 
197
  uint flag,idx;
198
198
 
199
199
  flag=1;
200
200
  if (hash->records)
225
225
        /* Get next record with identical key */
226
226
        /* Can only be called if previous calls was hash_search */
227
227
 
228
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key, size_t length,
 
228
uchar* hash_next(const HASH *hash, const uchar *key, size_t length,
229
229
               HASH_SEARCH_STATE *current_record)
230
230
{
231
231
  HASH_LINK *pos;
232
 
  uint32_t idx;
 
232
  uint idx;
233
233
 
234
234
  if (*current_record != NO_RECORD)
235
235
  {
251
251
 
252
252
        /* Change link from pos to new_link */
253
253
 
254
 
static void movelink(HASH_LINK *array,uint32_t find,uint32_t next_link,uint32_t newlink)
 
254
static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
255
255
{
256
256
  HASH_LINK *old_link;
257
257
  do
282
282
    != 0 key of record != key
283
283
 */
284
284
 
285
 
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,
286
286
                   size_t length)
287
287
{
288
288
  size_t rec_keylength;
289
 
  unsigned char *rec_key= (unsigned char*) hash_key(hash,pos->data,&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, (const unsigned char*) rec_key, rec_keylength,
292
 
                       (const unsigned char*) 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
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
310
      return(true);                             /* Duplicate entry */
311
311
  }
401
401
  pos=data+idx;
402
402
  if (pos == empty)
403
403
  {
404
 
    pos->data=(unsigned char*) record;
 
404
    pos->data=(uchar*) record;
405
405
    pos->next=NO_RECORD;
406
406
  }
407
407
  else
411
411
    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
412
412
    if (pos == gpos)
413
413
    {
414
 
      pos->data=(unsigned char*) record;
 
414
      pos->data=(uchar*) record;
415
415
      pos->next=(uint) (empty - data);
416
416
    }
417
417
    else
418
418
    {
419
 
      pos->data=(unsigned char*) record;
 
419
      pos->data=(uchar*) record;
420
420
      pos->next=NO_RECORD;
421
421
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
422
422
    }
433
433
** if there is a free-function it's called for record if found
434
434
******************************************************************************/
435
435
 
436
 
bool hash_delete(HASH *hash,unsigned char *record)
 
436
bool hash_delete(HASH *hash,uchar *record)
437
437
{
438
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
 
438
  uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
439
439
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
440
440
  if (!hash->records)
441
441
    return(1);
508
508
  pos->next=empty_index;
509
509
 
510
510
exit:
511
 
  pop_dynamic(&hash->array);
 
511
  VOID(pop_dynamic(&hash->array));
512
512
  if (hash->free)
513
 
    (*hash->free)((unsigned char*) record);
 
513
    (*hash->free)((uchar*) record);
514
514
  return(0);
515
515
}
516
516
 
519
519
          This is much more efficent than using a delete & insert.
520
520
          */
521
521
 
522
 
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
 
522
bool hash_update(HASH *hash, uchar *record, uchar *old_key,
523
523
                    size_t old_key_length)
524
524
{
525
 
  uint32_t new_index,new_pos_index,blength,records,empty;
 
525
  uint new_index,new_pos_index,blength,records,empty;
526
526
  size_t idx;
527
527
  HASH_LINK org_link,*data,*previous,*pos;
528
528
  
529
529
  if (HASH_UNIQUE & hash->flags)
530
530
  {
531
531
    HASH_SEARCH_STATE state;
532
 
    unsigned char *found, *new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
 
532
    uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);
533
533
    if ((found= hash_first(hash, new_key, idx, &state)))
534
534
    {
535
535
      do 
618
618
}
619
619
 
620
620
 
621
 
unsigned char *hash_element(HASH *hash,uint32_t idx)
 
621
uchar *hash_element(HASH *hash,uint32_t idx)
622
622
{
623
623
  if (idx < hash->records)
624
624
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
631
631
  isn't changed
632
632
*/
633
633
 
634
 
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, unsigned char *new_row)
 
634
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)
635
635
{
636
636
  if (*current_record != NO_RECORD)            /* Safety */
637
637
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;