← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/heap/hp_write.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

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