drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
hp_hash.cc
1/* Copyright (C) 2000-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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16/* The hash functions used for saveing keys */
17
18#include "heap_priv.h"
19#include <drizzled/error_t.h>
20#include <drizzled/charset.h>
21#include <drizzled/util/test.h>
22
23#include <math.h>
24#include <string.h>
25
26#include <cassert>
27
28using namespace drizzled;
29using namespace std;
30
31static uint32_t hp_hashnr(HP_KEYDEF *keydef, const unsigned char *key);
32static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key);
33
34
35 /* Search after a record based on a key */
36 /* Sets info->current_ptr to found record */
37 /* next_flag: Search=0, next=1, prev =2, same =3 */
38
39unsigned char *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
40 uint32_t nextflag)
41{
42 HASH_INFO *pos,*prev_ptr;
43 int flag;
44 uint32_t old_nextflag;
45 HP_SHARE *share=info->getShare();
46 old_nextflag=nextflag;
47 flag=1;
48 prev_ptr=0;
49
50 if (share->records)
51 {
52 pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
53 share->blength, share->records));
54 do
55 {
56 if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
57 {
58 switch (nextflag) {
59 case 0: /* Search after key */
60 info->current_hash_ptr=pos;
61 return(info->current_ptr= pos->ptr_to_rec);
62 case 1: /* Search next */
63 if (pos->ptr_to_rec == info->current_ptr)
64 nextflag=0;
65 break;
66 case 2: /* Search previous */
67 if (pos->ptr_to_rec == info->current_ptr)
68 {
69 errno=HA_ERR_KEY_NOT_FOUND; /* If gpos == 0 */
70 info->current_hash_ptr=prev_ptr;
71 return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
72 }
73 prev_ptr=pos; /* Prev. record found */
74 break;
75 case 3: /* Search same */
76 if (pos->ptr_to_rec == info->current_ptr)
77 {
78 info->current_hash_ptr=pos;
79 return(info->current_ptr);
80 }
81 }
82 }
83 if (flag)
84 {
85 flag=0; /* Reset flag */
86 if (hp_find_hash(&keyinfo->block,
87 hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
88 share->blength, share->records)) != pos)
89 break; /* Wrong link */
90 }
91 }
92 while ((pos=pos->next_key));
93 }
94 errno=HA_ERR_KEY_NOT_FOUND;
95 if (nextflag == 2 && ! info->current_ptr)
96 {
97 /* Do a previous from end */
98 info->current_hash_ptr=prev_ptr;
99 return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
100 }
101
102 if (old_nextflag && nextflag)
103 errno=HA_ERR_RECORD_CHANGED; /* Didn't find old record */
104 info->current_hash_ptr=0;
105 return((info->current_ptr= 0));
106}
107
108
109/*
110 Search next after last read; Assumes that the table hasn't changed
111 since last read !
112*/
113
114unsigned char *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
115 HASH_INFO *pos)
116{
117 while ((pos= pos->next_key))
118 {
119 if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
120 {
121 info->current_hash_ptr=pos;
122 return (info->current_ptr= pos->ptr_to_rec);
123 }
124 }
125 errno=HA_ERR_KEY_NOT_FOUND;
126 info->current_hash_ptr=0;
127 return ((info->current_ptr= 0));
128}
129
130
131/*
132 Calculate position number for hash value.
133 SYNOPSIS
134 hp_mask()
135 hashnr Hash value
136 buffmax Value such that
137 2^(n-1) < maxlength <= 2^n = buffmax
138 maxlength
139
140 RETURN
141 Array index, in [0..maxlength)
142*/
143
144uint32_t hp_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength)
145{
146 if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
147 return (hashnr & ((buffmax >> 1) -1));
148}
149
150
151/*
152 Change
153 next_link -> ... -> X -> pos
154 to
155 next_link -> ... -> X -> newlink
156*/
157
158void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
159{
160 HASH_INFO *old_link;
161 do
162 {
163 old_link=next_link;
164 }
165 while ((next_link=next_link->next_key) != pos);
166 old_link->next_key=newlink;
167 return;
168}
169
170 /* Calc hashvalue for a key */
171
172static uint32_t hp_hashnr(HP_KEYDEF *keydef, const unsigned char *key)
173{
174 /*register*/
175 uint32_t nr=1, nr2=4;
176 HA_KEYSEG *seg,*endseg;
177
178 for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
179 {
180 unsigned char *pos=(unsigned char*) key;
181 key+=seg->length;
182 if (seg->null_bit)
183 {
184 key++; /* Skip null byte */
185 if (*pos) /* Found null */
186 {
187 nr^= (nr << 1) | 1;
188 /* Add key pack length (2) to key for VARCHAR segments */
189 if (seg->type == HA_KEYTYPE_VARTEXT1)
190 key+= 2;
191 continue;
192 }
193 pos++;
194 }
195 if (seg->type == HA_KEYTYPE_TEXT)
196 {
197 const charset_info_st * const cs= seg->charset;
198 uint32_t length= seg->length;
199 if (cs->mbmaxlen > 1)
200 {
201 uint32_t char_length;
202 char_length= my_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
203 set_if_smaller(length, char_length);
204 }
205 cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
206 }
207 else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
208 {
209 const charset_info_st * const cs= seg->charset;
210 uint32_t pack_length= 2; /* Key packing is constant */
211 uint32_t length= uint2korr(pos);
212 if (cs->mbmaxlen > 1)
213 {
214 uint32_t char_length;
215 char_length= my_charpos(cs, pos +pack_length,
216 pos +pack_length + length,
217 seg->length/cs->mbmaxlen);
218 set_if_smaller(length, char_length);
219 }
220 cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
221 key+= pack_length;
222 }
223 else
224 {
225 for (; pos < (unsigned char*) key ; pos++)
226 {
227 nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
228 nr2+=3;
229 }
230 }
231 }
232 return((uint32_t) nr);
233}
234
235 /* Calc hashvalue for a key in a record */
236
237uint32_t hp_rec_hashnr(HP_KEYDEF *keydef, const unsigned char *rec)
238{
239 uint32_t nr=1, nr2=4;
240 HA_KEYSEG *seg,*endseg;
241
242 for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
243 {
244 unsigned char *pos=(unsigned char*) rec+seg->start,*end=pos+seg->length;
245 if (seg->null_bit)
246 {
247 if (rec[seg->null_pos] & seg->null_bit)
248 {
249 nr^= (nr << 1) | 1;
250 continue;
251 }
252 }
253 if (seg->type == HA_KEYTYPE_TEXT)
254 {
255 const charset_info_st * const cs= seg->charset;
256 uint32_t char_length= seg->length;
257 if (cs->mbmaxlen > 1)
258 {
259 char_length= my_charpos(cs, pos, pos + char_length,
260 char_length / cs->mbmaxlen);
261 set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
262 }
263 cs->coll->hash_sort(cs, pos, char_length, &nr, &nr2);
264 }
265 else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
266 {
267 const charset_info_st * const cs= seg->charset;
268 uint32_t pack_length= seg->bit_start;
269 uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
270 if (cs->mbmaxlen > 1)
271 {
272 uint32_t char_length;
273 char_length= my_charpos(cs, pos + pack_length,
274 pos + pack_length + length,
275 seg->length/cs->mbmaxlen);
276 set_if_smaller(length, char_length);
277 }
278 cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
279 }
280 else
281 {
282 for (; pos < end ; pos++)
283 {
284 nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
285 nr2+=3;
286 }
287 }
288 }
289 return(nr);
290}
291
292/*
293 Compare keys for two records. Returns 0 if they are identical
294
295 SYNOPSIS
296 hp_rec_key_cmp()
297 keydef Key definition
298 rec1 Record to compare
299 rec2 Other record to compare
300 diff_if_only_endspace_difference
301 Different number of end space is significant
302
303 NOTES
304 diff_if_only_endspace_difference is used to allow us to insert
305 'a' and 'a ' when there is an an unique key.
306
307 RETURN
308 0 Key is identical
309 <> 0 Key differes
310*/
311
312int hp_rec_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec1, const unsigned char *rec2,
313 bool diff_if_only_endspace_difference)
314{
315 HA_KEYSEG *seg,*endseg;
316
317 for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
318 {
319 if (seg->null_bit)
320 {
321 if ((rec1[seg->null_pos] & seg->null_bit) !=
322 (rec2[seg->null_pos] & seg->null_bit))
323 return 1;
324 if (rec1[seg->null_pos] & seg->null_bit)
325 continue;
326 }
327 if (seg->type == HA_KEYTYPE_TEXT)
328 {
329 const charset_info_st * const cs= seg->charset;
330 uint32_t char_length1;
331 uint32_t char_length2;
332 unsigned char *pos1= (unsigned char*)rec1 + seg->start;
333 unsigned char *pos2= (unsigned char*)rec2 + seg->start;
334 if (cs->mbmaxlen > 1)
335 {
336 uint32_t char_length= seg->length / cs->mbmaxlen;
337 char_length1= my_charpos(cs, pos1, pos1 + seg->length, char_length);
338 set_if_smaller(char_length1, (uint32_t)seg->length);
339 char_length2= my_charpos(cs, pos2, pos2 + seg->length, char_length);
340 set_if_smaller(char_length2, (uint32_t)seg->length);
341 }
342 else
343 {
344 char_length1= char_length2= seg->length;
345 }
346 if (seg->charset->coll->strnncollsp(seg->charset,
347 pos1,char_length1,
348 pos2,char_length2, 0))
349 return 1;
350 }
351 else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
352 {
353 unsigned char *pos1= (unsigned char*) rec1 + seg->start;
354 unsigned char *pos2= (unsigned char*) rec2 + seg->start;
355 uint32_t char_length1, char_length2;
356 uint32_t pack_length= seg->bit_start;
357 const charset_info_st * const cs= seg->charset;
358 if (pack_length == 1)
359 {
360 char_length1= (uint) *(unsigned char*) pos1++;
361 char_length2= (uint) *(unsigned char*) pos2++;
362 }
363 else
364 {
365 char_length1= uint2korr(pos1);
366 char_length2= uint2korr(pos2);
367 pos1+= 2;
368 pos2+= 2;
369 }
370 if (cs->mbmaxlen > 1)
371 {
372 uint32_t safe_length1= char_length1;
373 uint32_t safe_length2= char_length2;
374 uint32_t char_length= seg->length / cs->mbmaxlen;
375 char_length1= my_charpos(cs, pos1, pos1 + char_length1, char_length);
376 set_if_smaller(char_length1, safe_length1);
377 char_length2= my_charpos(cs, pos2, pos2 + char_length2, char_length);
378 set_if_smaller(char_length2, safe_length2);
379 }
380
381 if (cs->coll->strnncollsp(seg->charset,
382 pos1, char_length1,
383 pos2, char_length2,
384 seg->flag & HA_END_SPACE_ARE_EQUAL ?
385 0 : diff_if_only_endspace_difference))
386 return 1;
387 }
388 else
389 {
390 if (memcmp(rec1+seg->start,rec2+seg->start,seg->length))
391 return 1;
392 }
393 }
394 return 0;
395}
396
397 /* Compare a key in a record to a whole key */
398
399static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
400{
401 HA_KEYSEG *seg,*endseg;
402
403 for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
404 seg < endseg ;
405 key+= (seg++)->length)
406 {
407 if (seg->null_bit)
408 {
409 int found_null=test(rec[seg->null_pos] & seg->null_bit);
410 if (found_null != (int) *key++)
411 return 1;
412 if (found_null)
413 {
414 /* Add key pack length (2) to key for VARCHAR segments */
415 if (seg->type == HA_KEYTYPE_VARTEXT1)
416 key+= 2;
417 continue;
418 }
419 }
420 if (seg->type == HA_KEYTYPE_TEXT)
421 {
422 const charset_info_st * const cs= seg->charset;
423 uint32_t char_length_key;
424 uint32_t char_length_rec;
425 unsigned char *pos= (unsigned char*) rec + seg->start;
426 if (cs->mbmaxlen > 1)
427 {
428 uint32_t char_length= seg->length / cs->mbmaxlen;
429 char_length_key= my_charpos(cs, key, key + seg->length, char_length);
430 set_if_smaller(char_length_key, (uint32_t)seg->length);
431 char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
432 set_if_smaller(char_length_rec, (uint32_t)seg->length);
433 }
434 else
435 {
436 char_length_key= seg->length;
437 char_length_rec= seg->length;
438 }
439
440 if (seg->charset->coll->strnncollsp(seg->charset,
441 (unsigned char*) pos, char_length_rec,
442 (unsigned char*) key, char_length_key, 0))
443 return 1;
444 }
445 else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
446 {
447 unsigned char *pos= (unsigned char*) rec + seg->start;
448 const charset_info_st * const cs= seg->charset;
449 uint32_t pack_length= seg->bit_start;
450 uint32_t char_length_rec= (pack_length == 1 ? (uint) *(unsigned char*) pos :
451 uint2korr(pos));
452 /* Key segments are always packed with 2 bytes */
453 uint32_t char_length_key= uint2korr(key);
454 pos+= pack_length;
455 key+= 2; /* skip key pack length */
456 if (cs->mbmaxlen > 1)
457 {
458 uint32_t char_length1, char_length2;
459 char_length1= char_length2= seg->length / cs->mbmaxlen;
460 char_length1= my_charpos(cs, key, key + char_length_key, char_length1);
461 set_if_smaller(char_length_key, char_length1);
462 char_length2= my_charpos(cs, pos, pos + char_length_rec, char_length2);
463 set_if_smaller(char_length_rec, char_length2);
464 }
465
466 if (cs->coll->strnncollsp(seg->charset,
467 (unsigned char*) pos, char_length_rec,
468 (unsigned char*) key, char_length_key, 0))
469 return 1;
470 }
471 else
472 {
473 if (memcmp(rec+seg->start,key,seg->length))
474 return 1;
475 }
476 }
477 return 0;
478}
479
480
481 /* Copy a key from a record to a keybuffer */
482
483void hp_make_key(HP_KEYDEF *keydef, unsigned char *key, const unsigned char *rec)
484{
485 HA_KEYSEG *seg,*endseg;
486
487 for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
488 {
489 const charset_info_st * const cs= seg->charset;
490 uint32_t char_length= seg->length;
491 unsigned char *pos= (unsigned char*) rec + seg->start;
492 if (seg->null_bit)
493 *key++= test(rec[seg->null_pos] & seg->null_bit);
494 if (cs->mbmaxlen > 1)
495 {
496 char_length= my_charpos(cs, pos, pos + seg->length,
497 char_length / cs->mbmaxlen);
498 set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
499 }
500 if (seg->type == HA_KEYTYPE_VARTEXT1)
501 char_length+= seg->bit_start; /* Copy also length */
502 memcpy(key,rec+seg->start,(size_t) char_length);
503 key+= char_length;
504 }
505}
506
507#define FIX_LENGTH(cs, pos, length, char_length) \
508 do { \
509 if (length > char_length) \
510 char_length= my_charpos(cs, pos, pos+length, char_length); \
511 set_if_smaller(char_length,length); \
512 } while(0)
513
514/*
515 Test if any of the key parts are NULL.
516 Return:
517 1 if any of the key parts was NULL
518 0 otherwise
519*/
520
521bool hp_if_null_in_key(HP_KEYDEF *keydef, const unsigned char *record)
522{
523 HA_KEYSEG *seg,*endseg;
524 for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
525 {
526 if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
527 return 1;
528 }
529 return 0;
530}
531
532
533/*
534 Update auto_increment info
535
536 SYNOPSIS
537 update_auto_increment()
538 info MyISAM handler
539 record Row to update
540
541 IMPLEMENTATION
542 Only replace the auto_increment value if it is higher than the previous
543 one. For signed columns we don't update the auto increment value if it's
544 less than zero.
545*/
546
547void heap_update_auto_increment(HP_INFO *info, const unsigned char *record)
548{
549 uint64_t value= 0; /* Store unsigned values here */
550 int64_t s_value= 0; /* Store signed values here */
551
552 HA_KEYSEG *keyseg= info->getShare()->keydef[info->getShare()->auto_key - 1].seg;
553 const unsigned char *key= (unsigned char*) record + keyseg->start;
554
555 switch (info->getShare()->auto_key_type) {
556 case HA_KEYTYPE_BINARY:
557 value=(uint64_t) *(unsigned char*) key;
558 break;
559 case HA_KEYTYPE_LONG_INT:
560 s_value= (int64_t) sint4korr(key);
561 break;
562 case HA_KEYTYPE_ULONG_INT:
563 value=(uint64_t) uint4korr(key);
564 break;
565 case HA_KEYTYPE_DOUBLE: /* This shouldn't be used */
566 {
567 double f_1;
568 float8get(f_1,key);
569 /* Ignore negative values */
570 value = (f_1 < 0.0) ? 0 : (uint64_t) f_1;
571 break;
572 }
573 case HA_KEYTYPE_LONGLONG:
574 s_value= sint8korr(key);
575 break;
576 case HA_KEYTYPE_ULONGLONG:
577 value= uint8korr(key);
578 break;
579 default:
580 assert(0);
581 value=0; /* Error */
582 break;
583 }
584
585 /*
586 The following code works becasue if s_value < 0 then value is 0
587 and if s_value == 0 then value will contain either s_value or the
588 correct value.
589 */
590 set_if_bigger(info->getShare()->auto_increment,
591 (s_value > 0) ? (uint64_t) s_value : value);
592}
TODO: Rename this file - func.h is stupid.
STL namespace.