home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / mysys / hash.c < prev    next >
C/C++ Source or Header  |  2000-11-14  |  15KB  |  588 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This library is free software; you can redistribute it and/or
  4.    modify it under the terms of the GNU Library General Public
  5.    License as published by the Free Software Foundation; either
  6.    version 2 of the License, or (at your option) any later version.
  7.    
  8.    This library is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11.    Library General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU Library General Public
  14.    License along with this library; if not, write to the Free
  15.    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16.    MA 02111-1307, USA */
  17.  
  18. /* The hash functions used for saveing keys */
  19. /* One of key_length or key_length_offset must be given */
  20. /* Key length of 0 isn't allowed */
  21.  
  22. #include "mysys_priv.h"
  23. #include <m_string.h>
  24. #include <m_ctype.h>
  25. #include "hash.h"
  26.  
  27. #define NO_RECORD    ((uint) -1)
  28. #define LOWFIND 1
  29. #define LOWUSED 2
  30. #define HIGHFIND 4
  31. #define HIGHUSED 8
  32.  
  33. static uint hash_mask(uint hashnr,uint buffmax,uint maxlength);
  34. static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink);
  35. static uint calc_hashnr(const byte *key,uint length);
  36. static uint calc_hashnr_caseup(const byte *key,uint length);
  37. static int hashcmp(HASH *hash,HASH_LINK *pos,const byte *key,uint length);
  38.  
  39.  
  40. my_bool hash_init(HASH *hash,uint size,uint key_offset,uint key_length,
  41.           hash_get_key get_key,
  42.           void (*free_element)(void*),uint flags)
  43. {
  44.   DBUG_ENTER("hash_init");
  45.   DBUG_PRINT("enter",("hash: %lx  size: %d",hash,size));
  46.  
  47.   hash->records=0;
  48.   if (init_dynamic_array(&hash->array,sizeof(HASH_LINK),size,0))
  49.   {
  50.     hash->free=0;                /* Allow call to hash_free */
  51.     DBUG_RETURN(TRUE);
  52.   }
  53.   hash->key_offset=key_offset;
  54.   hash->key_length=key_length;
  55.   hash->blength=1;
  56.   hash->current_record= NO_RECORD;        /* For the future */
  57.   hash->get_key=get_key;
  58.   hash->free=free_element;
  59.   hash->flags=flags;
  60.   if (flags & HASH_CASE_INSENSITIVE)
  61.     hash->calc_hashnr=calc_hashnr_caseup;
  62.   else
  63.     hash->calc_hashnr=calc_hashnr;
  64.   DBUG_RETURN(0);
  65. }
  66.  
  67.  
  68. void hash_free(HASH *hash)
  69. {
  70.   DBUG_ENTER("hash_free");
  71.   if (hash->free)
  72.   {
  73.     uint i,records;
  74.     HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
  75.     for (i=0,records=hash->records ; i < records ; i++)
  76.       (*hash->free)(data[i].data);
  77.     hash->free=0;
  78.   }
  79.   delete_dynamic(&hash->array);
  80.   hash->records=0;
  81.   DBUG_VOID_RETURN;
  82. }
  83.  
  84.     /* some helper functions */
  85.  
  86. static inline byte*
  87. hash_key(HASH *hash,const byte *record,uint *length,my_bool first)
  88. {
  89.   if (hash->get_key)
  90.     return (*hash->get_key)(record,length,first);
  91.   *length=hash->key_length;
  92.   return (byte*) record+hash->key_offset;
  93. }
  94.  
  95.     /* Calculate pos according to keys */
  96.  
  97. static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)
  98. {
  99.   if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
  100.   return (hashnr & ((buffmax >> 1) -1));
  101. }
  102.  
  103. static uint hash_rec_mask(HASH *hash,HASH_LINK *pos,uint buffmax,
  104.               uint maxlength)
  105. {
  106.   uint length;
  107.   byte *key=hash_key(hash,pos->data,&length,0);
  108.   return hash_mask((*hash->calc_hashnr)(key,length),buffmax,maxlength);
  109. }
  110.  
  111.     /* Calc hashvalue for a key */
  112.  
  113. static uint calc_hashnr(const byte *key,uint length)
  114. {
  115.   register uint nr=1, nr2=4;
  116.   while (length--)
  117.   {
  118.     nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);
  119.     nr2+=3;
  120.   }
  121.   return((uint) nr);
  122. }
  123.  
  124.     /* Calc hashvalue for a key, case indepenently */
  125.  
  126. static uint calc_hashnr_caseup(const byte *key,uint length)
  127. {
  128.   register uint nr=1, nr2=4;
  129.   while (length--)
  130.   {
  131.     nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8);
  132.     nr2+=3;
  133.   }
  134.   return((uint) nr);
  135. }
  136.  
  137.  
  138. static inline uint rec_hashnr(HASH *hash,const byte *record)
  139. {
  140.   uint length;
  141.   byte *key=hash_key(hash,record,&length,0);
  142.   return (*hash->calc_hashnr)(key,length);
  143. }
  144.  
  145.  
  146.     /* Search after a record based on a key */
  147.     /* Sets info->current_ptr to found record */
  148.  
  149. gptr hash_search(HASH *hash,const byte *key,uint length)
  150. {
  151.   HASH_LINK *pos;
  152.   uint flag,idx;
  153.   DBUG_ENTER("hash_search");
  154.  
  155.   flag=1;
  156.   if (hash->records)
  157.   {
  158.     idx=hash_mask((*hash->calc_hashnr)(key,length ? length :
  159.                      hash->key_length),
  160.             hash->blength,hash->records);
  161.     do
  162.     {
  163.       pos= dynamic_element(&hash->array,idx,HASH_LINK*);
  164.       if (!hashcmp(hash,pos,key,length))
  165.       {
  166.     DBUG_PRINT("exit",("found key at %d",idx));
  167.     hash->current_record= idx;
  168.     DBUG_RETURN (pos->data);
  169.       }
  170.       if (flag)
  171.       {
  172.     flag=0;                    /* Reset flag */
  173.     if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
  174.       break;                /* Wrong link */
  175.       }
  176.     }
  177.     while ((idx=pos->next) != NO_RECORD);
  178.   }
  179.   hash->current_record= NO_RECORD;
  180.   DBUG_RETURN(0);
  181. }
  182.  
  183.     /* Get next record with identical key */
  184.     /* Can only be called if previous calls was hash_search */
  185.  
  186. gptr hash_next(HASH *hash,const byte *key,uint length)
  187. {
  188.   HASH_LINK *pos;
  189.   uint idx;
  190.  
  191.   if (hash->current_record != NO_RECORD)
  192.   {
  193.     HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
  194.     for (idx=data[hash->current_record].next; idx != NO_RECORD ; idx=pos->next)
  195.     {
  196.       pos=data+idx;
  197.       if (!hashcmp(hash,pos,key,length))
  198.       {
  199.     hash->current_record= idx;
  200.     return pos->data;
  201.       }
  202.     }
  203.     hash->current_record=NO_RECORD;
  204.   }
  205.   return 0;
  206. }
  207.  
  208.  
  209.     /* Change link from pos to new_link */
  210.  
  211. static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
  212. {
  213.   HASH_LINK *old_link;
  214.   do
  215.   {
  216.     old_link=array+next_link;
  217.   }
  218.   while ((next_link=old_link->next) != find);
  219.   old_link->next= newlink;
  220.   return;
  221. }
  222.  
  223.     /* Compare a key in a record to a whole key. Return 0 if identical */
  224.  
  225. static int hashcmp(HASH *hash,HASH_LINK *pos,const byte *key,uint length)
  226. {
  227.   uint rec_keylength;
  228.   byte *rec_key=hash_key(hash,pos->data,&rec_keylength,1);
  229.   return (length && length != rec_keylength) ||
  230.     (hash->flags & HASH_CASE_INSENSITIVE ?
  231.      my_casecmp(rec_key,key,rec_keylength) :
  232.      memcmp(rec_key,key,rec_keylength));
  233. }
  234.  
  235.  
  236.     /* Write a hash-key to the hash-index */
  237.  
  238. my_bool hash_insert(HASH *info,const byte *record)
  239. {
  240.   int flag;
  241.   uint halfbuff,hash_nr,first_index,idx;
  242.   byte *ptr_to_rec,*ptr_to_rec2;
  243.   HASH_LINK *data,*empty,*gpos,*gpos2,*pos;
  244.  
  245.   LINT_INIT(gpos); LINT_INIT(gpos2);
  246.   LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2);
  247.  
  248.   flag=0;
  249.   if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
  250.     return(TRUE);                /* No more memory */
  251.  
  252.   info->current_record= NO_RECORD;
  253.   data=dynamic_element(&info->array,0,HASH_LINK*);
  254.   halfbuff= info->blength >> 1;
  255.  
  256.   idx=first_index=info->records-halfbuff;
  257.   if (idx != info->records)                /* If some records */
  258.   {
  259.     do
  260.     {
  261.       pos=data+idx;
  262.       hash_nr=rec_hashnr(info,pos->data);
  263.       if (flag == 0)                /* First loop; Check if ok */
  264.     if (hash_mask(hash_nr,info->blength,info->records) != first_index)
  265.       break;
  266.       if (!(hash_nr & halfbuff))
  267.       {                        /* Key will not move */
  268.     if (!(flag & LOWFIND))
  269.     {
  270.       if (flag & HIGHFIND)
  271.       {
  272.         flag=LOWFIND | HIGHFIND;
  273.         /* key shall be moved to the current empty position */
  274.         gpos=empty;
  275.         ptr_to_rec=pos->data;
  276.         empty=pos;                /* This place is now free */
  277.       }
  278.       else
  279.       {
  280.         flag=LOWFIND | LOWUSED;        /* key isn't changed */
  281.         gpos=pos;
  282.         ptr_to_rec=pos->data;
  283.       }
  284.     }
  285.     else
  286.     {
  287.       if (!(flag & LOWUSED))
  288.       {
  289.         /* Change link of previous LOW-key */
  290.         gpos->data=ptr_to_rec;
  291.         gpos->next=(uint) (pos-data);
  292.         flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
  293.       }
  294.       gpos=pos;
  295.       ptr_to_rec=pos->data;
  296.     }
  297.       }
  298.       else
  299.       {                        /* key will be moved */
  300.     if (!(flag & HIGHFIND))
  301.     {
  302.       flag= (flag & LOWFIND) | HIGHFIND;
  303.       /* key shall be moved to the last (empty) position */
  304.       gpos2 = empty; empty=pos;
  305.       ptr_to_rec2=pos->data;
  306.     }
  307.     else
  308.     {
  309.       if (!(flag & HIGHUSED))
  310.       {
  311.         /* Change link of previous hash-key and save */
  312.         gpos2->data=ptr_to_rec2;
  313.         gpos2->next=(uint) (pos-data);
  314.         flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
  315.       }
  316.       gpos2=pos;
  317.       ptr_to_rec2=pos->data;
  318.     }
  319.       }
  320.     }
  321.     while ((idx=pos->next) != NO_RECORD);
  322.  
  323.     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
  324.     {
  325.       gpos->data=ptr_to_rec;
  326.       gpos->next=NO_RECORD;
  327.     }
  328.     if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
  329.     {
  330.       gpos2->data=ptr_to_rec2;
  331.       gpos2->next=NO_RECORD;
  332.     }
  333.   }
  334.   /* Check if we are at the empty position */
  335.  
  336.   idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
  337.   pos=data+idx;
  338.   if (pos == empty)
  339.   {
  340.     pos->data=(byte*) record;
  341.     pos->next=NO_RECORD;
  342.   }
  343.   else
  344.   {
  345.     /* Check if more records in same hash-nr family */
  346.     empty[0]=pos[0];
  347.     gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
  348.     if (pos == gpos)
  349.     {
  350.       pos->data=(byte*) record;
  351.       pos->next=(uint) (empty - data);
  352.     }
  353.     else
  354.     {
  355.       pos->data=(byte*) record;
  356.       pos->next=NO_RECORD;
  357.       movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
  358.     }
  359.   }
  360.   if (++info->records == info->blength)
  361.     info->blength+= info->blength;
  362.   return(0);
  363. }
  364.  
  365.  
  366. /******************************************************************************
  367. ** Remove one record from hash-table. The record with the same record
  368. ** ptr is removed.
  369. ** if there is a free-function it's called for record if found
  370. ******************************************************************************/
  371.  
  372. my_bool hash_delete(HASH *hash,byte *record)
  373. {
  374.   uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;
  375.   HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
  376.   DBUG_ENTER("hash_delete");
  377.   if (!hash->records)
  378.     DBUG_RETURN(1);
  379.  
  380.   blength=hash->blength;
  381.   data=dynamic_element(&hash->array,0,HASH_LINK*);
  382.   /* Search after record with key */
  383.   pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records);
  384.   gpos = 0;
  385.  
  386.   while (pos->data != record)
  387.   {
  388.     gpos=pos;
  389.     if (pos->next == NO_RECORD)
  390.       DBUG_RETURN(1);            /* Key not found */
  391.     pos=data+pos->next;
  392.   }
  393.  
  394.   if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;
  395.   hash->current_record= NO_RECORD;
  396.   lastpos=data+hash->records;
  397.  
  398.   /* Remove link to record */
  399.   empty=pos; empty_index=(uint) (empty-data);
  400.   if (gpos)
  401.     gpos->next=pos->next;        /* unlink current ptr */
  402.   else if (pos->next != NO_RECORD)
  403.   {
  404.     empty=data+(empty_index=pos->next);
  405.     pos->data=empty->data;
  406.     pos->next=empty->next;
  407.   }
  408.  
  409.   if (empty == lastpos)            /* last key at wrong pos or no next link */
  410.     goto exit;
  411.  
  412.   /* Move the last key (lastpos) */
  413.   lastpos_hashnr=rec_hashnr(hash,lastpos->data);
  414.   /* pos is where lastpos should be */
  415.   pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);
  416.   if (pos == empty)            /* Move to empty position. */
  417.   {
  418.     empty[0]=lastpos[0];
  419.     goto exit;
  420.   }
  421.   pos_hashnr=rec_hashnr(hash,pos->data);
  422.   /* pos3 is where the pos should be */
  423.   pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records);
  424.   if (pos != pos3)
  425.   {                    /* pos is on wrong posit */
  426.     empty[0]=pos[0];            /* Save it here */
  427.     pos[0]=lastpos[0];            /* This should be here */
  428.     movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
  429.     goto exit;
  430.   }
  431.   pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);
  432.   if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1))
  433.   {                    /* Identical key-positions */
  434.     if (pos2 != hash->records)
  435.     {
  436.       empty[0]=lastpos[0];
  437.       movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
  438.       goto exit;
  439.     }
  440.     idx= (uint) (pos-data);        /* Link pos->next after lastpos */
  441.   }
  442.   else idx= NO_RECORD;        /* Different positions merge */
  443.  
  444.   empty[0]=lastpos[0];
  445.   movelink(data,idx,empty_index,pos->next);
  446.   pos->next=empty_index;
  447.  
  448. exit:
  449.   VOID(pop_dynamic(&hash->array));
  450.   if (hash->free)
  451.     (*hash->free)((byte*) record);
  452.   DBUG_RETURN(0);
  453. }
  454.  
  455.     /*
  456.       Update keys when record has changed.
  457.       This is much more efficent than using a delete & insert.
  458.       */
  459.  
  460. my_bool hash_update(HASH *hash,byte *record,byte *old_key,uint old_key_length)
  461. {
  462.   uint idx,new_index,new_pos_index,blength,records,empty;
  463.   HASH_LINK org_link,*data,*previous,*pos;
  464.   DBUG_ENTER("hash_update");
  465.  
  466.   data=dynamic_element(&hash->array,0,HASH_LINK*);
  467.   blength=hash->blength; records=hash->records;
  468.  
  469.   /* Search after record with key */
  470.  
  471.   idx=hash_mask((*hash->calc_hashnr)(old_key,(old_key_length ?
  472.                         old_key_length :
  473.                         hash->key_length)),
  474.           blength,records);
  475.   new_index=hash_mask(rec_hashnr(hash,record),blength,records);
  476.   if (idx == new_index)
  477.     DBUG_RETURN(0);            /* Nothing to do (No record check) */
  478.   previous=0;
  479.   for (;;)
  480.   {
  481.  
  482.     if ((pos= data+idx)->data == record)
  483.       break;
  484.     previous=pos;
  485.     if ((idx=pos->next) == NO_RECORD)
  486.       DBUG_RETURN(1);            /* Not found in links */
  487.   }
  488.   hash->current_record= NO_RECORD;
  489.   org_link= *pos;
  490.   empty=idx;
  491.  
  492.   /* Relink record from current chain */
  493.  
  494.   if (!previous)
  495.   {
  496.     if (pos->next != NO_RECORD)
  497.     {
  498.       empty=pos->next;
  499.       *pos= data[pos->next];
  500.     }
  501.   }
  502.   else
  503.     previous->next=pos->next;        /* unlink pos */
  504.  
  505.   /* Move data to correct position */
  506.   pos=data+new_index;
  507.   new_pos_index=hash_rec_mask(hash,pos,blength,records);
  508.   if (new_index != new_pos_index)
  509.   {                    /* Other record in wrong position */
  510.     data[empty] = *pos;
  511.     movelink(data,new_index,new_pos_index,empty);
  512.     org_link.next=NO_RECORD;
  513.     data[new_index]= org_link;
  514.   }
  515.   else
  516.   {                    /* Link in chain at right position */
  517.     org_link.next=data[new_index].next;
  518.     data[empty]=org_link;
  519.     data[new_index].next=empty;
  520.   }
  521.   DBUG_RETURN(0);
  522. }
  523.  
  524.  
  525. byte *hash_element(HASH *hash,uint idx)
  526. {
  527.   if (idx < hash->records)
  528.     return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
  529.   return 0;
  530. }
  531.  
  532.  
  533. #ifndef DBUG_OFF
  534.  
  535. my_bool hash_check(HASH *hash)
  536. {
  537.   int error;
  538.   uint i,rec_link,found,max_links,seek,links,idx;
  539.   uint records,blength;
  540.   HASH_LINK *data,*hash_info;
  541.  
  542.   records=hash->records; blength=hash->blength;
  543.   data=dynamic_element(&hash->array,0,HASH_LINK*);
  544.   error=0;
  545.  
  546.   for (i=found=max_links=seek=0 ; i < records ; i++)
  547.   {
  548.     if (hash_rec_mask(hash,data+i,blength,records) == i)
  549.     {
  550.       found++; seek++; links=1;
  551.       for (idx=data[i].next ;
  552.        idx != NO_RECORD && found < records + 1;
  553.        idx=hash_info->next)
  554.       {
  555.     if (idx >= records)
  556.     {
  557.       DBUG_PRINT("error",
  558.              ("Found pointer outside array to %d from link starting at %d",
  559.               idx,i));
  560.       error=1;
  561.     }
  562.     hash_info=data+idx;
  563.     seek+= ++links;
  564.     if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i)
  565.     {
  566.       DBUG_PRINT("error",
  567.              ("Record in wrong link at %d: Start %d  Record: %lx  Record-link %d", idx,i,hash_info->data,rec_link));
  568.       error=1;
  569.     }
  570.     else
  571.       found++;
  572.       }
  573.       if (links > max_links) max_links=links;
  574.     }
  575.   }
  576.   if (found != records)
  577.   {
  578.     DBUG_PRINT("error",("Found %ld of %ld records"));
  579.     error=1;
  580.   }
  581.   if (records)
  582.     DBUG_PRINT("info",
  583.            ("records: %ld   seeks: %d   max links: %d   hitrate: %.2f",
  584.         records,seek,max_links,(float) seek / (float) records));
  585.   return error;
  586. }
  587. #endif
  588.