← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/hash.cc

  • Committer: Brian Aker
  • Date: 2009-01-24 09:43:35 UTC
  • Revision ID: brian@gir-3.local-20090124094335-6qdtvc35gl5fvivz
Adding in an example singe thread scheduler

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/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"
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
 
125
121
  return;
126
122
}
127
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;
 
140
}
 
141
 
128
142
/* some helper functions */
129
143
 
130
144
/*
319
333
  data=dynamic_element(&info->array,0,HASH_LINK*);
320
334
  halfbuff= info->blength >> 1;
321
335
 
322
 
  idx= first_index= info->records-halfbuff;
 
336
  idx=first_index=info->records-halfbuff;
323
337
  /* If some records */
324
338
  if (idx != info->records)
325
339
  {
359
373
          {
360
374
            /* Change link of previous LOW-key */
361
375
            gpos->data=ptr_to_rec;
362
 
            gpos->next= (uint32_t) (pos-data);
 
376
            gpos->next= (uint) (pos-data);
363
377
            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
364
378
          }
365
379
          gpos=pos;
382
396
          {
383
397
            /* Change link of previous hash-key and save */
384
398
            gpos2->data=ptr_to_rec2;
385
 
            gpos2->next=(uint32_t) (pos-data);
 
399
            gpos2->next=(uint) (pos-data);
386
400
            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
387
401
          }
388
402
          gpos2=pos;
420
434
    if (pos == gpos)
421
435
    {
422
436
      pos->data=(unsigned char*) record;
423
 
      pos->next=(uint32_t) (empty - data);
 
437
      pos->next=(uint) (empty - data);
424
438
    }
425
439
    else
426
440
    {
427
441
      pos->data=(unsigned char*) record;
428
442
      pos->next=NO_RECORD;
429
 
      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));
430
444
    }
431
445
  }
432
446
  if (++info->records == info->blength)
468
482
  lastpos=data+hash->records;
469
483
 
470
484
  /* Remove link to record */
471
 
  empty=pos; empty_index=(uint32_t) (empty-data);
 
485
  empty=pos; empty_index=(uint) (empty-data);
472
486
  if (gpos)
473
487
    /* unlink current ptr */
474
488
    gpos->next=pos->next;
500
514
  {                                     /* pos is on wrong posit */
501
515
    empty[0]=pos[0];                    /* Save it here */
502
516
    pos[0]=lastpos[0];                  /* This should be here */
503
 
    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);
 
517
    movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
504
518
    goto exit;
505
519
  }
506
520
  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
509
523
    if (pos2 != hash->records)
510
524
    {
511
525
      empty[0]=lastpos[0];
512
 
      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);
 
526
      movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
513
527
      goto exit;
514
528
    }
515
 
    idx= (uint32_t) (pos-data);         /* Link pos->next after lastpos */
 
529
    idx= (uint) (pos-data);             /* Link pos->next after lastpos */
516
530
  }
517
531
  else idx= NO_RECORD;          /* Different positions merge */
518
532
 
527
541
  return(0);
528
542
}
529
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
 
530
650
unsigned char *hash_element(HASH *hash,uint32_t idx)
531
651
{
532
652
  if (idx < hash->records)
534
654
  return 0;
535
655
}
536
656
 
537
 
} /* 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
}