List:Internals« Previous MessageNext Message »
From:Yan Yu Date:December 24 2009 5:46am
Subject:mysys/hash.c
View as plain text  
Dear MySQL experts:
     Thank you so much for your reply to my previous Qs, they are very  
helpful!
     Could someone please help me understand function my_hash_insert()  
in mysys/hash.cc?
what are lines 352 -429 trying to achieve?  Are they just some  
optimization to shuffle existing
hash entries in the table (since the existing hash entries may be in  
the wrong slot due to chaining
in the case of hash collision)?
Thanks!
yan

-----------------------
I copied function my_hash_insert() below:
331 my_bool my_hash_insert(HASH *info, const uchar *record)
332 {
333   int flag;
334   size_t idx,halfbuff,hash_nr,first_index;
335   uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);
336   HASH_LINK *data,*empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
337
338   if (HASH_UNIQUE & info->flags)
339   {
340     uchar *key= (uchar*) my_hash_key(info, record, &idx, 1);
341     if (my_hash_search(info, key, idx))
342       return(TRUE);       /* Duplicate entry */
343   }
344
345   flag=0;
346   if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
347     return(TRUE);       /* No more memory */
348
349   data=dynamic_element(&info->array,0,HASH_LINK*);
350   halfbuff= info->blength >> 1;
351
352   idx=first_index=info->records-halfbuff;
353   if (idx != info->records)       /* If some records */
354   {
355     do
356     {
357       pos=data+idx;
358       hash_nr=rec_hashnr(info,pos->data);
359       if (flag == 0)        /* First loop; Check if ok */
360   if (my_hash_mask(hash_nr, info->blength, info->records) !=  
first_index)
361     break;
362       if (!(hash_nr & halfbuff))
363       {           /* Key will not move */
364   if (!(flag & LOWFIND))
365   {
366     if (flag & HIGHFIND)
367     {
368       flag=LOWFIND | HIGHFIND;
369       /* key shall be moved to the current empty position */
370       gpos=empty;
371       ptr_to_rec=pos->data;
372       empty=pos;        /* This place is now free */
373     }
374     else
375     {
376       flag=LOWFIND | LOWUSED;   /* key isn't changed */
377       gpos=pos;
378       ptr_to_rec=pos->data;
379     }
380   }
381   else
382   {
383     if (!(flag & LOWUSED))
384     {
385       /* Change link of previous LOW-key */
386       gpos->data=ptr_to_rec;
387       gpos->next= (uint) (pos-data);
388       flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
389     }
390     gpos=pos;
391     ptr_to_rec=pos->data;
392   }
393       }
394       else
395       {           /* key will be moved */
396   if (!(flag & HIGHFIND))
397   {
398     flag= (flag & LOWFIND) | HIGHFIND;
399     /* key shall be moved to the last (empty) position */
400     gpos2 = empty; empty=pos;
401     ptr_to_rec2=pos->data;
402   }
403   else
404   {
405     if (!(flag & HIGHUSED))
406     {
407       /* Change link of previous hash-key and save */
408       gpos2->data=ptr_to_rec2;
409       gpos2->next=(uint) (pos-data);
410       flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
411     }
412     gpos2=pos;
413     ptr_to_rec2=pos->data;
414   }
415       }
416     }
417     while ((idx=pos->next) != NO_RECORD);
418
419     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
420     {
421       gpos->data=ptr_to_rec;
422       gpos->next=NO_RECORD;
423     }
424     if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
425     {
426       gpos2->data=ptr_to_rec2;
427       gpos2->next=NO_RECORD;
428     }
429   }
430   /* Check if we are at the empty position */
431
432   idx= my_hash_mask(rec_hashnr(info, record), info->blength, info- 
 >records + 1);
433   pos=data+idx;
434   if (pos == empty)
435   {
436     pos->data=(uchar*) record;
437     pos->next=NO_RECORD;
438   }
439   else
440   {
441     /* Check if more records in same hash-nr family */
442     empty[0]=pos[0];
443     gpos= data + my_hash_rec_mask(info, pos, info->blength, info- 
 >records + 1);
444     if (pos == gpos)
445     {
446       pos->data=(uchar*) record;
447       pos->next=(uint) (empty - data);
448     }
449     else
450     {
451
452       pos->data=(uchar*) record;
453       pos->next=NO_RECORD;
457       movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint)  
(empty-data));
458     }
459   }
460   if (++info->records == info->blength)
461     info->blength+= info->blength;
462   return(0);
463 }
464


Thread
mysys/hash.cYan Yu24 Dec
  • re: mysys/hash.cMichael Widenius24 Dec