Drizzled Public API Documentation

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 
28 using namespace drizzled;
29 using namespace std;
30 
31 static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key);
32 static 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 
39 unsigned char *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
40  uint32_t nextflag)
41 {
42  register 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 
114 unsigned 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 
144 uint32_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 
158 void 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 
172 static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register 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 
237 uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register 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 
312 int 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 
399 static 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 
483 void 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 
521 bool 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 
547 void 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 }