1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates.
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, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23 /* Write a record to heap-databas */
24
25 #include "heapdef.h"
26 #ifdef _WIN32
27 #include <fcntl.h>
28 #endif
29
30 #define LOWFIND 1
31 #define LOWUSED 2
32 #define HIGHFIND 4
33 #define HIGHUSED 8
34
35 static uchar *next_free_record_pos(HP_SHARE *info);
36 static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
37 ulong records);
38
heap_write(HP_INFO * info,const uchar * record)39 int heap_write(HP_INFO *info, const uchar *record)
40 {
41 HP_KEYDEF *keydef, *end;
42 uchar *pos;
43 HP_SHARE *share=info->s;
44 DBUG_ENTER("heap_write");
45 #ifndef NDEBUG
46 if (info->mode & O_RDONLY)
47 {
48 set_my_errno(EACCES);
49 DBUG_RETURN(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(NDEBUG) && 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 set_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 set_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 Populate HASH_INFO structure.
178
179 @param key Pointer to a HASH_INFO key to be populated
180 @param next_key HASH_INFO next_key value
181 @param ptr_to_rec HASH_INFO ptr_to_rec value
182 @param hash HASH_INFO hash value
183 */
184
set_hash_key(HASH_INFO * key,HASH_INFO * next_key,uchar * ptr_to_rec,ulong hash)185 static inline void set_hash_key(HASH_INFO *key, HASH_INFO *next_key,
186 uchar *ptr_to_rec, ulong hash)
187 {
188 key->next_key= next_key;
189 key->ptr_to_rec= ptr_to_rec;
190 key->hash= hash;
191 }
192
193
194 /*
195 Write a hash-key to the hash-index
196 SYNOPSIS
197 info Heap table info
198 keyinfo Key info
199 record Table record to added
200 recpos Memory buffer where the table record will be stored if added
201 successfully
202 NOTE
203 Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO
204 structs. Array size == number of entries in hash index.
205 hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
206 If there are several hash entries with the same hash array position P,
207 they are connected in a linked list via HASH_INFO::next_key. The first
208 list element is located at position P, next elements are located at
209 positions for which there is no record that should be located at that
210 position. The order of elements in the list is arbitrary.
211
212 RETURN
213 0 - OK
214 -1 - Out of memory
215 HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was
216 still added and the caller must call hp_delete_key for it.
217 */
218
hp_write_key(HP_INFO * info,HP_KEYDEF * keyinfo,const uchar * record,uchar * recpos)219 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
220 const uchar *record, uchar *recpos)
221 {
222 HP_SHARE *share = info->s;
223 int flag;
224 ulong halfbuff,hashnr,first_index;
225 uchar *ptr_to_rec= NULL, *ptr_to_rec2= NULL;
226 ulong hash1= 0, hash2= 0;
227 HASH_INFO *empty, *gpos= NULL, *gpos2= NULL, *pos;
228 DBUG_ENTER("hp_write_key");
229
230 flag=0;
231 if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
232 DBUG_RETURN(-1); /* No more memory */
233 halfbuff= (long) share->blength >> 1;
234 pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
235
236 /*
237 We're about to add one more hash array position, with hash_mask=#records.
238 The number of hash positions will change and some entries might need to
239 be relocated to the newly added position. Those entries are currently
240 members of the list that starts at #first_index position (this is
241 guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
242 At #first_index position currently there may be either:
243 a) An entry with hashnr != first_index. We don't need to move it.
244 or
245 b) A list of items with hash_mask=first_index. The list contains entries
246 of 2 types:
247 1) entries that should be relocated to the list that starts at new
248 position we're adding ('uppper' list)
249 2) entries that should be left in the list starting at #first_index
250 position ('lower' list)
251 */
252 if (pos != empty) /* If some records */
253 {
254 do
255 {
256 hashnr= pos->hash;
257 if (flag == 0)
258 {
259 /*
260 First loop, bail out if we're dealing with case a) from above
261 comment
262 */
263 if (hp_mask(hashnr, share->blength, share->records) != first_index)
264 break;
265 }
266 /*
267 flag & LOWFIND - found a record that should be put into lower position
268 flag & LOWUSED - lower position occupied by the record
269 Same for HIGHFIND and HIGHUSED and 'upper' position
270
271 gpos - ptr to last element in lower position's list
272 gpos2 - ptr to last element in upper position's list
273
274 ptr_to_rec - ptr to last entry that should go into lower list.
275 ptr_to_rec2 - same for upper list.
276 */
277 if (!(hashnr & halfbuff))
278 {
279 /* Key should be put into 'lower' list */
280 if (!(flag & LOWFIND))
281 {
282 /* key is the first element to go into lower position */
283 if (flag & HIGHFIND)
284 {
285 flag=LOWFIND | HIGHFIND;
286 /* key shall be moved to the current empty position */
287 gpos=empty;
288 ptr_to_rec=pos->ptr_to_rec;
289 empty=pos; /* This place is now free */
290 }
291 else
292 {
293 /*
294 We can only get here at first iteration: key is at 'lower'
295 position pos and should be left here.
296 */
297 flag=LOWFIND | LOWUSED;
298 gpos=pos;
299 ptr_to_rec=pos->ptr_to_rec;
300 }
301 }
302 else
303 {
304 /* Already have another key for lower position */
305 if (!(flag & LOWUSED))
306 {
307 /* Change link of previous lower-list key */
308 set_hash_key(gpos, pos, ptr_to_rec, hash1);
309 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
310 }
311 gpos=pos;
312 ptr_to_rec=pos->ptr_to_rec;
313 }
314 hash1= pos->hash;
315 }
316 else
317 {
318 /* key will be put into 'higher' list */
319 if (!(flag & HIGHFIND))
320 {
321 flag= (flag & LOWFIND) | HIGHFIND;
322 /* key shall be moved to the last (empty) position */
323 gpos2= empty;
324 empty= pos;
325 ptr_to_rec2=pos->ptr_to_rec;
326 }
327 else
328 {
329 if (!(flag & HIGHUSED))
330 {
331 /* Change link of previous upper-list key and save */
332 set_hash_key(gpos2, pos, ptr_to_rec2, hash2);
333 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
334 }
335 gpos2=pos;
336 ptr_to_rec2=pos->ptr_to_rec;
337 }
338 hash2= pos->hash;
339 }
340 }
341 while ((pos=pos->next_key));
342
343 if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
344 {
345 /*
346 If both 'higher' and 'lower' list have at least one element, now
347 there are two hash buckets instead of one.
348 */
349 keyinfo->hash_buckets++;
350 }
351
352 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
353 {
354 set_hash_key(gpos, NULL, ptr_to_rec, hash1);
355 }
356 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
357 {
358 set_hash_key(gpos2, NULL, ptr_to_rec2, hash2);
359 }
360 }
361 /* Check if we are at the empty position */
362 hash1= hp_rec_hashnr(keyinfo, record);
363 pos= hp_find_hash(&keyinfo->block, hp_mask(hash1, share->blength,
364 share->records + 1));
365 if (pos == empty)
366 {
367 set_hash_key(pos, NULL, recpos, hash1);
368 keyinfo->hash_buckets++;
369 }
370 else
371 {
372 /* Check if more records in same hash-nr family */
373 empty[0]=pos[0];
374 gpos= hp_find_hash(&keyinfo->block, hp_mask(pos->hash, share->blength,
375 share->records + 1));
376 if (pos == gpos)
377 {
378 set_hash_key(pos, empty, recpos, hash1);
379 }
380 else
381 {
382 set_hash_key(pos, NULL, recpos, hash1);
383 keyinfo->hash_buckets++;
384 hp_movelink(pos, gpos, empty);
385 }
386
387 /* Check if duplicated keys */
388 if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
389 (!(keyinfo->flag & HA_NULL_PART_KEY) ||
390 !hp_if_null_in_key(keyinfo, record)))
391 {
392 pos=empty;
393 do
394 {
395 if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec, 1))
396 {
397 set_my_errno(HA_ERR_FOUND_DUPP_KEY);
398 DBUG_RETURN(HA_ERR_FOUND_DUPP_KEY);
399 }
400 } while ((pos=pos->next_key));
401 }
402 }
403 DBUG_RETURN(0);
404 }
405
406 /* Returns ptr to block, and allocates block if neaded */
407
hp_find_free_hash(HP_SHARE * info,HP_BLOCK * block,ulong records)408 static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
409 HP_BLOCK *block, ulong records)
410 {
411 uint block_pos;
412 size_t length;
413
414 if (records < block->last_allocated)
415 return hp_find_hash(block,records);
416 if (!(block_pos=(records % block->records_in_block)))
417 {
418 if (hp_get_new_block(block,&length))
419 return(NULL);
420 info->index_length+=length;
421 }
422 block->last_allocated=records+1;
423 return((HASH_INFO*) ((uchar*) block->level_info[0].last_blocks+
424 block_pos*block->recbuffer));
425 }
426