release/src/router/mysql/storage/heap/hp_write.c

   1 /*
   2    Copyright (c) 2000-2002, 2004-2007 MySQL AB, 2009 Sun Microsystems, Inc.
   3    Use is subject to license terms.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; version 2 of the License.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
  17 */
  18
  19 /* Write a record to heap-databas */
  20
  21 #include "heapdef.h"
  22 #ifdef __WIN__
  23 #include <fcntl.h>
  24 #endif
  25
  26 #define LOWFIND 1
  27 #define LOWUSED 2
  28 #define HIGHFIND 4
  29 #define HIGHUSED 8
  30
  31 static uchar *next_free_record_pos(HP_SHARE *info);
  32 static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
  33                                      ulong records);
  34
  35 int heap_write(HP_INFO *info, const uchar *record)
  36 {
  37   HP_KEYDEF *keydef, *end;
  38   uchar *pos;
  39   HP_SHARE *share=info->s;
  40   DBUG_ENTER("heap_write");
  41 #ifndef DBUG_OFF
  42   if (info->mode & O_RDONLY)
  43   {
  44     DBUG_RETURN(my_errno=EACCES);
  45   }
  46 #endif
  47   if (!(pos=next_free_record_pos(share)))
  48     DBUG_RETURN(my_errno);
  49   share->changed=1;
  50
  51   for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
  52        keydef++)
  53   {
  54     if ((*keydef->write_key)(info, keydef, record, pos))
  55       goto err;
  56   }
  57
  58   memcpy(pos,record,(size_t) share->reclength);
  59   pos[share->reclength]=1;              /* Mark record as not deleted */
  60   if (++share->records == share->blength)
  61     share->blength+= share->blength;
  62   info->current_ptr=pos;
  63   info->current_hash_ptr=0;
  64   info->update|=HA_STATE_AKTIV;
  65 #if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
  66   DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
  67 #endif
  68   if (share->auto_key)
  69     heap_update_auto_increment(info, record);
  70   DBUG_RETURN(0);
  71
  72 err:
  73   if (my_errno == HA_ERR_FOUND_DUPP_KEY)
  74     DBUG_PRINT("info",("Duplicate key: %d", (int) (keydef - share->keydef)));
  75   info->errkey= (int) (keydef - share->keydef);
  76   /*
  77     We don't need to delete non-inserted key from rb-tree.  Also, if
  78     we got ENOMEM, the key wasn't inserted, so don't try to delete it
  79     either.  Otherwise for HASH index on HA_ERR_FOUND_DUPP_KEY the key
  80     was inserted and we have to delete it.
  81   */
  82   if (keydef->algorithm == HA_KEY_ALG_BTREE || my_errno == ENOMEM)
  83   {
  84     keydef--;
  85   }
  86   while (keydef >= share->keydef)
  87   {
  88     if ((*keydef->delete_key)(info, keydef, record, pos, 0))
  89       break;
  90     keydef--;
  91   }
  92
  93   share->deleted++;
  94   *((uchar**) pos)=share->del_link;
  95   share->del_link=pos;
  96   pos[share->reclength]=0;                      /* Record deleted */
  97
  98   DBUG_RETURN(my_errno);
  99 } /* heap_write */
 100
 101 /*
 102   Write a key to rb_tree-index
 103 */
 104
 105 int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record,
 106                     uchar *recpos)
 107 {
 108   heap_rb_param custom_arg;
 109   uint old_allocated;
 110
 111   custom_arg.keyseg= keyinfo->seg;
 112   custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
 113   if (keyinfo->flag & HA_NOSAME)
 114   {
 115     custom_arg.search_flag= SEARCH_FIND | SEARCH_UPDATE;
 116     keyinfo->rb_tree.flag= TREE_NO_DUPS;
 117   }
 118   else
 119   {
 120     custom_arg.search_flag= SEARCH_SAME;
 121     keyinfo->rb_tree.flag= 0;
 122   }
 123   old_allocated= keyinfo->rb_tree.allocated;
 124   if (!tree_insert(&keyinfo->rb_tree, (void*)info->recbuf,
 125                    custom_arg.key_length, &custom_arg))
 126   {
 127     my_errno= HA_ERR_FOUND_DUPP_KEY;
 128     return 1;
 129   }
 130   info->s->index_length+= (keyinfo->rb_tree.allocated-old_allocated);
 131   return 0;
 132 }
 133
 134         /* Find where to place new record */
 135
 136 static uchar *next_free_record_pos(HP_SHARE *info)
 137 {
 138   int block_pos;
 139   uchar *pos;
 140   size_t length;
 141   DBUG_ENTER("next_free_record_pos");
 142
 143   if (info->del_link)
 144   {
 145     pos=info->del_link;
 146     info->del_link= *((uchar**) pos);
 147     info->deleted--;
 148     DBUG_PRINT("exit",("Used old position: 0x%lx",(long) pos));
 149     DBUG_RETURN(pos);
 150   }
 151   if (!(block_pos=(info->records % info->block.records_in_block)))
 152   {
 153     if ((info->records > info->max_records && info->max_records) ||
 154         (info->data_length + info->index_length >= info->max_table_size))
 155     {
 156       my_errno=HA_ERR_RECORD_FILE_FULL;
 157       DBUG_RETURN(NULL);
 158     }
 159     if (hp_get_new_block(&info->block,&length))
 160       DBUG_RETURN(NULL);
 161     info->data_length+=length;
 162   }
 163   DBUG_PRINT("exit",("Used new position: 0x%lx",
 164                      (long) ((uchar*) info->block.level_info[0].last_blocks+
 165                              block_pos * info->block.recbuffer)));
 166   DBUG_RETURN((uchar*) info->block.level_info[0].last_blocks+
 167               block_pos*info->block.recbuffer);
 168 }
 169
 170
 171 /*
 172   Write a hash-key to the hash-index
 173   SYNOPSIS
 174     info     Heap table info
 175     keyinfo  Key info
 176     record   Table record to added
 177     recpos   Memory buffer where the table record will be stored if added
 178              successfully
 179   NOTE
 180     Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO
 181     structs. Array size == number of entries in hash index.
 182     hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
 183     If there are several hash entries with the same hash array position P,
 184     they are connected in a linked list via HASH_INFO::next_key. The first
 185     list element is located at position P, next elements are located at
 186     positions for which there is no record that should be located at that
 187     position. The order of elements in the list is arbitrary.
 188
 189   RETURN
 190     0  - OK
 191     -1 - Out of memory
 192     HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was
 193     still added and the caller must call hp_delete_key for it.
 194 */
 195
 196 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 197                  const uchar *record, uchar *recpos)
 198 {
 199   HP_SHARE *share = info->s;
 200   int flag;
 201   ulong halfbuff,hashnr,first_index;
 202   uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);
 203   HASH_INFO *empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
 204   DBUG_ENTER("hp_write_key");
 205
 206   flag=0;
 207   if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
 208     DBUG_RETURN(-1);                            /* No more memory */
 209   halfbuff= (long) share->blength >> 1;
 210   pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
 211
 212   /*
 213     We're about to add one more hash array position, with hash_mask=#records.
 214     The number of hash positions will change and some entries might need to
 215     be relocated to the newly added position. Those entries are currently
 216     members of the list that starts at #first_index position (this is
 217     guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
 218     At #first_index position currently there may be either:
 219     a) An entry with hashnr != first_index. We don't need to move it.
 220     or
 221     b) A list of items with hash_mask=first_index. The list contains entries
 222        of 2 types:
 223        1) entries that should be relocated to the list that starts at new
 224           position we're adding ('uppper' list)
 225        2) entries that should be left in the list starting at #first_index
 226           position ('lower' list)
 227   */
 228   if (pos != empty)                             /* If some records */
 229   {
 230     do
 231     {
 232       hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
 233       if (flag == 0)
 234       {
 235         /*
 236           First loop, bail out if we're dealing with case a) from above
 237           comment
 238         */
 239         if (hp_mask(hashnr, share->blength, share->records) != first_index)
 240           break;
 241       }
 242       /*
 243         flag & LOWFIND - found a record that should be put into lower position
 244         flag & LOWUSED - lower position occupied by the record
 245         Same for HIGHFIND and HIGHUSED and 'upper' position
 246
 247         gpos  - ptr to last element in lower position's list
 248         gpos2 - ptr to last element in upper position's list
 249
 250         ptr_to_rec - ptr to last entry that should go into lower list.
 251         ptr_to_rec2 - same for upper list.
 252       */
 253       if (!(hashnr & halfbuff))
 254       {
 255         /* Key should be put into 'lower' list */
 256         if (!(flag & LOWFIND))
 257         {
 258           /* key is the first element to go into lower position */
 259           if (flag & HIGHFIND)
 260           {
 261             flag=LOWFIND | HIGHFIND;
 262             /* key shall be moved to the current empty position */
 263             gpos=empty;
 264             ptr_to_rec=pos->ptr_to_rec;
 265             empty=pos;                          /* This place is now free */
 266           }
 267           else
 268           {
 269             /*
 270               We can only get here at first iteration: key is at 'lower'
 271               position pos and should be left here.
 272             */
 273             flag=LOWFIND | LOWUSED;
 274             gpos=pos;
 275             ptr_to_rec=pos->ptr_to_rec;
 276           }
 277         }
 278         else
 279         {
 280           /* Already have another key for lower position */
 281           if (!(flag & LOWUSED))
 282           {
 283             /* Change link of previous lower-list key */
 284             gpos->ptr_to_rec=ptr_to_rec;
 285             gpos->next_key=pos;
 286             flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
 287           }
 288           gpos=pos;
 289           ptr_to_rec=pos->ptr_to_rec;
 290         }
 291       }
 292       else
 293       {
 294         /* key will be put into 'higher' list */
 295         if (!(flag & HIGHFIND))
 296         {
 297           flag= (flag & LOWFIND) | HIGHFIND;
 298           /* key shall be moved to the last (empty) position */
 299           gpos2= empty;
 300           empty= pos;
 301           ptr_to_rec2=pos->ptr_to_rec;
 302         }
 303         else
 304         {
 305           if (!(flag & HIGHUSED))
 306           {
 307             /* Change link of previous upper-list key and save */
 308             gpos2->ptr_to_rec=ptr_to_rec2;
 309             gpos2->next_key=pos;
 310             flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
 311           }
 312           gpos2=pos;
 313           ptr_to_rec2=pos->ptr_to_rec;
 314         }
 315       }
 316     }
 317     while ((pos=pos->next_key));
 318
 319     if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
 320     {
 321       /*
 322         If both 'higher' and 'lower' list have at least one element, now
 323         there are two hash buckets instead of one.
 324       */
 325       keyinfo->hash_buckets++;
 326     }
 327
 328     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
 329     {
 330       gpos->ptr_to_rec=ptr_to_rec;
 331       gpos->next_key=0;
 332     }
 333     if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
 334     {
 335       gpos2->ptr_to_rec=ptr_to_rec2;
 336       gpos2->next_key=0;
 337     }
 338   }
 339   /* Check if we are at the empty position */
 340
 341   pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
 342                                          share->blength, share->records + 1));
 343   if (pos == empty)
 344   {
 345     pos->ptr_to_rec=recpos;
 346     pos->next_key=0;
 347     keyinfo->hash_buckets++;
 348   }
 349   else
 350   {
 351     /* Check if more records in same hash-nr family */
 352     empty[0]=pos[0];
 353     gpos=hp_find_hash(&keyinfo->block,
 354                       hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
 355                               share->blength, share->records + 1));
 356     if (pos == gpos)
 357     {
 358       pos->ptr_to_rec=recpos;
 359       pos->next_key=empty;
 360     }
 361     else
 362     {
 363       keyinfo->hash_buckets++;
 364       pos->ptr_to_rec=recpos;
 365       pos->next_key=0;
 366       hp_movelink(pos, gpos, empty);
 367     }
 368
 369     /* Check if duplicated keys */
 370     if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
 371         (!(keyinfo->flag & HA_NULL_PART_KEY) ||
 372          !hp_if_null_in_key(keyinfo, record)))
 373     {
 374       pos=empty;
 375       do
 376       {
 377         if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec, 1))
 378         {
 379           DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
 380         }
 381       } while ((pos=pos->next_key));
 382     }
 383   }
 384   DBUG_RETURN(0);
 385 }
 386
 387         /* Returns ptr to block, and allocates block if neaded */
 388
 389 static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
 390                                      HP_BLOCK *block, ulong records)
 391 {
 392   uint block_pos;
 393   size_t length;
 394
 395   if (records < block->last_allocated)
 396     return hp_find_hash(block,records);
 397   if (!(block_pos=(records % block->records_in_block)))
 398   {
 399     if (hp_get_new_block(block,&length))
 400       return(NULL);
 401     info->index_length+=length;
 402   }
 403   block->last_allocated=records+1;
 404   return((HASH_INFO*) ((uchar*) block->level_info[0].last_blocks+
 405                        block_pos*block->recbuffer));
 406 }