← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.cc

  • Committer: Lee
  • Date: 2009-01-01 03:07:33 UTC
  • mto: (758.1.3 devel)
  • mto: This revision was merged to the branch mainline in revision 759.
  • Revision ID: lbieber@lbieber-desktop-20090101030733-fb411b55f07vij8q
more header file cleanup

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/hash.cc
1
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
3
 *
4
 
 *  Copyright (C) 2008 Sun Microsystems, Inc.
 
4
 *  Copyright (C) 2008 Sun Microsystems
5
5
 *
6
6
 *  This program is free software; you can redistribute it and/or modify
7
7
 *  it under the terms of the GNU General Public License as published by
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>
28
 
 
29
 
namespace drizzled
30
 
{
 
24
#include <drizzled/global.h>
 
25
#include CSTDINT_H
 
26
#include <mysys/hash.h>
31
27
 
32
28
const uint32_t NO_RECORD= UINT32_MAX;
33
29
 
122
118
  hash_free_elements(hash);
123
119
  hash->free= 0;
124
120
  delete_dynamic(&hash->array);
 
121
  return;
 
122
}
 
123
 
 
124
 
 
125
/*
 
126
  Delete all elements from the hash (the hash itself is to be reused).
 
127
 
 
128
  SYNOPSIS
 
129
  my_hash_reset()
 
130
  hash   the hash to delete elements of
 
131
*/
 
132
 
 
133
void my_hash_reset(HASH *hash)
 
134
{
 
135
  hash_free_elements(hash);
 
136
  reset_dynamic(&hash->array);
 
137
  /* Set row pointers so that the hash can be reused at once */
 
138
  hash->blength= 1;
 
139
  return;
125
140
}
126
141
 
127
142
/* some helper functions */
318
333
  data=dynamic_element(&info->array,0,HASH_LINK*);
319
334
  halfbuff= info->blength >> 1;
320
335
 
321
 
  idx= first_index= info->records-halfbuff;
 
336
  idx=first_index=info->records-halfbuff;
322
337
  /* If some records */
323
338
  if (idx != info->records)
324
339
  {
358
373
          {
359
374
            /* Change link of previous LOW-key */
360
375
            gpos->data=ptr_to_rec;
361
 
            gpos->next= (uint32_t) (pos-data);
 
376
            gpos->next= (uint) (pos-data);
362
377
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
363
378
          }
364
379
          gpos=pos;
381
396
          {
382
397
            /* Change link of previous hash-key and save */
383
398
            gpos2->data=ptr_to_rec2;
384
 
            gpos2->next=(uint32_t) (pos-data);
 
399
            gpos2->next=(uint) (pos-data);
385
400
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
386
401
          }
387
402
          gpos2=pos;
419
434
    if (pos == gpos)
420
435
    {
421
436
      pos->data=(unsigned char*) record;
422
 
      pos->next=(uint32_t) (empty - data);
 
437
      pos->next=(uint) (empty - data);
423
438
    }
424
439
    else
425
440
    {
426
441
      pos->data=(unsigned char*) record;
427
442
      pos->next=NO_RECORD;
428
 
      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
 
443
      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
429
444
    }
430
445
  }
431
446
  if (++info->records == info->blength)
467
482
  lastpos=data+hash->records;
468
483
 
469
484
  /* Remove link to record */
470
 
  empty=pos; empty_index=(uint32_t) (empty-data);
 
485
  empty=pos; empty_index=(uint) (empty-data);
471
486
  if (gpos)
472
487
    /* unlink current ptr */
473
488
    gpos->next=pos->next;
499
514
  {                                     /* pos is on wrong posit */
500
515
    empty[0]=pos[0];                    /* Save it here */
501
516
    pos[0]=lastpos[0];                  /* This should be here */
502
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
 
517
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
503
518
    goto exit;
504
519
  }
505
520
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
508
523
    if (pos2 != hash->records)
509
524
    {
510
525
      empty[0]=lastpos[0];
511
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
 
526
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
512
527
      goto exit;
513
528
    }
514
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
 
529
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
515
530
  }
516
531
  else idx= NO_RECORD;          /* Different positions merge */
517
532
 
526
541
  return(0);
527
542
}
528
543
 
 
544
/*
 
545
  Update keys when record has changed.
 
546
  This is much more efficent than using a delete & insert.
 
547
*/
 
548
 
 
549
bool hash_update(HASH *hash, unsigned char *record, unsigned char *old_key,
 
550
                 size_t old_key_length)
 
551
{
 
552
  uint32_t new_index,new_pos_index,blength,records,empty;
 
553
  size_t idx;
 
554
  HASH_LINK org_link,*data,*previous,*pos;
 
555
 
 
556
  if (HASH_UNIQUE & hash->flags)
 
557
  {
 
558
    HASH_SEARCH_STATE state;
 
559
    unsigned char *found,
 
560
      *new_key= (unsigned char*) hash_key(hash, record, &idx, 1);
 
561
 
 
562
    if ((found= hash_first(hash, new_key, idx, &state)))
 
563
    {
 
564
      do
 
565
      {
 
566
        if (found != record)
 
567
          return(1);            /* Duplicate entry */
 
568
      }
 
569
      while ((found= hash_next(hash, new_key, idx, &state)));
 
570
    }
 
571
  }
 
572
 
 
573
  data=dynamic_element(&hash->array,0,HASH_LINK*);
 
574
  blength=hash->blength; records=hash->records;
 
575
 
 
576
  /* Search after record with key */
 
577
 
 
578
  idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?
 
579
                                         old_key_length :
 
580
                                         hash->key_length)),
 
581
                blength,records);
 
582
  new_index=hash_mask(rec_hashnr(hash,record),blength,records);
 
583
  if (idx == new_index)
 
584
    return(0);                  /* Nothing to do (No record check) */
 
585
  previous=0;
 
586
  for (;;)
 
587
  {
 
588
 
 
589
    if ((pos= data+idx)->data == record)
 
590
      break;
 
591
    previous=pos;
 
592
    if ((idx=pos->next) == NO_RECORD)
 
593
      return(1);                        /* Not found in links */
 
594
  }
 
595
  org_link= *pos;
 
596
  empty=idx;
 
597
 
 
598
  /* Relink record from current chain */
 
599
 
 
600
  if (!previous)
 
601
  {
 
602
    if (pos->next != NO_RECORD)
 
603
    {
 
604
      empty=pos->next;
 
605
      *pos= data[pos->next];
 
606
    }
 
607
  }
 
608
  else
 
609
    previous->next=pos->next;           /* unlink pos */
 
610
 
 
611
  /* Move data to correct position */
 
612
  if (new_index == empty)
 
613
  {
 
614
    /*
 
615
      At this point record is unlinked from the old chain, thus it holds
 
616
      random position. By the chance this position is equal to position
 
617
      for the first element in the new chain. That means updated record
 
618
      is the only record in the new chain.
 
619
    */
 
620
    if (empty != idx)
 
621
    {
 
622
      /*
 
623
        Record was moved while unlinking it from the old chain.
 
624
        Copy data to a new position.
 
625
      */
 
626
      data[empty]= org_link;
 
627
    }
 
628
    data[empty].next= NO_RECORD;
 
629
    return(0);
 
630
  }
 
631
  pos=data+new_index;
 
632
  new_pos_index=hash_rec_mask(hash,pos,blength,records);
 
633
  if (new_index != new_pos_index)
 
634
  {                                     /* Other record in wrong position */
 
635
    data[empty] = *pos;
 
636
    movelink(data,new_index,new_pos_index,empty);
 
637
    org_link.next=NO_RECORD;
 
638
    data[new_index]= org_link;
 
639
  }
 
640
  else
 
641
  {                                     /* Link in chain at right position */
 
642
    org_link.next=data[new_index].next;
 
643
    data[empty]=org_link;
 
644
    data[new_index].next=empty;
 
645
  }
 
646
  return(0);
 
647
}
 
648
 
 
649
 
529
650
unsigned char *hash_element(HASH *hash,uint32_t idx)
530
651
{
531
652
  if (idx < hash->records)
533
654
  return 0;
534
655
}
535
656
 
536
 
} /* namespace drizzled */
 
657
 
 
658
/*
 
659
  Replace old row with new row.  This should only be used when key
 
660
  isn't changed
 
661
*/
 
662
 
 
663
void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record,
 
664
                  unsigned char *new_row)
 
665
{
 
666
  if (*current_record != NO_RECORD)            /* Safety */
 
667
    dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
 
668
}