Drizzled Public API Documentation

key.cc
00001 /* Copyright (C) 2000-2006 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 
00017 /* Functions to handle keys and fields in forms */
00018 
00019 #include <config.h>
00020 #include <drizzled/table.h>
00021 #include <drizzled/key.h>
00022 #include <drizzled/field/blob.h>
00023 #include <drizzled/util/test.h>
00024 #include <drizzled/plugin/storage_engine.h>
00025 
00026 #include <boost/dynamic_bitset.hpp>
00027 
00028 #include <string>
00029 
00030 #include <algorithm>
00031 
00032 using namespace std;
00033 
00034 namespace drizzled
00035 {
00036 
00037 /*
00038   Search after a key that starts with 'field'
00039 
00040   SYNOPSIS
00041     find_ref_key()
00042     key     First key to check
00043     key_count   How many keys to check
00044     record    Start of record
00045     field   Field to search after
00046     key_length    On partial match, contains length of fields before
00047       field
00048     keypart             key part # of a field
00049 
00050   NOTES
00051    Used when calculating key for NEXT_NUMBER
00052 
00053   IMPLEMENTATION
00054     If no key starts with field test if field is part of some key. If we find
00055     one, then return first key and set key_length to the number of bytes
00056     preceding 'field'.
00057 
00058   RETURN
00059    -1  field is not part of the key
00060    #   Key part for key matching key.
00061        key_length is set to length of key before (not including) field
00062 */
00063 
00064 int find_ref_key(KeyInfo *key, uint32_t key_count, unsigned char *record, Field *field,
00065                  uint32_t *key_length, uint32_t *keypart)
00066 {
00067   int i;
00068   KeyInfo *key_info;
00069   uint32_t fieldpos;
00070 
00071   fieldpos= field->offset(record);
00072 
00073   /* Test if some key starts as fieldpos */
00074   for (i= 0, key_info= key ;
00075        i < (int) key_count ;
00076        i++, key_info++)
00077   {
00078     if (key_info->key_part[0].offset == fieldpos)
00079     {                                     /* Found key. Calc keylength */
00080       *key_length= *keypart= 0;
00081       return i;                                 /* Use this key */
00082     }
00083   }
00084 
00085   /* Test if some key contains fieldpos */
00086   for (i= 0, key_info= key;
00087        i < (int) key_count ;
00088        i++, key_info++)
00089   {
00090     uint32_t j;
00091     KeyPartInfo *key_part;
00092     *key_length=0;
00093     for (j=0, key_part=key_info->key_part ;
00094    j < key_info->key_parts ;
00095    j++, key_part++)
00096     {
00097       if (key_part->offset == fieldpos)
00098       {
00099         *keypart= j;
00100         return i;                               /* Use this key */
00101       }
00102       *key_length+= key_part->store_length;
00103     }
00104   }
00105   return(-1);         /* No key is ok */
00106 }
00107 
00108 
00109 void key_copy(unsigned char *to_key, unsigned char *from_record, KeyInfo *key_info,
00110               unsigned int key_length)
00111 {
00112   uint32_t length;
00113   KeyPartInfo *key_part;
00114 
00115   if (key_length == 0)
00116     key_length= key_info->key_length;
00117   for (key_part= key_info->key_part; (int) key_length > 0; key_part++)
00118   {
00119     if (key_part->null_bit)
00120     {
00121       *to_key++= test(from_record[key_part->null_offset] &
00122        key_part->null_bit);
00123       key_length--;
00124     }
00125     if (key_part->key_part_flag & HA_BLOB_PART ||
00126         key_part->key_part_flag & HA_VAR_LENGTH_PART)
00127     {
00128       key_length-= HA_KEY_BLOB_LENGTH;
00129       length= min((uint16_t)key_length, key_part->length);
00130       key_part->field->get_key_image(to_key, length);
00131       to_key+= HA_KEY_BLOB_LENGTH;
00132     }
00133     else
00134     {
00135       length= min((uint16_t)key_length, key_part->length);
00136       Field *field= key_part->field;
00137       const CHARSET_INFO * const cs= field->charset();
00138       uint32_t bytes= field->get_key_image(to_key, length);
00139       if (bytes < length)
00140         cs->cset->fill(cs, (char*) to_key + bytes, length - bytes, ' ');
00141     }
00142     to_key+= length;
00143     key_length-= length;
00144   }
00145 }
00146 
00147 
00152 void key_zero_nulls(unsigned char *tuple, KeyInfo *key_info)
00153 {
00154   KeyPartInfo *key_part= key_info->key_part;
00155   KeyPartInfo *key_part_end= key_part + key_info->key_parts;
00156   for (; key_part != key_part_end; key_part++)
00157   {
00158     if (key_part->null_bit && *tuple)
00159       memset(tuple+1, 0, key_part->store_length-1);
00160     tuple+= key_part->store_length;
00161   }
00162 }
00163 
00164 
00165 /*
00166   Restore a key from some buffer to record.
00167 
00168     This function converts a key into record format. It can be used in cases
00169     when we want to return a key as a result row.
00170 
00171   @param to_record   record buffer where the key will be restored to
00172   @param from_key    buffer that contains a key
00173   @param key_info    descriptor of the index
00174   @param key_length  specifies length of all keyparts that will be restored
00175 */
00176 
00177 void key_restore(unsigned char *to_record, unsigned char *from_key, KeyInfo *key_info,
00178                  uint16_t key_length)
00179 {
00180   uint32_t length;
00181   KeyPartInfo *key_part;
00182 
00183   if (key_length == 0)
00184   {
00185     key_length= key_info->key_length;
00186   }
00187   for (key_part= key_info->key_part ; (int) key_length > 0 ; key_part++)
00188   {
00189     unsigned char used_uneven_bits= 0;
00190     if (key_part->null_bit)
00191     {
00192       if (*from_key++)
00193   to_record[key_part->null_offset]|= key_part->null_bit;
00194       else
00195   to_record[key_part->null_offset]&= ~key_part->null_bit;
00196       key_length--;
00197     }
00198     if (key_part->key_part_flag & HA_BLOB_PART)
00199     {
00200       /*
00201         This in fact never happens, as we have only partial BLOB
00202         keys yet anyway, so it's difficult to find any sence to
00203         restore the part of a record.
00204         Maybe this branch is to be removed, but now we
00205         have to ignore GCov compaining.
00206 
00207         This may make more sense once we push down block lengths to the engine (aka partial retrieval).
00208       */
00209       uint32_t blob_length= uint2korr(from_key);
00210       Field_blob *field= (Field_blob*) key_part->field;
00211 
00212       field->setReadSet();
00213       from_key+= HA_KEY_BLOB_LENGTH;
00214       key_length-= HA_KEY_BLOB_LENGTH;
00215       field->set_ptr_offset(to_record - field->getTable()->getInsertRecord(),
00216                             (ulong) blob_length, from_key);
00217       length= key_part->length;
00218     }
00219     else if (key_part->key_part_flag & HA_VAR_LENGTH_PART)
00220     {
00221       Field *field= key_part->field;
00222       ptrdiff_t ptrdiff= to_record - field->getTable()->getInsertRecord();
00223 
00224       field->setReadSet();
00225       field->setWriteSet();
00226       field->move_field_offset(ptrdiff);
00227       key_length-= HA_KEY_BLOB_LENGTH;
00228       length= min(key_length, key_part->length);
00229       field->set_key_image(from_key, length);
00230       from_key+= HA_KEY_BLOB_LENGTH;
00231       field->move_field_offset(-ptrdiff);
00232     }
00233     else
00234     {
00235       length= min(key_length, key_part->length);
00236       /* skip the byte with 'uneven' bits, if used */
00237       memcpy(to_record + key_part->offset, from_key + used_uneven_bits
00238              , (size_t) length - used_uneven_bits);
00239     }
00240     from_key+= length;
00241     key_length-= length;
00242   }
00243 }
00244 
00245 
00266 bool key_cmp_if_same(Table *table,const unsigned char *key,uint32_t idx,uint32_t key_length)
00267 {
00268   uint32_t store_length;
00269   KeyPartInfo *key_part;
00270   const unsigned char *key_end= key + key_length;;
00271 
00272   for (key_part=table->key_info[idx].key_part;
00273        key < key_end ;
00274        key_part++, key+= store_length)
00275   {
00276     uint32_t length;
00277     store_length= key_part->store_length;
00278 
00279     if (key_part->null_bit)
00280     {
00281       if (*key != test(table->getInsertRecord()[key_part->null_offset] &
00282            key_part->null_bit))
00283   return 1;
00284       if (*key)
00285   continue;
00286       key++;
00287       store_length--;
00288     }
00289     if (key_part->key_part_flag & (HA_BLOB_PART | HA_VAR_LENGTH_PART |
00290                                    HA_BIT_PART))
00291     {
00292       if (key_part->field->key_cmp(key, key_part->length))
00293   return 1;
00294       continue;
00295     }
00296     length= min((uint32_t) (key_end-key), store_length);
00297     if (key_part->field->type() == DRIZZLE_TYPE_VARCHAR)
00298     {
00299       const CHARSET_INFO * const cs= key_part->field->charset();
00300       uint32_t char_length= key_part->length / cs->mbmaxlen;
00301       const unsigned char *pos= table->getInsertRecord() + key_part->offset;
00302       if (length > char_length)
00303       {
00304         char_length= my_charpos(cs, pos, pos + length, char_length);
00305         set_if_smaller(char_length, length);
00306       }
00307       if (cs->coll->strnncollsp(cs,
00308                                 (const unsigned char*) key, length,
00309                                 (const unsigned char*) pos, char_length, 0))
00310         return 1;
00311       continue;
00312     }
00313     if (memcmp(key,table->getInsertRecord()+key_part->offset,length))
00314       return 1;
00315   }
00316   return 0;
00317 }
00318 
00319 /*
00320   unpack key-fields from record to some buffer.
00321 
00322   This is used mainly to get a good error message.  We temporary
00323   change the column bitmap so that all columns are readable.
00324 
00325   @param
00326      to   Store value here in an easy to read form
00327   @param
00328      table  Table to use
00329   @param
00330      idx  Key number
00331 */
00332 
00333 void key_unpack(String *to, const Table *table, uint32_t idx)
00334 {
00335   KeyPartInfo *key_part,*key_part_end;
00336   Field *field;
00337   String tmp;
00338 
00339   to->length(0);
00340   for (key_part=table->key_info[idx].key_part,key_part_end=key_part+
00341    table->key_info[idx].key_parts ;
00342        key_part < key_part_end;
00343        key_part++)
00344   {
00345     if (to->length())
00346       to->append('-');
00347     if (key_part->null_bit)
00348     {
00349       if (table->getInsertRecord()[key_part->null_offset] & key_part->null_bit)
00350       {
00351   to->append(STRING_WITH_LEN("NULL"));
00352   continue;
00353       }
00354     }
00355     if ((field= key_part->field))
00356     {
00357       const CHARSET_INFO * const cs= field->charset();
00358       field->setReadSet();
00359       field->val_str_internal(&tmp);
00360       if (cs->mbmaxlen > 1 &&
00361           table->getField(key_part->fieldnr - 1)->field_length !=
00362           key_part->length)
00363       {
00364         /*
00365           Prefix key, multi-byte charset.
00366           For the columns of type CHAR(N), the above val_str()
00367           call will return exactly "key_part->length" bytes,
00368           which can break a multi-byte characters in the middle.
00369           Align, returning not more than "char_length" characters.
00370         */
00371         uint32_t charpos, char_length= key_part->length / cs->mbmaxlen;
00372         if ((charpos= my_charpos(cs, tmp.c_ptr(),
00373                                  tmp.c_ptr() + tmp.length(),
00374                                  char_length)) < key_part->length)
00375           tmp.length(charpos);
00376       }
00377 
00378       if (key_part->length < field->pack_length())
00379         tmp.length(min(tmp.length(), static_cast<size_t>(key_part->length)));
00380       to->append(tmp);
00381     }
00382     else
00383       to->append(STRING_WITH_LEN("???"));
00384   }
00385 }
00386 
00387 
00388 /*
00389   Check if key uses field that is marked in passed field bitmap.
00390 
00391   SYNOPSIS
00392     is_key_used()
00393       table   Table object with which keys and fields are associated.
00394       idx     Key to be checked.
00395       fields  Bitmap of fields to be checked.
00396 
00397   NOTE
00398     This function uses Table::tmp_set bitmap so the caller should care
00399     about saving/restoring its state if it also uses this bitmap.
00400 
00401   RETURN VALUE
00402     TRUE   Key uses field from bitmap
00403     FALSE  Otherwise
00404 */
00405 
00406 bool is_key_used(Table *table, uint32_t idx, const boost::dynamic_bitset<>& fields)
00407 {
00408   table->tmp_set.reset();
00409   table->mark_columns_used_by_index_no_reset(idx, table->tmp_set);
00410   if (table->tmp_set.is_subset_of(fields))
00411     return 1;
00412 
00413   /*
00414     If table handler has primary key as part of the index, check that primary
00415     key is not updated
00416   */
00417   if (idx != table->getShare()->getPrimaryKey() && table->getShare()->hasPrimaryKey() &&
00418       (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
00419   {
00420     return is_key_used(table, table->getShare()->getPrimaryKey(), fields);
00421   }
00422   return 0;
00423 }
00424 
00425 
00440 int key_cmp(KeyPartInfo *key_part, const unsigned char *key, uint32_t key_length)
00441 {
00442   uint32_t store_length;
00443 
00444   for (const unsigned char *end=key + key_length;
00445        key < end;
00446        key+= store_length, key_part++)
00447   {
00448     int cmp;
00449     store_length= key_part->store_length;
00450     if (key_part->null_bit)
00451     {
00452       /* This key part allows null values; NULL is lower than everything */
00453       bool field_is_null= key_part->field->is_null();
00454       if (*key)                                 // If range key is null
00455       {
00456   /* the range is expecting a null value */
00457   if (!field_is_null)
00458     return 1;                             // Found key is > range
00459         /* null -- exact match, go to next key part */
00460   continue;
00461       }
00462       else if (field_is_null)
00463   return -1;                              // NULL is less than any value
00464       key++;          // Skip null byte
00465       store_length--;
00466     }
00467     if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
00468       return -1;
00469     if (cmp > 0)
00470       return 1;
00471   }
00472   return 0;                                     // Keys are equal
00473 }
00474 
00475 
00476 } /* namespace drizzled */