Fix for bug#5138 continued: added comments, removed extra debug printf calls, changed ha_heap::records_in_range to use table->rec_per_key.

heap/hp_block.c:
  Fix for bug#5138 continued: Added comments.
heap/hp_delete.c:
  Fix for bug#5138 continued: Added comments.
heap/hp_write.c:
  Fix for bug#5138 continued: Added comments, removed unneeded printf
include/heap.h:
  Fix for bug#5138 continued: Added comments.
mysql-test/r/heap_hash.result:
  Fix for bug#5138 continued: added FLUSH TABLES and rec_per_key estimates tests, updated test results
mysql-test/t/heap_hash.test:
  Fix for bug#5138 continued: added FLUSH TABLES and rec_per_key estimates tests, updated test results
sql/ha_heap.cc:
  Fix for bug#5138 continued: 
    fixed comments to be correct
    removed unneded printf
    use TABLE::rec_per_key for records_in_range statistics

1 files changed, 76 insertions, 21 deletions

diff --git a/heap/hp_write.c b/heap/hp_write.c
index 853360976bf..43cee67b39c 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -36,7 +36,6 @@ int heap_write(HP_INFO *info, const byte *record)
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_write");
-  printf("heap_write\n");
 #ifndef DBUG_OFF
   if (info->mode & O_RDONLY)
   {
@@ -160,7 +159,31 @@ static byte *next_free_record_pos(HP_SHARE *info)
 	      block_pos*info->block.recbuffer);
 }
 
-	/* Write a hash-key to the hash-index */
+
+/*
+  Write a hash-key to the hash-index
+  SYNOPSIS
+    info     Heap table info
+    keyinfo  Key info
+    record   Table record to added
+    recpos   Memory buffer where the table record will be stored if added 
+             successfully
+  NOTE
+    Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO 
+    structs. Array size == number of entries in hash index.
+    hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
+    If there are several hash entries with the same hash array position P,
+    they are connected in a linked list via HASH_INFO::next_key. The first 
+    list element is located at position P, next elements are located at 
+    positions for which there is no record that should be located at that
+    position. The order of elements in the list is arbitrary.
+
+  RETURN
+    0  - OK
+    -1 - Out of memory
+    HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was 
+    still added and the caller must call hp_delete_key for it.
+*/
 
 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 		 const byte *record, byte *recpos)
@@ -182,33 +205,52 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
   pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
   
   /*
-    We're about to add one more hash position, with hash_mask=#records. 
-    Entries that should be relocated to that position are currently members 
-    of the list that starts at #first_index position.
-    At #first_index position there may be either:
-    a) A list of items with hash_mask=first_index. The list contains 
+    We're about to add one more hash array position, with hash_mask=#records.
+    The number of hash positions will change and some entries might need to 
+    be relocated to the newly added position. Those entries are currently 
+    members of the list that starts at #first_index position (this is 
+    guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
+    At #first_index position currently there may be either:
+    a) An entry with hashnr != first_index. We don't need to move it.
+    or
+    b) A list of items with hash_mask=first_index. The list contains entries
+       of 2 types:
        1) entries that should be relocated to the list that starts at new 
-          position we're adding
+          position we're adding ('uppper' list)
        2) entries that should be left in the list starting at #first_index 
-          position 
-    or
-    b) An entry with hashnr != first_index. We don't need to move it.
+          position ('lower' list)
   */
   if (pos != empty)				/* If some records */
   {
     do
     {
       hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
-      if (flag == 0)				/* First loop; Check if ok */
+      if (flag == 0)
       {
-        /* Bail out if we're dealing with case b) from above comment */
+        /* 
+          First loop, bail out if we're dealing with case a) from above 
+          comment
+        */
 	if (hp_mask(hashnr, share->blength, share->records) != first_index)
 	  break;
       }
+      /*
+        flag & LOWFIND - found a record that should be put into lower position
+        flag & LOWUSED - lower position occupied by the record
+        Same for HIGHFIND and HIGHUSED and 'upper' position
+
+        gpos  - ptr to last element in lower position's list
+        gpos2 - ptr to last element in upper position's list
+
+        ptr_to_rec - ptr to last entry that should go into lower list.
+        ptr_to_rec2 - same for upper list.
+      */
       if (!(hashnr & halfbuff))
-      {						/* Key will not move */
+      {						
+        /* Key should be put into 'lower' list */
 	if (!(flag & LOWFIND))
 	{
+          /* key is the first element to go into lower position */
 	  if (flag & HIGHFIND)
 	  {
 	    flag=LOWFIND | HIGHFIND;
@@ -219,16 +261,21 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 	  }
 	  else
 	  {
-	    flag=LOWFIND | LOWUSED;		/* key isn't changed */
+            /*
+              We can only get here at first iteration: key is at 'lower' 
+              position pos and should be left here.
+            */
+	    flag=LOWFIND | LOWUSED;
 	    gpos=pos;
 	    ptr_to_rec=pos->ptr_to_rec;
 	  }
 	}
 	else
-	{
+        {
+          /* Already have another key for lower position */
 	  if (!(flag & LOWUSED))
 	  {
-	    /* Change link of previous LOW-key */
+	    /* Change link of previous lower-list key */
 	    gpos->ptr_to_rec=ptr_to_rec;
 	    gpos->next_key=pos;
 	    flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
@@ -238,19 +285,21 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 	}
       }
       else
-      {						/* key will be moved */
+      {
+        /* key will be put into 'higher' list */
 	if (!(flag & HIGHFIND))
 	{
 	  flag= (flag & LOWFIND) | HIGHFIND;
 	  /* key shall be moved to the last (empty) position */
-	  gpos2 = empty; empty=pos;
+	  gpos2= empty;
+          empty= pos;
 	  ptr_to_rec2=pos->ptr_to_rec;
 	}
 	else
 	{
 	  if (!(flag & HIGHUSED))
 	  {
-	    /* Change link of previous hash-key and save */
+	    /* Change link of previous upper-list key and save */
 	    gpos2->ptr_to_rec=ptr_to_rec2;
 	    gpos2->next_key=pos;
 	    flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
@@ -262,8 +311,14 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
     }
     while ((pos=pos->next_key));
     
-    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND)) 
+    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
+    {
+      /*
+        If both 'higher' and 'lower' list have at least one element, now
+        there are two hash buckets instead of one.
+      */
       keyinfo->hash_buckets++;
+    }
 
     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
     {