hp_write.c 11.3 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4 5 6
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
unknown's avatar
unknown committed
7

unknown's avatar
unknown committed
8 9 10 11
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
unknown's avatar
unknown committed
12

unknown's avatar
unknown committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* Write a record to heap-databas */

#include "heapdef.h"
#ifdef __WIN__
#include <fcntl.h>
#endif

#define LOWFIND 1
#define LOWUSED 2
#define HIGHFIND 4
#define HIGHUSED 8

static byte *next_free_record_pos(HP_SHARE *info);
30
static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
unknown's avatar
unknown committed
31 32 33 34
				     ulong records);

int heap_write(HP_INFO *info, const byte *record)
{
35
  HP_KEYDEF *keydef, *end;
unknown's avatar
unknown committed
36 37 38 39
  byte *pos;
  HP_SHARE *share=info->s;
  DBUG_ENTER("heap_write");
#ifndef DBUG_OFF
unknown's avatar
unknown committed
40
  if (info->mode & O_RDONLY)
unknown's avatar
unknown committed
41 42 43 44 45 46 47 48
  {
    DBUG_RETURN(my_errno=EACCES);
  }
#endif
  if (!(pos=next_free_record_pos(share)))
    DBUG_RETURN(my_errno);
  share->changed=1;

49 50
  for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
       keydef++)
unknown's avatar
unknown committed
51
  {
52
    if ((*keydef->write_key)(info, keydef, record, pos))
unknown's avatar
unknown committed
53 54 55 56 57 58 59 60 61 62
      goto err;
  }

  memcpy(pos,record,(size_t) share->reclength);
  pos[share->reclength]=1;		/* Mark record as not deleted */
  if (++share->records == share->blength)
    share->blength+= share->blength;
  info->current_ptr=pos;
  info->current_hash_ptr=0;
  info->update|=HA_STATE_AKTIV;
unknown's avatar
unknown committed
63 64 65
#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
  DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
#endif
unknown's avatar
unknown committed
66 67
  if (share->auto_key)
    heap_update_auto_increment(info, record);
unknown's avatar
unknown committed
68
  DBUG_RETURN(0);
unknown's avatar
unknown committed
69

unknown's avatar
unknown committed
70
err:
71 72 73
  DBUG_PRINT("info",("Duplicate key: %d", keydef - share->keydef));
  info->errkey= keydef - share->keydef;
  if (keydef->algorithm == HA_KEY_ALG_BTREE)
unknown's avatar
unknown committed
74
  {
75 76 77 78 79 80
    /* we don't need to delete non-inserted key from rb-tree */
    keydef--;
  }
  while (keydef >= share->keydef)
  {
    if ((*keydef->delete_key)(info, keydef, record, pos, 0))
unknown's avatar
unknown committed
81
      break;
82 83
    keydef--;
  } 
unknown's avatar
unknown committed
84 85 86 87 88

  share->deleted++;
  *((byte**) pos)=share->del_link;
  share->del_link=pos;
  pos[share->reclength]=0;			/* Record deleted */
unknown's avatar
unknown committed
89

unknown's avatar
unknown committed
90 91 92
  DBUG_RETURN(my_errno);
} /* heap_write */

93 94 95 96 97
/* 
  Write a key to rb_tree-index 
*/

int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *record, 
unknown's avatar
unknown committed
98
		    byte *recpos)
99 100
{
  heap_rb_param custom_arg;
101
  uint old_allocated;
102

103 104 105
  info->last_pos= NULL; /* For heap_rnext/heap_rprev */
  custom_arg.keyseg= keyinfo->seg;
  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
106
  if (keyinfo->flag & HA_NOSAME)
107
  {
108
    custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
109 110 111 112 113 114 115
    keyinfo->rb_tree.flag= TREE_NO_DUPS;
  }
  else
  {
    custom_arg.search_flag= SEARCH_SAME;
    keyinfo->rb_tree.flag= 0;
  }
116
  old_allocated= keyinfo->rb_tree.allocated;
117 118 119 120 121
  if (!tree_insert(&keyinfo->rb_tree, (void*)info->recbuf,
		   custom_arg.key_length, &custom_arg))
  {
    my_errno= HA_ERR_FOUND_DUPP_KEY;
    return 1;
122
  }
123
  info->s->index_length+= (keyinfo->rb_tree.allocated-old_allocated);
124
  return 0;
125
}
unknown's avatar
unknown committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

	/* Find where to place new record */

static byte *next_free_record_pos(HP_SHARE *info)
{
  int block_pos;
  byte *pos;
  ulong length;
  DBUG_ENTER("next_free_record_pos");

  if (info->del_link)
  {
    pos=info->del_link;
    info->del_link= *((byte**) pos);
    info->deleted--;
    DBUG_PRINT("exit",("Used old position: %lx",pos));
    DBUG_RETURN(pos);
  }
  if (!(block_pos=(info->records % info->block.records_in_block)))
  {
146 147
    if ((info->records > info->max_records && info->max_records) ||
        (info->data_length + info->index_length >= info->max_table_size))
unknown's avatar
unknown committed
148 149 150 151
    {
      my_errno=HA_ERR_RECORD_FILE_FULL;
      DBUG_RETURN(NULL);
    }
152
    if (hp_get_new_block(&info->block,&length))
unknown's avatar
unknown committed
153 154 155 156 157 158 159 160 161 162
      DBUG_RETURN(NULL);
    info->data_length+=length;
  }
  DBUG_PRINT("exit",("Used new position: %lx",
		     (byte*) info->block.level_info[0].last_blocks+block_pos*
		     info->block.recbuffer));
  DBUG_RETURN((byte*) info->block.level_info[0].last_blocks+
	      block_pos*info->block.recbuffer);
}

163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

/*
  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.
*/
unknown's avatar
unknown committed
188

189
int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
190
		 const byte *record, byte *recpos)
unknown's avatar
unknown committed
191
{
192
  HP_SHARE *share = info->s;
unknown's avatar
unknown committed
193 194 195 196 197 198 199 200 201 202
  int flag;
  ulong halfbuff,hashnr,first_index;
  byte *ptr_to_rec,*ptr_to_rec2;
  HASH_INFO *empty,*gpos,*gpos2,*pos;
  DBUG_ENTER("hp_write_key");

  LINT_INIT(gpos); LINT_INIT(gpos2);
  LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2);

  flag=0;
203
  if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
unknown's avatar
unknown committed
204
    DBUG_RETURN(-1);				/* No more memory */
205 206
  halfbuff= (long) share->blength >> 1;
  pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
207 208
  
  /*
209 210 211 212 213 214 215 216 217 218
    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:
219
       1) entries that should be relocated to the list that starts at new 
220
          position we're adding ('uppper' list)
221
       2) entries that should be left in the list starting at #first_index 
222
          position ('lower' list)
223
  */
unknown's avatar
unknown committed
224 225 226 227
  if (pos != empty)				/* If some records */
  {
    do
    {
228
      hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
229
      if (flag == 0)
230
      {
231 232 233 234
        /* 
          First loop, bail out if we're dealing with case a) from above 
          comment
        */
235
	if (hp_mask(hashnr, share->blength, share->records) != first_index)
unknown's avatar
unknown committed
236
	  break;
237
      }
238 239 240 241 242 243 244 245 246 247 248
      /*
        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.
      */
unknown's avatar
unknown committed
249
      if (!(hashnr & halfbuff))
250 251
      {						
        /* Key should be put into 'lower' list */
unknown's avatar
unknown committed
252 253
	if (!(flag & LOWFIND))
	{
254
          /* key is the first element to go into lower position */
unknown's avatar
unknown committed
255 256 257 258 259 260 261 262 263 264
	  if (flag & HIGHFIND)
	  {
	    flag=LOWFIND | HIGHFIND;
	    /* key shall be moved to the current empty position */
	    gpos=empty;
	    ptr_to_rec=pos->ptr_to_rec;
	    empty=pos;				/* This place is now free */
	  }
	  else
	  {
265 266 267 268 269
            /*
              We can only get here at first iteration: key is at 'lower' 
              position pos and should be left here.
            */
	    flag=LOWFIND | LOWUSED;
unknown's avatar
unknown committed
270 271 272 273 274
	    gpos=pos;
	    ptr_to_rec=pos->ptr_to_rec;
	  }
	}
	else
275 276
        {
          /* Already have another key for lower position */
unknown's avatar
unknown committed
277 278
	  if (!(flag & LOWUSED))
	  {
279
	    /* Change link of previous lower-list key */
unknown's avatar
unknown committed
280 281 282 283 284 285 286 287 288
	    gpos->ptr_to_rec=ptr_to_rec;
	    gpos->next_key=pos;
	    flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
	  }
	  gpos=pos;
	  ptr_to_rec=pos->ptr_to_rec;
	}
      }
      else
289 290
      {
        /* key will be put into 'higher' list */
unknown's avatar
unknown committed
291 292 293 294
	if (!(flag & HIGHFIND))
	{
	  flag= (flag & LOWFIND) | HIGHFIND;
	  /* key shall be moved to the last (empty) position */
295 296
	  gpos2= empty;
          empty= pos;
unknown's avatar
unknown committed
297 298 299 300 301 302
	  ptr_to_rec2=pos->ptr_to_rec;
	}
	else
	{
	  if (!(flag & HIGHUSED))
	  {
303
	    /* Change link of previous upper-list key and save */
unknown's avatar
unknown committed
304 305 306 307 308 309 310 311 312 313
	    gpos2->ptr_to_rec=ptr_to_rec2;
	    gpos2->next_key=pos;
	    flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
	  }
	  gpos2=pos;
	  ptr_to_rec2=pos->ptr_to_rec;
	}
      }
    }
    while ((pos=pos->next_key));
314
    
315 316 317 318 319 320
    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.
      */
321
      keyinfo->hash_buckets++;
322
    }
unknown's avatar
unknown committed
323 324 325 326 327 328 329 330 331 332 333 334 335 336

    if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
    {
      gpos->ptr_to_rec=ptr_to_rec;
      gpos->next_key=0;
    }
    if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
    {
      gpos2->ptr_to_rec=ptr_to_rec2;
      gpos2->next_key=0;
    }
  }
  /* Check if we are at the empty position */

337 338
  pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
					 share->blength, share->records + 1));
unknown's avatar
unknown committed
339 340 341 342
  if (pos == empty)
  {
    pos->ptr_to_rec=recpos;
    pos->next_key=0;
343
    keyinfo->hash_buckets++;
unknown's avatar
unknown committed
344 345 346 347 348 349
  }
  else
  {
    /* Check if more records in same hash-nr family */
    empty[0]=pos[0];
    gpos=hp_find_hash(&keyinfo->block,
350 351
		      hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
			      share->blength, share->records + 1));
unknown's avatar
unknown committed
352 353 354 355 356 357 358
    if (pos == gpos)
    {
      pos->ptr_to_rec=recpos;
      pos->next_key=empty;
    }
    else
    {
359
      keyinfo->hash_buckets++;
unknown's avatar
unknown committed
360 361
      pos->ptr_to_rec=recpos;
      pos->next_key=0;
362
      hp_movelink(pos, gpos, empty);
unknown's avatar
unknown committed
363 364
    }

365
    /* Check if duplicated keys */
366 367 368
    if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
	(!(keyinfo->flag & HA_NULL_PART_KEY) ||
	 !hp_if_null_in_key(keyinfo, record)))
unknown's avatar
unknown committed
369 370 371 372
    {
      pos=empty;
      do
      {
373
	if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
unknown's avatar
unknown committed
374 375 376 377 378 379 380 381 382 383 384
	{
	  DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
	}
      } while ((pos=pos->next_key));
    }
  }
  DBUG_RETURN(0);
}

	/* Returns ptr to block, and allocates block if neaded */

385
static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
unknown's avatar
unknown committed
386 387 388 389 390 391 392 393 394
				     HP_BLOCK *block, ulong records)
{
  uint block_pos;
  ulong length;

  if (records < block->last_allocated)
    return hp_find_hash(block,records);
  if (!(block_pos=(records % block->records_in_block)))
  {
395
    if (hp_get_new_block(block,&length))
unknown's avatar
unknown committed
396 397 398 399 400 401 402
      return(NULL);
    info->index_length+=length;
  }
  block->last_allocated=records+1;
  return((HASH_INFO*) ((byte*) block->level_info[0].last_blocks+
		       block_pos*block->recbuffer));
}