← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/my_hash.cc

merge lp:~linuxjedi/drizzle/trunk-remove-drizzleadmin

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/my_hash.cc
21
21
/* One of key_length or key_length_offset must be given */
22
22
/* Key length of 0 isn't allowed */
23
23
 
24
 
#include "config.h"
25
 
#include "drizzled/my_hash.h"
26
 
#include "drizzled/charset.h"
27
 
#include "drizzled/charset_info.h"
 
24
#include <config.h>
 
25
#include <drizzled/my_hash.h>
 
26
#include <drizzled/charset.h>
 
27
#include <vector>
28
28
 
29
 
namespace drizzled
30
 
{
 
29
namespace drizzled {
31
30
 
32
31
const uint32_t NO_RECORD= UINT32_MAX;
33
32
 
36
35
const int HIGHFIND= 4;
37
36
const int HIGHUSED= 8;
38
37
 
39
 
typedef struct st_hash_info {
40
 
  /* index to next key */
41
 
  uint32_t next;
42
 
  /* data for current entry */
43
 
  unsigned char *data;
44
 
} HASH_LINK;
45
 
 
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,
51
 
                   size_t length);
52
 
 
53
 
static uint32_t calc_hash(const HASH *hash, const unsigned char *key,
54
 
                          size_t length)
 
38
static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength);
 
39
static void movelink(HASH_LINK *array, uint32_t pos, uint32_t next_link, uint32_t newlink);
 
40
static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key, size_t length);
 
41
 
 
42
static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length)
55
43
{
56
44
  uint32_t nr1=1, nr2=4;
57
45
  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
58
46
  return nr1;
59
47
}
60
48
 
 
49
#define dynamic_element(array,array_index,type) ((type)((array)->buffer) +(array_index))
 
50
 
61
51
bool
62
 
_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,
 
52
_hash_init(HASH *hash,uint32_t growth_size, const charset_info_st * const charset,
63
53
           uint32_t size, size_t key_offset, size_t key_length,
64
54
           hash_get_key get_key,
65
55
           hash_free_key free_element, uint32_t flags)
218
208
  return(0);
219
209
}
220
210
 
221
 
/* Get next record with identical key */
222
 
/* Can only be called if previous calls was hash_search */
223
 
 
224
 
unsigned char* hash_next(const HASH *hash, const unsigned char *key,
225
 
                         size_t length,
226
 
                         HASH_SEARCH_STATE *current_record)
227
 
{
228
 
  HASH_LINK *pos;
229
 
  uint32_t idx;
230
 
 
231
 
  if (*current_record != NO_RECORD)
232
 
  {
233
 
    HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
234
 
    for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next)
235
 
    {
236
 
      pos=data+idx;
237
 
      if (!hashcmp(hash,pos,key,length))
238
 
      {
239
 
        *current_record= idx;
240
 
        return pos->data;
241
 
      }
242
 
    }
243
 
    *current_record= NO_RECORD;
244
 
  }
245
 
  return 0;
246
 
}
247
 
 
248
 
 
249
211
/* Change link from pos to new_link */
250
212
 
251
213
static void movelink(HASH_LINK *array, uint32_t find,
433
395
  return(0);
434
396
}
435
397
 
436
 
 
437
 
/******************************************************************************
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
 
 
443
 
bool hash_delete(HASH *hash,unsigned char *record)
444
 
{
445
 
  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
446
 
  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
447
 
  if (!hash->records)
448
 
    return(1);
449
 
 
450
 
  blength=hash->blength;
451
 
  data=dynamic_element(&hash->array,0,HASH_LINK*);
452
 
  /* Search after record with key */
453
 
  pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records);
454
 
  gpos = 0;
455
 
 
456
 
  while (pos->data != record)
457
 
  {
458
 
    gpos=pos;
459
 
    if (pos->next == NO_RECORD)
460
 
      /* Key not found */
461
 
      return(1);
462
 
 
463
 
    pos=data+pos->next;
464
 
  }
465
 
 
466
 
  if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;
467
 
  lastpos=data+hash->records;
468
 
 
469
 
  /* Remove link to record */
470
 
  empty=pos; empty_index=(uint32_t) (empty-data);
471
 
  if (gpos)
472
 
    /* unlink current ptr */
473
 
    gpos->next=pos->next;
474
 
  else if (pos->next != NO_RECORD)
475
 
  {
476
 
    empty=data+(empty_index=pos->next);
477
 
    pos->data=empty->data;
478
 
    pos->next=empty->next;
479
 
  }
480
 
 
481
 
  /* last key at wrong pos or no next link */
482
 
  if (empty == lastpos)
483
 
    goto exit;
484
 
 
485
 
  /* Move the last key (lastpos) */
486
 
  lastpos_hashnr=rec_hashnr(hash,lastpos->data);
487
 
  /* pos is where lastpos should be */
488
 
  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
489
 
  /* Move to empty position. */
490
 
  if (pos == empty)
491
 
  {
492
 
    empty[0]=lastpos[0];
493
 
    goto exit;
494
 
  }
495
 
  pos_hashnr=rec_hashnr(hash,pos->data);
496
 
  /* pos3 is where the pos should be */
497
 
  pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records);
498
 
  if (pos != pos3)
499
 
  {                                     /* pos is on wrong posit */
500
 
    empty[0]=pos[0];                    /* Save it here */
501
 
    pos[0]=lastpos[0];                  /* This should be here */
502
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
503
 
    goto exit;
504
 
  }
505
 
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
506
 
  if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1))
507
 
  {                                     /* Identical key-positions */
508
 
    if (pos2 != hash->records)
509
 
    {
510
 
      empty[0]=lastpos[0];
511
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
512
 
      goto exit;
513
 
    }
514
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
515
 
  }
516
 
  else idx= NO_RECORD;          /* Different positions merge */
517
 
 
518
 
  empty[0]=lastpos[0];
519
 
  movelink(data,idx,empty_index,pos->next);
520
 
  pos->next=empty_index;
521
 
 
522
 
exit:
523
 
  pop_dynamic(&hash->array);
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)
530
 
{
531
 
  if (idx < hash->records)
532
 
    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
533
 
  return 0;
534
 
}
535
 
 
536
398
} /* namespace drizzled */