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, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24 /* Write a record to heap-databas */
25
26 #include "heapdef.h"
27 #ifdef __WIN__
28 #include <fcntl.h>
29 #endif
30
31 #define LOWFIND 1
32 #define LOWUSED 2
33 #define HIGHFIND 4
34 #define HIGHUSED 8
35
36 static uchar *next_free_record_pos(HP_SHARE *info);
37 static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
38 ulong records);
39
heap_write(HP_INFO * info,const uchar * record)40 int heap_write(HP_INFO *info, const uchar *record)
41 {
42 HP_KEYDEF *keydef, *end;
43 uchar *pos;
44 HP_SHARE *share=info->s;
45 DBUG_ENTER("heap_write");
46 #ifndef DBUG_OFF
47 if (info->mode & O_RDONLY)
48 {
49 DBUG_RETURN(my_errno=EACCES);
50 }
51 #endif
52 if (!(pos=next_free_record_pos(share)))
53 DBUG_RETURN(my_errno);
54 share->changed=1;
55
56 for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
57 keydef++)
58 {
59 if ((*keydef->write_key)(info, keydef, record, pos))
60 goto err;
61 }
62
63 memcpy(pos,record,(size_t) share->reclength);
64 pos[share->reclength]=1; /* Mark record as not deleted */
65 if (++share->records == share->blength)
66 share->blength+= share->blength;
67 info->current_ptr=pos;
68 info->current_hash_ptr=0;
69 info->update|=HA_STATE_AKTIV;
70 #if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
71 DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
72 #endif
73 if (share->auto_key)
74 heap_update_auto_increment(info, record);
75 DBUG_RETURN(0);
76
77 err:
78 if (my_errno == HA_ERR_FOUND_DUPP_KEY)
79 DBUG_PRINT("info",("Duplicate key: %d", (int) (keydef - share->keydef)));
80 info->errkey= (int) (keydef - share->keydef);
81 /*
82 We don't need to delete non-inserted key from rb-tree. Also, if
83 we got ENOMEM, the key wasn't inserted, so don't try to delete it
84 either. Otherwise for HASH index on HA_ERR_FOUND_DUPP_KEY the key
85 was inserted and we have to delete it.
86 */
87 if (keydef->algorithm == HA_KEY_ALG_BTREE || my_errno == ENOMEM)
88 {
89 keydef--;
90 }
91 while (keydef >= share->keydef)
92 {
93 if ((*keydef->delete_key)(info, keydef, record, pos, 0))
94 break;
95 keydef--;
96 }
97
98 share->deleted++;
99 *((uchar**) pos)=share->del_link;
100 share->del_link=pos;
101 pos[share->reclength]=0; /* Record deleted */
102
103 DBUG_RETURN(my_errno);
104 } /* heap_write */
105
106 /*
107 Write a key to rb_tree-index
108 */
109
hp_rb_write_key(HP_INFO * info,HP_KEYDEF * keyinfo,const uchar * record,uchar * recpos)110 int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record,
111 uchar *recpos)
112 {
113 heap_rb_param custom_arg;
114 uint old_allocated;
115
116 custom_arg.keyseg= keyinfo->seg;
117 custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
118 if (keyinfo->flag & HA_NOSAME)
119 {
120 custom_arg.search_flag= SEARCH_FIND | SEARCH_UPDATE;
121 keyinfo->rb_tree.flag= TREE_NO_DUPS;
122 }
123 else
124 {
125 custom_arg.search_flag= SEARCH_SAME;
126 keyinfo->rb_tree.flag= 0;
127 }
128 old_allocated= keyinfo->rb_tree.allocated;
129 if (!tree_insert(&keyinfo->rb_tree, (void*)info->recbuf,
130 custom_arg.key_length, &custom_arg))
131 {
132 my_errno= HA_ERR_FOUND_DUPP_KEY;
133 return 1;
134 }
135 info->s->index_length+= (keyinfo->rb_tree.allocated-old_allocated);
136 return 0;
137 }
138
139 /* Find where to place new record */
140
next_free_record_pos(HP_SHARE * info)141 static uchar *next_free_record_pos(HP_SHARE *info)
142 {
143 int block_pos;
144 uchar *pos;
145 size_t length;
146 DBUG_ENTER("next_free_record_pos");
147
148 if (info->del_link)
149 {
150 pos=info->del_link;
151 info->del_link= *((uchar**) pos);
152 info->deleted--;
153 DBUG_PRINT("exit",("Used old position: 0x%lx",(long) pos));
154 DBUG_RETURN(pos);
155 }
156 if (!(block_pos=(info->records % info->block.records_in_block)))
157 {
158 if ((info->records > info->max_records && info->max_records) ||
159 (info->data_length + info->index_length >= info->max_table_size))
160 {
161 my_errno=HA_ERR_RECORD_FILE_FULL;
162 DBUG_RETURN(NULL);
163 }
164 if (hp_get_new_block(&info->block,&length))
165 DBUG_RETURN(NULL);
166 info->data_length+=length;
167 }
168 DBUG_PRINT("exit",("Used new position: 0x%lx",
169 (long) ((uchar*) info->block.level_info[0].last_blocks+
170 block_pos * info->block.recbuffer)));
171 DBUG_RETURN((uchar*) info->block.level_info[0].last_blocks+
172 block_pos*info->block.recbuffer);
173 }
174
175
176 /*
177 Write a hash-key to the hash-index
178 SYNOPSIS
179 info Heap table info
180 keyinfo Key info
181 record Table record to added
182 recpos Memory buffer where the table record will be stored if added
183 successfully
184 NOTE
185 Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO
186 structs. Array size == number of entries in hash index.
187 hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
188 If there are several hash entries with the same hash array position P,
189 they are connected in a linked list via HASH_INFO::next_key. The first
190 list element is located at position P, next elements are located at
191 positions for which there is no record that should be located at that
192 position. The order of elements in the list is arbitrary.
193
194 RETURN
195 0 - OK
196 -1 - Out of memory
197 HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was
198 still added and the caller must call hp_delete_key for it.
199 */
200
hp_write_key(HP_INFO * info,HP_KEYDEF * keyinfo,const uchar * record,uchar * recpos)201 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
202 const uchar *record, uchar *recpos)
203 {
204 HP_SHARE *share = info->s;
205 int flag;
206 ulong halfbuff,hashnr,first_index;
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 = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
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 ptr_to_rec=pos->ptr_to_rec;
270 empty=pos; /* This place is now free */
271 }
272 else
273 {
274 /*
275 We can only get here at first iteration: key is at 'lower'
276 position pos and should be left here.
277 */
278 flag=LOWFIND | LOWUSED;
279 gpos=pos;
280 ptr_to_rec=pos->ptr_to_rec;
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 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
292 }
293 gpos=pos;
294 ptr_to_rec=pos->ptr_to_rec;
295 }
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 ptr_to_rec2=pos->ptr_to_rec;
307 }
308 else
309 {
310 if (!(flag & HIGHUSED))
311 {
312 /* Change link of previous upper-list key and save */
313 gpos2->ptr_to_rec=ptr_to_rec2;
314 gpos2->next_key=pos;
315 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
316 }
317 gpos2=pos;
318 ptr_to_rec2=pos->ptr_to_rec;
319 }
320 }
321 }
322 while ((pos=pos->next_key));
323
324 if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
325 {
326 /*
327 If both 'higher' and 'lower' list have at least one element, now
328 there are two hash buckets instead of one.
329 */
330 keyinfo->hash_buckets++;
331 }
332
333 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
334 {
335 gpos->ptr_to_rec=ptr_to_rec;
336 gpos->next_key=0;
337 }
338 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
339 {
340 gpos2->ptr_to_rec=ptr_to_rec2;
341 gpos2->next_key=0;
342 }
343 }
344 /* Check if we are at the empty position */
345
346 pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
347 share->blength, share->records + 1));
348 if (pos == empty)
349 {
350 pos->ptr_to_rec=recpos;
351 pos->next_key=0;
352 keyinfo->hash_buckets++;
353 }
354 else
355 {
356 /* Check if more records in same hash-nr family */
357 empty[0]=pos[0];
358 gpos=hp_find_hash(&keyinfo->block,
359 hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
360 share->blength, share->records + 1));
361 if (pos == gpos)
362 {
363 pos->ptr_to_rec=recpos;
364 pos->next_key=empty;
365 }
366 else
367 {
368 keyinfo->hash_buckets++;
369 pos->ptr_to_rec=recpos;
370 pos->next_key=0;
371 hp_movelink(pos, gpos, empty);
372 }
373
374 /* Check if duplicated keys */
375 if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
376 (!(keyinfo->flag & HA_NULL_PART_KEY) ||
377 !hp_if_null_in_key(keyinfo, record)))
378 {
379 pos=empty;
380 do
381 {
382 if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec, 1))
383 {
384 DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
385 }
386 } while ((pos=pos->next_key));
387 }
388 }
389 DBUG_RETURN(0);
390 }
391
392 /* Returns ptr to block, and allocates block if neaded */
393
hp_find_free_hash(HP_SHARE * info,HP_BLOCK * block,ulong records)394 static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
395 HP_BLOCK *block, ulong records)
396 {
397 uint block_pos;
398 size_t length;
399
400 if (records < block->last_allocated)
401 return hp_find_hash(block,records);
402 if (!(block_pos=(records % block->records_in_block)))
403 {
404 if (hp_get_new_block(block,&length))
405 return(NULL);
406 info->index_length+=length;
407 }
408 block->last_allocated=records+1;
409 return((HASH_INFO*) ((uchar*) block->level_info[0].last_blocks+
410 block_pos*block->recbuffer));
411 }
412