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-1335 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
29 static uchar *next_free_record_pos(HP_SHARE *info);
30 static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
31 ulong records);
32
heap_write(HP_INFO * info,const uchar * record)33 int 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->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= (int) (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->visible]= 0; /* Record deleted */
94
95 DBUG_RETURN(my_errno);
96 } /* heap_write */
97
98 /*
99 Write a key to rb_tree-index
100 */
101
hp_rb_write_key(HP_INFO * info,HP_KEYDEF * keyinfo,const uchar * record,uchar * recpos)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 size_t 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 | SEARCH_INSERT;
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
next_free_record_pos(HP_SHARE * info)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: %p", 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 DBUG_PRINT("error",
154 ("record file full. records: %lu max_records: %lu "
155 "data_length: %llu index_length: %llu "
156 "max_table_size: %llu",
157 info->records, info->max_records,
158 info->data_length, info->index_length,
159 info->max_table_size));
160 my_errno=HA_ERR_RECORD_FILE_FULL;
161 DBUG_RETURN(NULL);
162 }
163 if (hp_get_new_block(info, &info->block,&length))
164 DBUG_RETURN(NULL);
165 info->data_length+=length;
166 }
167 DBUG_PRINT("exit",("Used new position: %p",
168 ((uchar*) info->block.level_info[0].last_blocks+
169 block_pos * info->block.recbuffer)));
170 DBUG_RETURN((uchar*) info->block.level_info[0].last_blocks+
171 block_pos*info->block.recbuffer);
172 }
173
174
175 /*
176 Write a hash-key to the hash-index
177 SYNOPSIS
178 info Heap table info
179 keyinfo Key info
180 record Table record to added
181 recpos Memory buffer where the table record will be stored if added
182 successfully
183 NOTE
184 Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO
185 structs. Array size == number of entries in hash index.
186 hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
187 If there are several hash entries with the same hash array position P,
188 they are connected in a linked list via HASH_INFO::next_key. The first
189 list element is located at position P, next elements are located at
190 positions for which there is no record that should be located at that
191 position. The order of elements in the list is arbitrary.
192
193 RETURN
194 0 - OK
195 -1 - Out of memory
196 HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was
197 still added and the caller must call hp_delete_key for it.
198 */
199
hp_write_key(HP_INFO * info,HP_KEYDEF * keyinfo,const uchar * record,uchar * recpos)200 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
201 const uchar *record, uchar *recpos)
202 {
203 HP_SHARE *share = info->s;
204 int flag;
205 ulong halfbuff,hashnr,first_index;
206 ulong UNINIT_VAR(hash_of_key), UNINIT_VAR(hash_of_key2);
207 uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);
208 HASH_INFO *empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
209 DBUG_ENTER("hp_write_key");
210
211 flag=0;
212 if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
213 DBUG_RETURN(-1); /* No more memory */
214 halfbuff= (long) share->blength >> 1;
215 pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
216
217 /*
218 We're about to add one more hash array position, with hash_mask=#records.
219 The number of hash positions will change and some entries might need to
220 be relocated to the newly added position. Those entries are currently
221 members of the list that starts at #first_index position (this is
222 guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
223 At #first_index position currently there may be either:
224 a) An entry with hashnr != first_index. We don't need to move it.
225 or
226 b) A list of items with hash_mask=first_index. The list contains entries
227 of 2 types:
228 1) entries that should be relocated to the list that starts at new
229 position we're adding ('uppper' list)
230 2) entries that should be left in the list starting at #first_index
231 position ('lower' list)
232 */
233 if (pos != empty) /* If some records */
234 {
235 do
236 {
237 hashnr = pos->hash_of_key;
238 if (flag == 0)
239 {
240 /*
241 First loop, bail out if we're dealing with case a) from above
242 comment
243 */
244 if (hp_mask(hashnr, share->blength, share->records) != first_index)
245 break;
246 }
247 /*
248 flag & LOWFIND - found a record that should be put into lower position
249 flag & LOWUSED - lower position occupied by the record
250 Same for HIGHFIND and HIGHUSED and 'upper' position
251
252 gpos - ptr to last element in lower position's list
253 gpos2 - ptr to last element in upper position's list
254
255 ptr_to_rec - ptr to last entry that should go into lower list.
256 ptr_to_rec2 - same for upper list.
257 */
258 if (!(hashnr & halfbuff))
259 {
260 /* Key should be put into 'lower' list */
261 if (!(flag & LOWFIND))
262 {
263 /* key is the first element to go into lower position */
264 if (flag & HIGHFIND)
265 {
266 flag=LOWFIND | HIGHFIND;
267 /* key shall be moved to the current empty position */
268 gpos=empty;
269 empty=pos; /* This place is now free */
270 }
271 else
272 {
273 /*
274 We can only get here at first iteration: key is at 'lower'
275 position pos and should be left here.
276 */
277 flag=LOWFIND | LOWUSED;
278 gpos=pos;
279 }
280 }
281 else
282 {
283 /* Already have another key for lower position */
284 if (!(flag & LOWUSED))
285 {
286 /* Change link of previous lower-list key */
287 gpos->ptr_to_rec= ptr_to_rec;
288 gpos->next_key= pos;
289 gpos->hash_of_key= hash_of_key;
290 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
291 }
292 gpos=pos;
293 }
294 ptr_to_rec= pos->ptr_to_rec;
295 hash_of_key= pos->hash_of_key;
296 }
297 else
298 {
299 /* key will be put into 'higher' list */
300 if (!(flag & HIGHFIND))
301 {
302 flag= (flag & LOWFIND) | HIGHFIND;
303 /* key shall be moved to the last (empty) position */
304 gpos2= empty;
305 empty= pos;
306 }
307 else
308 {
309 if (!(flag & HIGHUSED))
310 {
311 /* Change link of previous upper-list key and save */
312 gpos2->ptr_to_rec= ptr_to_rec2;
313 gpos2->next_key= pos;
314 gpos2->hash_of_key= hash_of_key2;
315 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
316 }
317 gpos2=pos;
318 }
319 ptr_to_rec2= pos->ptr_to_rec;
320 hash_of_key2= pos->hash_of_key;
321 }
322 }
323 while ((pos=pos->next_key));
324
325 if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
326 {
327 /*
328 If both 'higher' and 'lower' list have at least one element, now
329 there are two hash buckets instead of one.
330 */
331 keyinfo->hash_buckets++;
332 }
333
334 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
335 {
336 gpos->ptr_to_rec= ptr_to_rec;
337 gpos->hash_of_key= hash_of_key;
338 gpos->next_key= 0;
339 }
340 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
341 {
342 gpos2->ptr_to_rec= ptr_to_rec2;
343 gpos2->hash_of_key= hash_of_key2;
344 gpos2->next_key= 0;
345 }
346 }
347 /* Check if we are at the empty position */
348
349 hash_of_key= hp_rec_hashnr(keyinfo, record);
350 pos=hp_find_hash(&keyinfo->block,
351 hp_mask(hash_of_key, share->blength, share->records + 1));
352 if (pos == empty)
353 {
354 pos->ptr_to_rec= recpos;
355 pos->hash_of_key= hash_of_key;
356 pos->next_key= 0;
357 keyinfo->hash_buckets++;
358 }
359 else
360 {
361 /* Check if more records in same hash-nr family */
362 empty[0]=pos[0];
363 gpos=hp_find_hash(&keyinfo->block,
364 hp_mask(pos->hash_of_key,
365 share->blength, share->records + 1));
366
367 pos->ptr_to_rec= recpos;
368 pos->hash_of_key= hash_of_key;
369 if (pos == gpos)
370 pos->next_key=empty;
371 else
372 {
373 keyinfo->hash_buckets++;
374 pos->next_key= 0;
375 hp_movelink(pos, gpos, empty);
376 }
377
378 /* Check if duplicated keys */
379 if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
380 (!(keyinfo->flag & HA_NULL_PART_KEY) ||
381 !hp_if_null_in_key(keyinfo, record)))
382 {
383 pos=empty;
384 do
385 {
386 if (pos->hash_of_key == hash_of_key &&
387 ! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
388 {
389 DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
390 }
391 } while ((pos=pos->next_key));
392 }
393 }
394 DBUG_RETURN(0);
395 }
396
397 /* Returns ptr to block, and allocates block if neaded */
398
hp_find_free_hash(HP_SHARE * info,HP_BLOCK * block,ulong records)399 static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
400 HP_BLOCK *block, ulong records)
401 {
402 ulong block_pos;
403 size_t length;
404
405 if (records < block->last_allocated)
406 return hp_find_hash(block,records);
407 if (!(block_pos=(records % block->records_in_block)))
408 {
409 if (hp_get_new_block(info, block, &length))
410 return(NULL);
411 info->index_length+=length;
412 }
413 block->last_allocated=records+1;
414 return((HASH_INFO*) ((uchar*) block->level_info[0].last_blocks+
415 block_pos*block->recbuffer));
416 }
417