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