开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
opt_range.cc
资源名称：mysql-3.23.35.tar.gz　[点击查看]
上传用户：tsgydb
上传日期：2007-04-14
资源大小：10674k
文件大小：67k
源码类别：

MySQL数据库

开发平台：

Visual C++

opt_range.cc：源码内容
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  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; either version 2 of the License, or
  6.    (at your option) any later version.
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  13.    You should have received a copy of the GNU General Public License
  14.    along with this program; if not, write to the Free Software
  15.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  17. /*
  18.   TODO:
  19.   Fix that MAYBE_KEY are stored in the tree so that we can detect use
  20.   of full hash keys for queries like:
  22.   select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);
  24. */
  28. #ifdef __GNUC__
  29. #pragma implementation // gcc: Class implementation
  30. #endif
  32. #include "mysql_priv.h"
  33. #include <m_ctype.h>
  34. #include <nisam.h>
  35. #include "sql_select.h"
  38. #ifndef EXTRA_DEBUG
  39. #define test_rb_tree(A,B) {}
  40. #define test_use_count(A) {}
  41. #endif
  44. static int sel_cmp(Field *f,char *a,char *b,uint8 a_flag,uint8 b_flag);
  46. static char is_null_string[2]= {1,0};
  48. class SEL_ARG :public Sql_alloc
  49. {
  50. public:
  51.   uint8 min_flag,max_flag,maybe_flag;
  52.   uint8 part; // Which key part
  53.   uint8 maybe_null;
  54.   uint16 elements; // Elements in tree
  55.   ulong use_count; // use of this sub_tree
  56.   Field *field;
  57.   char *min_value,*max_value; // Pointer to range
  59.   SEL_ARG *left,*right,*next,*prev,*parent,*next_key_part;
  60.   enum leaf_color { BLACK,RED } color;
  61.   enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
  63.   SEL_ARG() {}
  64.   SEL_ARG(SEL_ARG &);
  65.   SEL_ARG(Field *,const char *,const char *);
  66.   SEL_ARG(Field *field, uint8 part, char *min_value, char *max_value,
  67.   uint8 min_flag, uint8 max_flag, uint8 maybe_flag);
  68.   SEL_ARG(enum Type type_arg)
  69.     :elements(1),use_count(1),left(0),next_key_part(0),type(type_arg) {}
  70.   inline bool is_same(SEL_ARG *arg)
  71.   {
  72.     if (type != arg->type)
  73.       return 0;
  74.     if (type != KEY_RANGE)
  75.       return 1;
  76.     return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
  77.   }
  78.   inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
  79.   inline void maybe_smaller() { maybe_flag=1; }
  80.   inline int cmp_min_to_min(SEL_ARG* arg)
  81.   {
  82.     return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
  83.   }
  84.   inline int cmp_min_to_max(SEL_ARG* arg)
  85.   {
  86.     return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
  87.   }
  88.   inline int cmp_max_to_max(SEL_ARG* arg)
  89.   {
  90.     return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
  91.   }
  92.   inline int cmp_max_to_min(SEL_ARG* arg)
  93.   {
  94.     return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
  95.   }
  96.   SEL_ARG *clone_and(SEL_ARG* arg)
  97.   { // Get overlapping range
  98.     char *new_min,*new_max;
  99.     uint8 flag_min,flag_max;
  100.     if (cmp_min_to_min(arg) >= 0)
  101.     {
  102.       new_min=min_value; flag_min=min_flag;
  103.     }
  104.     else
  105.     {
  106.       new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
  107.     }
  108.     if (cmp_max_to_max(arg) <= 0)
  109.     {
  110.       new_max=max_value; flag_max=max_flag;
  111.     }
  112.     else
  113.     {
  114.       new_max=arg->max_value; flag_max=arg->max_flag;
  115.     }
  116.     return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
  117.        test(maybe_flag && arg->maybe_flag));
  118.   }
  119.   SEL_ARG *clone_first(SEL_ARG *arg)
  120.   { // min <= X < arg->min
  121.     return new SEL_ARG(field,part, min_value, arg->min_value,
  122.        min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
  123.        maybe_flag | arg->maybe_flag);
  124.   }
  125.   SEL_ARG *clone_last(SEL_ARG *arg)
  126.   { // min <= X <= key_max
  127.     return new SEL_ARG(field, part, min_value, arg->max_value,
  128.        min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
  129.   }
  130.   SEL_ARG *clone(SEL_ARG *new_parent,SEL_ARG **next);
  132.   bool copy_min(SEL_ARG* arg)
  133.   { // Get overlapping range
  134.     if (cmp_min_to_min(arg) > 0)
  135.     {
  136.       min_value=arg->min_value; min_flag=arg->min_flag;
  137.       if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
  138.   (NO_MAX_RANGE | NO_MIN_RANGE))
  139. return 1; // Full range
  140.     }
  141.     maybe_flag|=arg->maybe_flag;
  142.     return 0;
  143.   }
  144.   bool copy_max(SEL_ARG* arg)
  145.   { // Get overlapping range
  146.     if (cmp_max_to_max(arg) <= 0)
  147.     {
  148.       max_value=arg->max_value; max_flag=arg->max_flag;
  149.       if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
  150.   (NO_MAX_RANGE | NO_MIN_RANGE))
  151. return 1; // Full range
  152.     }
  153.     maybe_flag|=arg->maybe_flag;
  154.     return 0;
  155.   }
  157.   void copy_min_to_min(SEL_ARG *arg)
  158.   {
  159.     min_value=arg->min_value; min_flag=arg->min_flag;
  160.   }
  161.   void copy_min_to_max(SEL_ARG *arg)
  162.   {
  163.     max_value=arg->min_value;
  164.     max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
  165.   }
  166.   void copy_max_to_min(SEL_ARG *arg)
  167.   {
  168.     min_value=arg->max_value;
  169.     min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
  170.   }
  171.   void store(uint length,char **min_key,uint min_key_flag,
  172.      char **max_key, uint max_key_flag)
  173.   {
  174.     if (!(min_flag & NO_MIN_RANGE) &&
  175. !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN)))
  176.     {
  177.       if (maybe_null && *min_value)
  178.       {
  179. **min_key=1;
  180. bzero(*min_key+1,length);
  181.       }
  182.       else
  183. memcpy(*min_key,min_value,length+(int) maybe_null);
  184.       (*min_key)+= length+(int) maybe_null;
  185.     }
  186.     if (!(max_flag & NO_MAX_RANGE) &&
  187. !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
  188.     {
  189.       if (maybe_null && *max_value)
  190.       {
  191. **max_key=1;
  192. bzero(*max_key+1,length);
  193.       }
  194.       else
  195. memcpy(*max_key,max_value,length+(int) maybe_null);
  196.       (*max_key)+= length+(int) maybe_null;
  197.     }
  198.   }
  200.   void store_min_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  201.   {
  202.     SEL_ARG *key_tree= first();
  203.     key_tree->store(key[key_tree->part].part_length,
  204.     range_key,*range_key_flag,range_key,NO_MAX_RANGE);
  205.     *range_key_flag|= key_tree->min_flag;
  206.     if (key_tree->next_key_part &&
  207. key_tree->next_key_part->part == key_tree->part+1 &&
  208. !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
  209. key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  210.       key_tree->next_key_part->store_min_key(key,range_key, range_key_flag);
  211.   }
  213.   void store_max_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  214.   {
  215.     SEL_ARG *key_tree= last();
  216.     key_tree->store(key[key_tree->part].part_length,
  217.     range_key, NO_MIN_RANGE, range_key,*range_key_flag);
  218.     (*range_key_flag)|= key_tree->max_flag;
  219.     if (key_tree->next_key_part &&
  220. key_tree->next_key_part->part == key_tree->part+1 &&
  221. !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
  222. key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  223.       key_tree->next_key_part->store_max_key(key,range_key, range_key_flag);
  224.   }
  226.   SEL_ARG *insert(SEL_ARG *key);
  227.   SEL_ARG *tree_delete(SEL_ARG *key);
  228.   SEL_ARG *find_range(SEL_ARG *key);
  229.   SEL_ARG *rb_insert(SEL_ARG *leaf);
  230.   friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
  231. #ifdef EXTRA_DEBUG
  232.   friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
  233.   void test_use_count(SEL_ARG *root);
  234. #endif
  235.   SEL_ARG *first();
  236.   SEL_ARG *last();
  237.   void make_root();
  238.   inline bool simple_key()
  239.   {
  240.     return !next_key_part && elements == 1;
  241.   }
  242.   void increment_use_count(long count)
  243.   {
  244.     if (next_key_part)
  245.     {
  246.       next_key_part->use_count+=count;
  247.       count*= (next_key_part->use_count-count);
  248.       for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
  249. if (pos->next_key_part)
  250.   pos->increment_use_count(count);
  251.     }
  252.   }
  253.   void free_tree()
  254.   {
  255.     for (SEL_ARG *pos=first(); pos ; pos=pos->next)
  256.       if (pos->next_key_part)
  257.       {
  258. pos->next_key_part->use_count--;
  259. pos->next_key_part->free_tree();
  260.       }
  261.   }
  263.   inline SEL_ARG **parent_ptr()
  264.   {
  265.     return parent->left == this ? &parent->left : &parent->right;
  266.   }
  267.   SEL_ARG *clone_tree();
  268. };
  271. class SEL_TREE :public Sql_alloc
  272. {
  273. public:
  274.   enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
  275.   SEL_TREE(enum Type type_arg) :type(type_arg) {}
  276.   SEL_TREE() :type(KEY) { bzero((char*) keys,sizeof(keys));}
  277.   SEL_ARG *keys[MAX_KEY];
  278. };
  281. typedef struct st_qsel_param {
  282.   uint baseflag,keys,max_key_part;
  283.   table_map prev_tables,read_tables,current_table;
  284.   TABLE *table;
  285.   bool quick; // Don't calulate possible keys
  286.   KEY_PART *key_parts,*key_parts_end,*key[MAX_KEY];
  287.   uint real_keynr[MAX_KEY];
  288.   char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
  289.     max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
  290. } PARAM;
  293. static SEL_TREE * get_mm_parts(PARAM *param,Field *field,
  294.        Item_func::Functype type,Item *value,
  295.        Item_result cmp_type);
  296. static SEL_ARG *get_mm_leaf(Field *field,KEY_PART *key_part,
  297.     Item_func::Functype type,Item *value);
  298. static bool like_range(const char *ptr,uint length,char wild_prefix,
  299.        uint field_length, char *min_str,char *max_str,
  300.        char max_sort_char,uint *min_length,uint *max_length);
  301. static SEL_TREE *get_mm_tree(PARAM *param,COND *cond);
  302. static ha_rows check_quick_select(PARAM *param,uint index,SEL_ARG *key_tree);
  303. static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
  304. char *min_key,uint min_key_flag,
  305. char *max_key, uint max_key_flag);
  307. static QUICK_SELECT *get_quick_select(PARAM *param,uint index,
  308.       SEL_ARG *key_tree);
  309. #ifndef DBUG_OFF
  310. static void print_quick(QUICK_SELECT *quick,key_map needed_reg);
  311. #endif
  312. static SEL_TREE *tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
  313. static SEL_TREE *tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
  314. static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
  315. static SEL_ARG *key_or(SEL_ARG *key1,SEL_ARG *key2);
  316. static SEL_ARG *key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag);
  317. static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
  318. static bool get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
  319.    SEL_ARG *key_tree,char *min_key,uint min_key_flag,
  320.    char *max_key,uint max_key_flag);
  321. static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
  323. static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
  326. /***************************************************************************
  327. ** Basic functions for SQL_SELECT and QUICK_SELECT
  328. ***************************************************************************/
  330. /* make a select from mysql info
  331.    Error is set as following:
  332.    0 = ok
  333.    1 = Got some error (out of memory?)
  334.    */
  336. SQL_SELECT *make_select(TABLE *head, table_map const_tables,
  337. table_map read_tables, COND *conds, int *error)
  338. {
  339.   SQL_SELECT *select;
  340.   DBUG_ENTER("make_select");
  342.   *error=0;
  343.   if (!conds)
  344.     DBUG_RETURN(0);
  345.   if (!(select= new SQL_SELECT))
  346.   {
  347.     *error= 1;
  348.     DBUG_RETURN(0); /* purecov: inspected */
  349.   }
  350.   select->read_tables=read_tables;
  351.   select->const_tables=const_tables;
  352.   select->head=head;
  353.   select->cond=conds;
  355.   if (head->io_cache)
  356.   {
  357.     select->file= *head->io_cache;
  358.     select->records=(ha_rows) (select->file.end_of_file/
  359.        head->file->ref_length);
  360.     my_free((gptr) (head->io_cache),MYF(0));
  361.     head->io_cache=0;
  362.   }
  363.   DBUG_RETURN(select);
  364. }
  367. SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
  368. {
  369.   quick_keys=0; needed_reg=0;
  370.   my_b_clear(&file);
  371. }
  374. SQL_SELECT::~SQL_SELECT()
  375. {
  376.   delete quick;
  377.   if (free_cond)
  378.     delete cond;
  379.   close_cached_file(&file);
  380. }
  382. #undef index // Fix for Unixware 7
  384. QUICK_SELECT::QUICK_SELECT(TABLE *table,uint key_nr,bool no_alloc)
  385.   :error(0),index(key_nr),max_used_key_length(0),head(table),
  386.    it(ranges),range(0)
  387. {
  388.   if (!no_alloc)
  389.   {
  390.     init_sql_alloc(&alloc,1024,0); // Allocates everything here
  391.     my_pthread_setspecific_ptr(THR_MALLOC,&alloc);
  392.   }
  393.   else
  394.     bzero((char*) &alloc,sizeof(alloc));
  395.   file=head->file;
  396.   record=head->record[0];
  397.   init();
  398. }
  400. QUICK_SELECT::~QUICK_SELECT()
  401. {
  402.   file->index_end();
  403.   free_root(&alloc,MYF(0));
  404. }
  406. int QUICK_SELECT::init()
  407. {
  408.   return error=file->index_init(index);
  409. }
  411. QUICK_RANGE::QUICK_RANGE()
  412.   :min_key(0),max_key(0),min_length(0),max_length(0),
  413.    flag(NO_MIN_RANGE | NO_MAX_RANGE)
  414. {}
  416. SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
  417. {
  418.   type=arg.type;
  419.   min_flag=arg.min_flag;
  420.   max_flag=arg.max_flag;
  421.   maybe_flag=arg.maybe_flag;
  422.   maybe_null=arg.maybe_null;
  423.   part=arg.part;
  424.   field=arg.field;
  425.   min_value=arg.min_value;
  426.   max_value=arg.max_value;
  427.   next_key_part=arg.next_key_part;
  428.   use_count=1; elements=1;
  429. }
  432. inline void SEL_ARG::make_root()
  433. {
  434.   left=right= &null_element;
  435.   color=BLACK;
  436.   next=prev=0;
  437.   use_count=0; elements=1;
  438. }
  440. SEL_ARG::SEL_ARG(Field *f,const char *min_value_arg,const char *max_value_arg)
  441.   :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
  442.    elements(1), use_count(1), field(f), min_value((char*) min_value_arg),
  443.    max_value((char*) max_value_arg), next(0),prev(0),
  444.    next_key_part(0),color(BLACK),type(KEY_RANGE)
  445. {
  446.   left=right= &null_element;
  447. }
  449. SEL_ARG::SEL_ARG(Field *field_,uint8 part_,char *min_value_,char *max_value_,
  450.  uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_)
  451.   :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
  452.    part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
  453.    field(field_), min_value(min_value_), max_value(max_value_),
  454.    next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
  455. {
  456.   left=right= &null_element;
  457. }
  459. SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg)
  460. {
  461.   SEL_ARG *tmp;
  462.   if (type != KEY_RANGE)
  463.   {
  464.     tmp=new SEL_ARG(type);
  465.     tmp->prev= *next_arg; // Link into next/prev chain
  466.     (*next_arg)->next=tmp;
  467.     (*next_arg)= tmp;
  468.   }
  469.   else
  470.   {
  471.     tmp=new SEL_ARG(field,part, min_value,max_value,
  472.     min_flag, max_flag, maybe_flag);
  473.     tmp->parent=new_parent;
  474.     tmp->next_key_part=next_key_part;
  475.     if (left != &null_element)
  476.       tmp->left=left->clone(tmp,next_arg);
  478.     tmp->prev= *next_arg; // Link into next/prev chain
  479.     (*next_arg)->next=tmp;
  480.     (*next_arg)= tmp;
  482.     if (right != &null_element)
  483.       tmp->right=right->clone(tmp,next_arg);
  484.   }
  485.   increment_use_count(1);
  486.   return tmp;
  487. }
  489. SEL_ARG *SEL_ARG::first()
  490. {
  491.   SEL_ARG *next_arg=this;
  492.   if (!next_arg->left)
  493.     return 0; // MAYBE_KEY
  494.   while (next_arg->left != &null_element)
  495.     next_arg=next_arg->left;
  496.   return next_arg;
  497. }
  499. SEL_ARG *SEL_ARG::last()
  500. {
  501.   SEL_ARG *next_arg=this;
  502.   if (!next_arg->right)
  503.     return 0; // MAYBE_KEY
  504.   while (next_arg->right != &null_element)
  505.     next_arg=next_arg->right;
  506.   return next_arg;
  507. }
  509. /*
  510.   Check if a compare is ok, when one takes ranges in account
  511.   Returns -2 or 2 if the ranges where 'joined' like  < 2 and >= 2
  512.  */
  514. static int sel_cmp(Field *field, char *a,char *b,uint8 a_flag,uint8 b_flag)
  515. {
  516.   int cmp;
  517.   /* First check if there was a compare to a min or max element */
  518.   if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
  519.   {
  520.     if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
  521. (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
  522.       return 0;
  523.     return (a_flag & NO_MIN_RANGE) ? -1 : 1;
  524.   }
  525.   if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
  526.     return (b_flag & NO_MIN_RANGE) ? 1 : -1;
  528.   if (field->real_maybe_null()) // If null is part of key
  529.   {
  530.     if (*a != *b)
  531.     {
  532.       return *a ? -1 : 1;
  533.     }
  534.     if (*a)
  535.       goto end; // NULL where equal
  536.     a++; b++; // Skipp NULL marker
  537.   }
  538.   cmp=field->key_cmp((byte*) a,(byte*) b);
  539.   if (cmp) return cmp < 0 ? -1 : 1; // The values differed
  541.   // Check if the compared equal arguments was defined with open/closed range
  542.  end:
  543.   if (a_flag & (NEAR_MIN | NEAR_MAX))
  544.   {
  545.     if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
  546.       return 0;
  547.     if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
  548.       return (a_flag & NEAR_MIN) ? 2 : -2;
  549.     return (a_flag & NEAR_MIN) ? 1 : -1;
  550.   }
  551.   if (b_flag & (NEAR_MIN | NEAR_MAX))
  552.     return (b_flag & NEAR_MIN) ? -2 : 2;
  553.   return 0; // The elements where equal
  554. }
  557. SEL_ARG *SEL_ARG::clone_tree()
  558. {
  559.   SEL_ARG tmp_link,*next_arg,*root;
  560.   next_arg= &tmp_link;
  561.   root=clone((SEL_ARG *) 0, &next_arg);
  562.   next_arg->next=0; // Fix last link
  563.   tmp_link.next->prev=0; // Fix first link
  564.   root->use_count=0;
  565.   return root;
  566. }
  568. /*****************************************************************************
  569. ** Test if a key can be used in different ranges
  570. ** Returns:
  571. ** -1 if impossible select
  572. ** 0 if can't use quick_select
  573. ** 1 if found usable range
  574. ** Updates the following in the select parameter:
  575. ** needed_reg ; Bits for keys with may be used if all prev regs are read
  576. ** quick    ; Parameter to use when reading records.
  577. ** In the table struct the following information is updated:
  578. ** quick_keys ; Which keys can be used
  579. ** quick_rows ; How many rows the key matches
  580. *****************************************************************************/
  582. int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
  583.   ha_rows limit, bool force_quick_range)
  584. {
  585.   uint basflag;
  586.   uint idx;
  587.   double scan_time;
  588.   DBUG_ENTER("test_quick_select");
  590.   delete quick;
  591.   quick=0;
  592.   needed_reg=0; quick_keys=0;
  593.   if (!cond || (specialflag & SPECIAL_SAFE_MODE) && ! force_quick_range ||
  594.       !limit)
  595.     DBUG_RETURN(0); /* purecov: inspected */
  596.   if (!((basflag= head->file->option_flag()) & HA_KEYPOS_TO_RNDPOS) &&
  597.       keys_to_use == (uint) ~0 || !keys_to_use)
  598.     DBUG_RETURN(0); /* Not smart database */
  599.   records=head->file->records;
  600.   if (!records)
  601.     records++; /* purecov: inspected */
  602.   scan_time=(double) records / TIME_FOR_COMPARE+1;
  603.   read_time=(double) head->file->scan_time()+ scan_time + 1.0;
  604.   if (limit < records)
  605.     read_time=(double) records+scan_time+1; // Force to use index
  606.   else if (read_time <= 2.0 && !force_quick_range)
  607.     DBUG_RETURN(0); /* No nead for quick select */
  609.   DBUG_PRINT("info",("Time to scan table: %ld",(long) read_time));
  611.   keys_to_use&=head->keys_in_use_for_query;
  612.   if (keys_to_use)
  613.   {
  614.     MEM_ROOT *old_root,alloc;
  615.     SEL_TREE *tree;
  616.     KEY_PART *key_parts;
  617.     PARAM param;
  619.     /* set up parameter that is passed to all functions */
  620.     param.baseflag=basflag;
  621.     param.prev_tables=prev_tables | const_tables;
  622.     param.read_tables=read_tables;
  623.     param.current_table= head->map;
  624.     param.table=head;
  625.     param.keys=0;
  627.     current_thd->no_errors=1; // Don't warn about NULL
  628.     init_sql_alloc(&alloc,2048,0);
  629.     if (!(param.key_parts = (KEY_PART*) alloc_root(&alloc,
  630.    sizeof(KEY_PART)*
  631.    head->key_parts)))
  632.     {
  633.       current_thd->no_errors=0;
  634.       free_root(&alloc,MYF(0)); // Return memory & allocator
  635.       DBUG_RETURN(0); // Can't use range
  636.     }
  637.     key_parts= param.key_parts;
  638.     old_root=my_pthread_getspecific_ptr(MEM_ROOT*,THR_MALLOC);
  639.     my_pthread_setspecific_ptr(THR_MALLOC,&alloc);
  641.     for (idx=0 ; idx < head->keys ; idx++)
  642.     {
  643.       if (!(keys_to_use & ((key_map) 1L << idx)))
  644. continue;
  645.       KEY *key_info= &head->key_info[idx];
  646.       if (key_info->flags & HA_FULLTEXT)
  647. continue;    // ToDo: ft-keys in non-ft ranges, if possible   SerG
  649.       param.key[param.keys]=key_parts;
  650.       for (uint part=0 ; part < key_info->key_parts ; part++,key_parts++)
  651.       {
  652. key_parts->key=param.keys;
  653. key_parts->part=part;
  654. key_parts->part_length= key_info->key_part[part].length;
  655. key_parts->field=    key_info->key_part[part].field;
  656. key_parts->null_bit= key_info->key_part[part].null_bit;
  657. if (key_parts->field->type() == FIELD_TYPE_BLOB)
  658.   key_parts->part_length+=HA_KEY_BLOB_LENGTH;
  659.       }
  660.       param.real_keynr[param.keys++]=idx;
  661.     }
  662.     param.key_parts_end=key_parts;
  664.     if ((tree=get_mm_tree(&param,cond)))
  665.     {
  666.       if (tree->type == SEL_TREE::IMPOSSIBLE)
  667.       {
  668. records=0L; // Return -1 from this function
  669. read_time= (double) HA_POS_ERROR;
  670.       }
  671.       else if (tree->type == SEL_TREE::KEY ||
  672.        tree->type == SEL_TREE::KEY_SMALLER)
  673.       {
  674. SEL_ARG **key,**end,**best_key=0;
  676. for (idx=0,key=tree->keys, end=key+param.keys ;
  677.      key != end ;
  678.      key++,idx++)
  679. {
  680.   ha_rows found_records;
  681.   double found_read_time;
  683.   if (*key)
  684.   {
  685.     if ((*key)->type == SEL_ARG::MAYBE_KEY ||
  686. (*key)->maybe_flag)
  687.       needed_reg|= (key_map) 1 << param.real_keynr[idx];
  689.     found_records=check_quick_select(&param,idx, *key);
  690.     if (found_records != HA_POS_ERROR && found_records > 2 &&
  691. head->used_keys & ((table_map) 1 << param.real_keynr[idx]) &&
  692. (head->file->option_flag() & HA_HAVE_KEY_READ_ONLY))
  693.     {
  694.       /*
  695.       ** We can resolve this by only reading through this key
  696.       ** Assume that we will read trough the whole key range
  697.       ** and that all key blocks are half full (normally things are
  698.       ** much better)
  699.       */
  700.       uint keys_per_block= head->file->block_size/2/head->key_info[param.real_keynr[idx]].key_length+1;
  701.       found_read_time=((double) (found_records+keys_per_block-1)/
  702.        (double) keys_per_block);
  703.     }
  704.     else
  705.       found_read_time= head->file->read_time(found_records)+
  706. (double) found_records / TIME_FOR_COMPARE;
  707.     if (read_time > found_read_time)
  708.     {
  709.       read_time=found_read_time;
  710.       records=found_records;
  711.       best_key=key;
  712.     }
  713.   }
  714. }
  715. if (best_key && records)
  716. {
  717.   if ((quick=get_quick_select(&param,(uint) (best_key-tree->keys),
  718.       *best_key)))
  719.   {
  720.     quick->records=records;
  721.     quick->read_time=read_time;
  722.   }
  723. }
  724.       }
  725.     }
  726.     free_root(&alloc,MYF(0)); // Return memory & allocator
  727.     my_pthread_setspecific_ptr(THR_MALLOC,old_root);
  728.     current_thd->no_errors=0;
  729.   }
  730.   DBUG_EXECUTE("info",print_quick(quick,needed_reg););
  731.   /*
  732.     Assume that if the user is using 'limit' we will only need to scan
  733.     limit rows if we are using a key
  734.   */
  735.   DBUG_RETURN(records ? test(quick) : -1);
  736. }
  738. /* make a select tree of all keys in condition */
  740. static SEL_TREE *get_mm_tree(PARAM *param,COND *cond)
  741. {
  742.   SEL_TREE *tree=0;
  743.   DBUG_ENTER("get_mm_tree");
  745.   if (cond->type() == Item::COND_ITEM)
  746.   {
  747.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  749.     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  750.     {
  751.       tree=0;
  752.       Item *item;
  753.       while ((item=li++))
  754.       {
  755. SEL_TREE *new_tree=get_mm_tree(param,item);
  756. tree=tree_and(param,tree,new_tree);
  757. if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
  758.   break;
  759.       }
  760.     }
  761.     else
  762.     { // COND OR
  763.       tree=get_mm_tree(param,li++);
  764.       if (tree)
  765.       {
  766. Item *item;
  767. while ((item=li++))
  768. {
  769.   SEL_TREE *new_tree=get_mm_tree(param,item);
  770.   if (!new_tree)
  771.     DBUG_RETURN(0);
  772.   tree=tree_or(param,tree,new_tree);
  773.   if (!tree || tree->type == SEL_TREE::ALWAYS)
  774.     break;
  775. }
  776.       }
  777.     }
  778.     DBUG_RETURN(tree);
  779.   }
  780.   /* Here when simple cond */
  781.   if (cond->const_item())
  782.   {
  783.     if (cond->val_int())
  784.       DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));
  785.     DBUG_RETURN(new SEL_TREE(SEL_TREE::IMPOSSIBLE));
  786.   }
  787.   table_map ref_tables=cond->used_tables();
  788.   if (ref_tables & ~(param->prev_tables | param->read_tables |
  789.      param->current_table))
  790.     DBUG_RETURN(0); // Can't be calculated yet
  791.   if (cond->type() != Item::FUNC_ITEM)
  792.   { // Should be a field
  793.     if (ref_tables & param->current_table)
  794.       DBUG_RETURN(0);
  795.     DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE));
  796.   }
  797.   if (!(ref_tables & param->current_table))
  798.     DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE)); // This may be false or true
  799.   Item_func *cond_func= (Item_func*) cond;
  800.   if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
  801.     DBUG_RETURN(0); // Can't be calculated
  803.   if (cond_func->functype() == Item_func::BETWEEN)
  804.   {
  805.     if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  806.     {
  807.       Field *field=((Item_field*) (cond_func->arguments()[0]))->field;
  808.       Item_result cmp_type=field->cmp_type();
  809.       tree= get_mm_parts(param,field,Item_func::GE_FUNC,
  810.  cond_func->arguments()[1],cmp_type);
  811.       DBUG_RETURN(tree_and(param,tree,
  812.    get_mm_parts(param, field,
  813. Item_func::LE_FUNC,
  814. cond_func->arguments()[2],cmp_type)));
  815.     }
  816.     DBUG_RETURN(0);
  817.   }
  818.   if (cond_func->functype() == Item_func::IN_FUNC)
  819.   { // COND OR
  820.     Item_func_in *func=(Item_func_in*) cond_func;
  821.     if (func->key_item()->type() == Item::FIELD_ITEM)
  822.     {
  823.       Field *field=((Item_field*) (func->key_item()))->field;
  824.       Item_result cmp_type=field->cmp_type();
  825.       tree= get_mm_parts(param,field,Item_func::EQ_FUNC,
  826.  func->arguments()[0],cmp_type);
  827.       if (!tree)
  828. DBUG_RETURN(tree); // Not key field
  829.       for (uint i=1 ; i < func->argument_count(); i++)
  830.       {
  831. SEL_TREE *new_tree=get_mm_parts(param,field,Item_func::EQ_FUNC,
  832. func->arguments()[i],cmp_type);
  833. tree=tree_or(param,tree,new_tree);
  834.       }
  835.       DBUG_RETURN(tree);
  836.     }
  837.     DBUG_RETURN(0); // Can't optimize this IN
  838.   }
  840.   /* check field op const */
  841.   /* btw, ft_func's arguments()[0] isn't FIELD_ITEM.  SerG*/
  842.   if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  843.   {
  844.     tree= get_mm_parts(param,
  845.        ((Item_field*) (cond_func->arguments()[0]))->field,
  846.        cond_func->functype(),
  847.        cond_func->arg_count > 1 ? cond_func->arguments()[1] :
  848.        0,
  849.        ((Item_field*) (cond_func->arguments()[0]))->field->
  850.        cmp_type());
  851.   }
  852.   /* check const op field */
  853.   if (!tree &&
  854.       cond_func->have_rev_func() &&
  855.       cond_func->arguments()[1]->type() == Item::FIELD_ITEM)
  856.   {
  857.     DBUG_RETURN(get_mm_parts(param,
  858.      ((Item_field*)
  859.       (cond_func->arguments()[1]))->field,
  860.      ((Item_bool_func2*) cond_func)->rev_functype(),
  861.      cond_func->arguments()[0],
  862.      ((Item_field*)
  863.       (cond_func->arguments()[1]))->field->cmp_type()
  864.      ));
  865.   }
  866.   DBUG_RETURN(tree);
  867. }
  870. static SEL_TREE *
  871. get_mm_parts(PARAM *param,Field *field, Item_func::Functype type,Item *value,
  872.      Item_result cmp_type)
  873. {
  874.   DBUG_ENTER("get_mm_parts");
  875.   if (field->table != param->table)
  876.     DBUG_RETURN(0);
  878.   KEY_PART *key_part = param->key_parts,*end=param->key_parts_end;
  879.   SEL_TREE *tree=0;
  880.   if (value &&
  881.       value->used_tables() & ~(param->prev_tables | param->read_tables))
  882.     DBUG_RETURN(0);
  883.   for ( ; key_part != end ; key_part++)
  884.   {
  885.     if (field->eq(key_part->field))
  886.     {
  887.       SEL_ARG *sel_arg=0;
  888.       if (!tree)
  889. tree=new SEL_TREE();
  890.       if (!value || !(value->used_tables() & ~param->read_tables))
  891.       {
  892. sel_arg=get_mm_leaf(key_part->field,key_part,type,value);
  893. if (!sel_arg)
  894.   continue;
  895. if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
  896. {
  897.   tree->type=SEL_TREE::IMPOSSIBLE;
  898.   DBUG_RETURN(tree);
  899. }
  900.       }
  901.       else
  902. sel_arg=new SEL_ARG(SEL_ARG::MAYBE_KEY);// This key may be used later
  903.       sel_arg->part=(uchar) key_part->part;
  904.       tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
  905.     }
  906.   }
  907.   DBUG_RETURN(tree);
  908. }
  911. static SEL_ARG *
  912. get_mm_leaf(Field *field,KEY_PART *key_part,
  913.     Item_func::Functype type,Item *value)
  914. {
  915.   uint maybe_null=(uint) field->real_maybe_null();
  916.   uint field_length=field->pack_length()+maybe_null;
  917.   SEL_ARG *tree;
  918.   DBUG_ENTER("get_mm_leaf");
  920.   if (type == Item_func::LIKE_FUNC)
  921.   {
  922.     bool like_error;
  923.     char buff1[MAX_FIELD_WIDTH],*min_str,*max_str;
  924.     String tmp(buff1,sizeof(buff1)),*res;
  925.     uint length,offset,min_length,max_length;
  927.     if (!(res= value->val_str(&tmp)))
  928.       DBUG_RETURN(&null_element);
  930.     // Check if this was a function. This should have be optimized away
  931.     // in the sql_select.cc
  932.     if (res != &tmp)
  933.     {
  934.       tmp.copy(*res); // Get own copy
  935.       res= &tmp;
  936.     }
  937.     if (field->cmp_type() != STRING_RESULT)
  938.       DBUG_RETURN(0); // Can only optimize strings
  940.     offset=maybe_null;
  941.     length=key_part->part_length;
  942.     if (field->type() == FIELD_TYPE_BLOB)
  943.     {
  944.       offset+=HA_KEY_BLOB_LENGTH;
  945.       field_length=key_part->part_length-HA_KEY_BLOB_LENGTH;
  946.     }
  947.     else
  948.     {
  949.       if (length < field_length)
  950. length=field_length; // Only if overlapping key
  951.       else
  952. field_length=length;
  953.     }
  954.     length+=offset;
  955.     if (!(min_str= (char*) sql_alloc(length*2)))
  956.       DBUG_RETURN(0);
  957.     max_str=min_str+length;
  958.     if (maybe_null)
  959.       max_str[0]= min_str[0]=0;
  960.     if (field->binary())
  961.       like_error=like_range(res->ptr(),res->length(),wild_prefix,field_length,
  962.     min_str+offset,max_str+offset,(char) 255,
  963.     &min_length,&max_length);
  964.     else
  965.     {
  966. #ifdef USE_STRCOLL
  967.       if (use_strcoll(default_charset_info))
  968.         like_error= my_like_range(default_charset_info,
  969.                                   res->ptr(),res->length(),wild_prefix,
  970.                                   field_length, min_str+maybe_null,
  971.                                   max_str+maybe_null,&min_length,&max_length);
  972.       else
  973. #endif
  974.         like_error=like_range(res->ptr(),res->length(),wild_prefix,field_length,
  975.                               min_str+offset,max_str+offset,
  976.                               max_sort_char,&min_length,&max_length);
  977.     }
  978.     if (like_error) // Can't optimize with LIKE
  979.       DBUG_RETURN(0);
  980.     if (offset != maybe_null) // Blob
  981.     {
  982.       int2store(min_str+maybe_null,min_length);
  983.       int2store(max_str+maybe_null,max_length);
  984.     }
  985.     DBUG_RETURN(new SEL_ARG(field,min_str,max_str));
  986.   }
  988.   if (!value) // IS NULL or IS NOT NULL
  989.   {
  990.     if (field->table->outer_join) // Can't use a key on this
  991.       DBUG_RETURN(0);
  992.     if (!maybe_null) // Not null field
  993.       DBUG_RETURN(type == Item_func::ISNULL_FUNC ? &null_element : 0);
  994.     tree=new SEL_ARG(field,is_null_string,is_null_string);
  995.     if (!tree)
  996.       DBUG_RETURN(0);
  997.     if (type == Item_func::ISNOTNULL_FUNC)
  998.     {
  999.       tree->min_flag=NEAR_MIN;     /* IS NOT NULL ->  X > NULL */
  1000.       tree->max_flag=NO_MAX_RANGE;
  1001.     }
  1002.     DBUG_RETURN(tree);
  1003.   }
  1005.   if (!field->optimize_range() && type != Item_func::EQ_FUNC &&
  1006.       type != Item_func::EQUAL_FUNC)
  1007.     DBUG_RETURN(0); // Can't optimize this
  1009.   /* We can't always use indexes when comparing a string index to a number */
  1010.   /* cmp_type() is checked to allow compare of dates to numbers */
  1011.   if (field->result_type() == STRING_RESULT &&
  1012.       value->result_type() != STRING_RESULT &&
  1013.       field->cmp_type() != value->result_type())
  1014.     DBUG_RETURN(0);
  1016.   if (value->save_in_field(field))
  1017.   {
  1018.     if (type == Item_func::EQUAL_FUNC)
  1019.     {
  1020.       /* convert column_name <=> NULL -> column_name IS NULL */
  1021.       char *str= (char*) sql_alloc(1); // Get local copy of key
  1022.       if (!*str)
  1023. DBUG_RETURN(0);
  1024.       *str = 1;
  1025.       DBUG_RETURN(new SEL_ARG(field,str,str));
  1026.     }
  1027.     DBUG_RETURN(&null_element); // NULL is never true
  1028.   }
  1029.   // Get local copy of key
  1030.   char *str= (char*) sql_alloc(key_part->part_length+maybe_null);
  1031.   if (!str)
  1032.     DBUG_RETURN(0);
  1033.   if (maybe_null)
  1034.     *str=0; // Not NULL
  1035.   field->get_key_image(str+maybe_null,key_part->part_length);
  1036.   if (!(tree=new SEL_ARG(field,str,str)))
  1037.     DBUG_RETURN(0);
  1039.   switch (type) {
  1040.   case Item_func::LT_FUNC:
  1041.     if (field_is_equal_to_item(field,value))
  1042.       tree->max_flag=NEAR_MAX;
  1043.     /* fall through */
  1044.   case Item_func::LE_FUNC:
  1045.     if (!maybe_null)
  1046.       tree->min_flag=NO_MIN_RANGE; /* From start */
  1047.     else
  1048.     { // > NULL
  1049.       tree->min_value=is_null_string;
  1050.       tree->min_flag=NEAR_MIN;
  1051.     }
  1052.     break;
  1053.   case Item_func::GT_FUNC:
  1054.     if (field_is_equal_to_item(field,value))
  1055.       tree->min_flag=NEAR_MIN;
  1056.     /* fall through */
  1057.   case Item_func::GE_FUNC:
  1058.     tree->max_flag=NO_MAX_RANGE;
  1059.     break;
  1060.   default:
  1061.     break;
  1062.   }
  1063.   DBUG_RETURN(tree);
  1064. }
  1067. /*
  1068. ** Calculate min_str and max_str that ranges a LIKE string.
  1069. ** Arguments:
  1070. ** ptr Pointer to LIKE string.
  1071. ** ptr_length Length of LIKE string.
  1072. ** escape Escape character in LIKE.  (Normally '').
  1073. ** All escape characters should be removed from min_str and max_str
  1074. ** res_length Length of min_str and max_str.
  1075. ** min_str Smallest case sensitive string that ranges LIKE.
  1076. ** Should be space padded to res_length.
  1077. ** max_str Largest case sensitive string that ranges LIKE.
  1078. ** Normally padded with the biggest character sort value.
  1079. **
  1080. ** The function should return 0 if ok and 1 if the LIKE string can't be
  1081. ** optimized !
  1082. */
  1084. static bool like_range(const char *ptr,uint ptr_length,char escape,
  1085.        uint res_length, char *min_str,char *max_str,
  1086.        char max_sort_chr, uint *min_length, uint *max_length)
  1087. {
  1088.   const char *end=ptr+ptr_length;
  1089.   char *min_org=min_str;
  1090.   char *min_end=min_str+res_length;
  1092.   for (; ptr != end && min_str != min_end ; ptr++)
  1093.   {
  1094.     if (*ptr == escape && ptr+1 != end)
  1095.     {
  1096.       ptr++; // Skipp escape
  1097.       *min_str++= *max_str++ = *ptr;
  1098.       continue;
  1099.     }
  1100.     if (*ptr == wild_one) // '_' in SQL
  1101.     {
  1102.       *min_str++=''; // This should be min char
  1103.       *max_str++=max_sort_chr;
  1104.       continue;
  1105.     }
  1106.     if (*ptr == wild_many) // '%' in SQL
  1107.     {
  1108.       *min_length= (uint) (min_str - min_org);
  1109.       *max_length=res_length;
  1110.       do {
  1111. *min_str++ = ' '; // Because if key compression
  1112. *max_str++ = max_sort_chr;
  1113.       } while (min_str != min_end);
  1114.       return 0;
  1115.     }
  1116.     *min_str++= *max_str++ = *ptr;
  1117.   }
  1118.   *min_length= *max_length = (uint) (min_str - min_org);
  1120.   /* Temporary fix for handling wild_one at end of string (key compression) */
  1121.   for (char *tmp= min_str ; tmp > min_org && tmp[-1] == '';)
  1122.     *--tmp=' ';
  1124.   while (min_str != min_end)
  1125.     *min_str++ = *max_str++ = ' '; // Because if key compression
  1126.   return 0;
  1127. }
  1130. /******************************************************************************
  1131. ** Tree manipulation functions
  1132. ** If tree is 0 it means that the condition can't be tested. It refers
  1133. ** to a non existent table or to a field in current table with isn't a key.
  1134. ** The different tree flags:
  1135. ** IMPOSSIBLE:  Condition is never true
  1136. ** ALWAYS:  Condition is always true
  1137. ** MAYBE:  Condition may exists when tables are read
  1138. ** MAYBE_KEY:  Condition refers to a key that may be used in join loop
  1139. ** KEY_RANGE:  Condition uses a key
  1140. ******************************************************************************/
  1142. /*
  1143. ** Add a new key test to a key when scanning through all keys
  1144. ** This will never be called for same key parts.
  1145. */
  1147. static SEL_ARG *
  1148. sel_add(SEL_ARG *key1,SEL_ARG *key2)
  1149. {
  1150.   SEL_ARG *root,**key_link;
  1152.   if (!key1)
  1153.     return key2;
  1154.   if (!key2)
  1155.     return key1;
  1157.   key_link= &root;
  1158.   while (key1 && key2)
  1159.   {
  1160.     if (key1->part < key2->part)
  1161.     {
  1162.       *key_link= key1;
  1163.       key_link= &key1->next_key_part;
  1164.       key1=key1->next_key_part;
  1165.     }
  1166.     else
  1167.     {
  1168.       *key_link= key2;
  1169.       key_link= &key2->next_key_part;
  1170.       key2=key2->next_key_part;
  1171.     }
  1172.   }
  1173.   *key_link=key1 ? key1 : key2;
  1174.   return root;
  1175. }
  1177. #define CLONE_KEY1_MAYBE 1
  1178. #define CLONE_KEY2_MAYBE 2
  1179. #define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
  1182. static SEL_TREE *
  1183. tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
  1184. {
  1185.   DBUG_ENTER("tree_and");
  1186.   if (!tree1)
  1187.     DBUG_RETURN(tree2);
  1188.   if (!tree2)
  1189.     DBUG_RETURN(tree1);
  1190.   if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
  1191.     DBUG_RETURN(tree1);
  1192.   if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
  1193.     DBUG_RETURN(tree2);
  1194.   if (tree1->type == SEL_TREE::MAYBE)
  1195.   {
  1196.     if (tree2->type == SEL_TREE::KEY)
  1197.       tree2->type=SEL_TREE::KEY_SMALLER;
  1198.     DBUG_RETURN(tree2);
  1199.   }
  1200.   if (tree2->type == SEL_TREE::MAYBE)
  1201.   {
  1202.     tree1->type=SEL_TREE::KEY_SMALLER;
  1203.     DBUG_RETURN(tree1);
  1204.   }
  1206.   /* Join the trees key per key */
  1207.   SEL_ARG **key1,**key2,**end;
  1208.   for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
  1209.        key1 != end ; key1++,key2++)
  1210.   {
  1211.     uint flag=0;
  1212.     if (*key1 || *key2)
  1213.     {
  1214.       if (*key1 && !(*key1)->simple_key())
  1215. flag|=CLONE_KEY1_MAYBE;
  1216.       if (*key2 && !(*key2)->simple_key())
  1217. flag|=CLONE_KEY2_MAYBE;
  1218.       *key1=key_and(*key1,*key2,flag);
  1219.       if ((*key1)->type == SEL_ARG::IMPOSSIBLE)
  1220.       {
  1221. tree1->type= SEL_TREE::IMPOSSIBLE;
  1222. break;
  1223.       }
  1224. #ifdef EXTRA_DEBUG
  1225.       (*key1)->test_use_count(*key1);
  1226. #endif
  1227.     }
  1228.   }
  1229.   DBUG_RETURN(tree1);
  1230. }
  1234. static SEL_TREE *
  1235. tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
  1236. {
  1237.   DBUG_ENTER("tree_or");
  1238.   if (!tree1 || !tree2)
  1239.     DBUG_RETURN(0);
  1240.   if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
  1241.     DBUG_RETURN(tree2);
  1242.   if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
  1243.     DBUG_RETURN(tree1);
  1244.   if (tree1->type == SEL_TREE::MAYBE)
  1245.     DBUG_RETURN(tree1); // Can't use this
  1246.   if (tree2->type == SEL_TREE::MAYBE)
  1247.     DBUG_RETURN(tree2);
  1249.   /* Join the trees key per key */
  1250.   SEL_ARG **key1,**key2,**end;
  1251.   SEL_TREE *result=0;
  1252.   for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
  1253.        key1 != end ; key1++,key2++)
  1254.   {
  1255.     *key1=key_or(*key1,*key2);
  1256.     if (*key1)
  1257.     {
  1258.       result=tree1; // Added to tree1
  1259. #ifdef EXTRA_DEBUG
  1260.       (*key1)->test_use_count(*key1);
  1261. #endif
  1262.     }
  1263.   }
  1264.   DBUG_RETURN(result);
  1265. }
  1268. /* And key trees where key1->part < key2 -> part */
  1270. static SEL_ARG *
  1271. and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
  1272. {
  1273.   SEL_ARG *next;
  1274.   ulong use_count=key1->use_count;
  1276.   if (key1->elements != 1)
  1277.   {
  1278.     key2->use_count+=key1->elements-1;
  1279.     key2->increment_use_count((int) key1->elements-1);
  1280.   }
  1281.   if (key1->type == SEL_ARG::MAYBE_KEY)
  1282.   {
  1283.     key1->left= &null_element; key1->next=0;
  1284.   }
  1285.   for (next=key1->first(); next ; next=next->next)
  1286.   {
  1287.     if (next->next_key_part)
  1288.     {
  1289.       SEL_ARG *tmp=key_and(next->next_key_part,key2,clone_flag);
  1290.       if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE)
  1291.       {
  1292. key1=key1->tree_delete(next);
  1293. continue;
  1294.       }
  1295.       next->next_key_part=tmp;
  1296.       if (use_count)
  1297. next->increment_use_count(use_count);
  1298.     }
  1299.     else
  1300.       next->next_key_part=key2;
  1301.   }
  1302.   if (!key1)
  1303.     return &null_element; // Impossible ranges
  1304.   key1->use_count++;
  1305.   return key1;
  1306. }
  1310. static SEL_ARG *
  1311. key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
  1312. {
  1313.   if (!key1)
  1314.     return key2;
  1315.   if (!key2)
  1316.     return key1;
  1317.   if (key1->part != key2->part)
  1318.   {
  1319.     if (key1->part > key2->part)
  1320.     {
  1321.       swap(SEL_ARG *,key1,key2);
  1322.       clone_flag=swap_clone_flag(clone_flag);
  1323.     }
  1324.     // key1->part < key2->part
  1325.     key1->use_count--;
  1326.     if (key1->use_count > 0)
  1327.       key1=key1->clone_tree();
  1328.     return and_all_keys(key1,key2,clone_flag);
  1329.   }
  1331.   if (((clone_flag & CLONE_KEY2_MAYBE) &&
  1332.        !(clone_flag & CLONE_KEY1_MAYBE)) ||
  1333.       key1->type == SEL_ARG::MAYBE_KEY)
  1334.   { // Put simple key in key2
  1335.     swap(SEL_ARG *,key1,key2);
  1336.     clone_flag=swap_clone_flag(clone_flag);
  1337.   }
  1339.   // If one of the key is MAYBE_KEY then the found region may be smaller
  1340.   if (key2->type == SEL_ARG::MAYBE_KEY)
  1341.   {
  1342.     if (key1->use_count > 1)
  1343.     {
  1344.       key1->use_count--;
  1345.       key1=key1->clone_tree();
  1346.       key1->use_count++;
  1347.     }
  1348.     if (key1->type == SEL_ARG::MAYBE_KEY)
  1349.     { // Both are maybe key
  1350.       key1->next_key_part=key_and(key1->next_key_part,key2->next_key_part,
  1351.  clone_flag);
  1352.       if (key1->next_key_part &&
  1353.   key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
  1354. return key1;
  1355.     }
  1356.     else
  1357.     {
  1358.       key1->maybe_smaller();
  1359.       if (key2->next_key_part)
  1360. return and_all_keys(key1,key2,clone_flag);
  1361.       key2->use_count--; // Key2 doesn't have a tree
  1362.     }
  1363.     return key1;
  1364.   }
  1366.   key1->use_count--;
  1367.   key2->use_count--;
  1368.   SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;
  1370.   while (e1 && e2)
  1371.   {
  1372.     int cmp=e1->cmp_min_to_min(e2);
  1373.     if (cmp < 0)
  1374.     {
  1375.       if (get_range(&e1,&e2,key1))
  1376. continue;
  1377.     }
  1378.     else if (get_range(&e2,&e1,key2))
  1379.       continue;
  1380.     SEL_ARG *next=key_and(e1->next_key_part,e2->next_key_part,clone_flag);
  1381.     e1->increment_use_count(1);
  1382.     e2->increment_use_count(1);
  1383.     if (!next || next->type != SEL_ARG::IMPOSSIBLE)
  1384.     {
  1385.       SEL_ARG *new_arg= e1->clone_and(e2);
  1386.       new_arg->next_key_part=next;
  1387.       if (!new_tree)
  1388.       {
  1389. new_tree=new_arg;
  1390.       }
  1391.       else
  1392. new_tree=new_tree->insert(new_arg);
  1393.     }
  1394.     if (e1->cmp_max_to_max(e2) < 0)
  1395.       e1=e1->next; // e1 can't overlapp next e2
  1396.     else
  1397.       e2=e2->next;
  1398.   }
  1399.   key1->free_tree();
  1400.   key2->free_tree();
  1401.   if (!new_tree)
  1402.     return &null_element; // Impossible range
  1403.   return new_tree;
  1404. }
  1407. static bool
  1408. get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1)
  1409. {
  1410.   (*e1)=root1->find_range(*e2); // first e1->min < e2->min
  1411.   if ((*e1)->cmp_max_to_min(*e2) < 0)
  1412.   {
  1413.     if (!((*e1)=(*e1)->next))
  1414.       return 1;
  1415.     if ((*e1)->cmp_min_to_max(*e2) > 0)
  1416.     {
  1417.       (*e2)=(*e2)->next;
  1418.       return 1;
  1419.     }
  1420.   }
  1421.   return 0;
  1422. }
  1425. static SEL_ARG *
  1426. key_or(SEL_ARG *key1,SEL_ARG *key2)
  1427. {
  1428.   if (!key1)
  1429.   {
  1430.     if (key2)
  1431.     {
  1432.       key2->use_count--;
  1433.       key2->free_tree();
  1434.     }
  1435.     return 0;
  1436.   }
  1437.   else if (!key2)
  1438.   {
  1439.     key1->use_count--;
  1440.     key1->free_tree();
  1441.     return 0;
  1442.   }
  1443.   key1->use_count--;
  1444.   key2->use_count--;
  1446.   if (key1->part != key2->part)
  1447.   {
  1448.     key1->free_tree();
  1449.     key2->free_tree();
  1450.     return 0; // Can't optimize this
  1451.   }
  1453.   // If one of the key is MAYBE_KEY then the found region may be bigger
  1454.   if (key1->type == SEL_ARG::MAYBE_KEY)
  1455.   {
  1456.     key2->free_tree();
  1457.     key1->use_count++;
  1458.     return key1;
  1459.   }
  1460.   if (key2->type == SEL_ARG::MAYBE_KEY)
  1461.   {
  1462.     key1->free_tree();
  1463.     key2->use_count++;
  1464.     return key2;
  1465.   }
  1467.   if (key1->use_count > 0)
  1468.   {
  1469.     if (key2->use_count == 0 || key1->elements > key2->elements)
  1470.     {
  1471.       swap(SEL_ARG *,key1,key2);
  1472.     }
  1473.     else
  1474.       key1=key1->clone_tree();
  1475.   }
  1477.   // Add tree at key2 to tree at key1
  1478.   bool key2_shared=key2->use_count != 0;
  1479.   key1->maybe_flag|=key2->maybe_flag;
  1481.   for (key2=key2->first(); key2; )
  1482.   {
  1483.     SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
  1484.     int cmp;
  1486.     if (!tmp)
  1487.     {
  1488.       tmp=key1->first(); // tmp.min > key2.min
  1489.       cmp= -1;
  1490.     }
  1491.     else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
  1492.     { // Found tmp.max < key2.min
  1493.       SEL_ARG *next=tmp->next;
  1494.       if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
  1495.       {
  1496. // Join near ranges like tmp.max < 0 and key2.min >= 0
  1497. SEL_ARG *key2_next=key2->next;
  1498. if (key2_shared)
  1499. {
  1500.   key2=new SEL_ARG(*key2);
  1501.   key2->increment_use_count(key1->use_count+1);
  1502.   key2->next=key2_next; // New copy of key2
  1503. }
  1504. key2->copy_min(tmp);
  1505. if (!(key1=key1->tree_delete(tmp)))
  1506. { // Only one key in tree
  1507.   key1=key2;
  1508.   key1->make_root();
  1509.   key2=key2_next;
  1510.   break;
  1511. }
  1512.       }
  1513.       if (!(tmp=next)) // tmp.min > key2.min
  1514. break; // Copy rest of key2
  1515.     }
  1516.     if (cmp < 0)
  1517.     { // tmp.min > key2.min
  1518.       int tmp_cmp;
  1519.       if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
  1520.       {
  1521. if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
  1522. { // ranges are connected
  1523.   tmp->copy_min_to_min(key2);
  1524.   key1->merge_flags(key2);
  1525.   if (tmp->min_flag & NO_MIN_RANGE &&
  1526.       tmp->max_flag & NO_MAX_RANGE)
  1527.   {
  1528.     if (key1->maybe_flag)
  1529.       return new SEL_ARG(SEL_ARG::MAYBE_KEY);
  1530.     return 0;
  1531.   }
  1532.   key2->increment_use_count(-1); // Free not used tree
  1533.   key2=key2->next;
  1534.   continue;
  1535. }
  1536. else
  1537. {
  1538.   SEL_ARG *next=key2->next; // Keys are not overlapping
  1539.   if (key2_shared)
  1540.   {
  1541.     key1=key1->insert(new SEL_ARG(*key2)); // Must make copy
  1542.     key2->increment_use_count(key1->use_count+1);
  1543.   }
  1544.   else
  1545.     key1=key1->insert(key2); // Will destroy key2_root
  1546.   key2=next;
  1547.   continue;
  1548. }
  1549.       }
  1550.     }
  1552.     // tmp.max >= key2.min && tmp.min <= key.max  (overlapping ranges)
  1553.     if (eq_tree(tmp->next_key_part,key2->next_key_part))
  1554.     {
  1555.       if (tmp->is_same(key2))
  1556.       {
  1557. tmp->merge_flags(key2); // Copy maybe flags
  1558. key2->increment_use_count(-1); // Free not used tree
  1559.       }
  1560.       else
  1561.       {
  1562. SEL_ARG *last=tmp;
  1563. while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
  1564.        eq_tree(last->next->next_key_part,key2->next_key_part))
  1565. {
  1566.   SEL_ARG *save=last;
  1567.   last=last->next;
  1568.   key1=key1->tree_delete(save);
  1569. }
  1570. if (last->copy_min(key2) || last->copy_max(key2))
  1571. { // Full range
  1572.   key1->free_tree();
  1573.   for (; key2 ; key2=key2->next)
  1574.     key2->increment_use_count(-1); // Free not used tree
  1575.   if (key1->maybe_flag)
  1576.     return new SEL_ARG(SEL_ARG::MAYBE_KEY);
  1577.   return 0;
  1578. }
  1579.       }
  1580.       key2=key2->next;
  1581.       continue;
  1582.     }
  1584.     if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
  1585.     { // tmp.min <= x < key2.min
  1586.       SEL_ARG *new_arg=tmp->clone_first(key2);
  1587.       if ((new_arg->next_key_part= key1->next_key_part))
  1588. new_arg->increment_use_count(key1->use_count+1);
  1589.       tmp->copy_min_to_min(key2);
  1590.       key1=key1->insert(new_arg);
  1591.     }
  1593.     // tmp.min >= key2.min && tmp.min <= key2.max
  1594.     SEL_ARG key(*key2); // Get copy we can modify
  1595.     for (;;)
  1596.     {
  1597.       if (tmp->cmp_min_to_min(&key) > 0)
  1598.       { // key.min <= x < tmp.min
  1599. SEL_ARG *new_arg=key.clone_first(tmp);
  1600. if ((new_arg->next_key_part=key.next_key_part))
  1601.   new_arg->increment_use_count(key1->use_count+1);
  1602. key1=key1->insert(new_arg);
  1603.       }
  1604.       if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
  1605.       { // tmp.min. <= x <= tmp.max
  1606. tmp->maybe_flag|= key.maybe_flag;
  1607. key.increment_use_count(key1->use_count+1);
  1608. tmp->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
  1609. if (!cmp) // Key2 is ready
  1610.   break;
  1611. key.copy_max_to_min(tmp);
  1612. if (!(tmp=tmp->next))
  1613. {
  1614.   key1=key1->insert(new SEL_ARG(key));
  1615.   key2=key2->next;
  1616.   goto end;
  1617. }
  1618. if (tmp->cmp_min_to_max(&key) > 0)
  1619. {
  1620.   key1=key1->insert(new SEL_ARG(key));
  1621.   break;
  1622. }
  1623.       }
  1624.       else
  1625.       {
  1626. SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
  1627. tmp->copy_max_to_min(&key);
  1628. tmp->increment_use_count(key1->use_count+1);
  1629. new_arg->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
  1630. key1=key1->insert(new_arg);
  1631. break;
  1632.       }
  1633.     }
  1634.     key2=key2->next;
  1635.   }
  1637. end:
  1638.   while (key2)
  1639.   {
  1640.     SEL_ARG *next=key2->next;
  1641.     if (key2_shared)
  1642.     {
  1643.       key2->increment_use_count(key1->use_count+1);
  1644.       key1=key1->insert(new SEL_ARG(*key2)); // Must make copy
  1645.     }
  1646.     else
  1647.       key1=key1->insert(key2); // Will destroy key2_root
  1648.     key2=next;
  1649.   }
  1650.   key1->use_count++;
  1651.   return key1;
  1652. }
  1655. /* Compare if two trees are equal */
  1657. static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
  1658. {
  1659.   if (a == b)
  1660.     return 1;
  1661.   if (!a || !b || !a->is_same(b))
  1662.     return 0;
  1663.   if (a->left != &null_element && b->left != &null_element)
  1664.   {
  1665.     if (!eq_tree(a->left,b->left))
  1666.       return 0;
  1667.   }
  1668.   else if (a->left != &null_element || b->left != &null_element)
  1669.     return 0;
  1670.   if (a->right != &null_element && b->right != &null_element)
  1671.   {
  1672.     if (!eq_tree(a->right,b->right))
  1673.       return 0;
  1674.   }
  1675.   else if (a->right != &null_element || b->right != &null_element)
  1676.     return 0;
  1677.   if (a->next_key_part != b->next_key_part)
  1678.   { // Sub range
  1679.     if (!a->next_key_part != !b->next_key_part ||
  1680. !eq_tree(a->next_key_part, b->next_key_part))
  1681.       return 0;
  1682.   }
  1683.   return 1;
  1684. }
  1687. SEL_ARG *
  1688. SEL_ARG::insert(SEL_ARG *key)
  1689. {
  1690.   SEL_ARG *element,**par,*last_element;
  1692.   LINT_INIT(par); LINT_INIT(last_element);
  1693.   for (element= this; element != &null_element ; )
  1694.   {
  1695.     last_element=element;
  1696.     if (key->cmp_min_to_min(element) > 0)
  1697.     {
  1698.       par= &element->right; element= element->right;
  1699.     }
  1700.     else
  1701.     {
  1702.       par = &element->left; element= element->left;
  1703.     }
  1704.   }
  1705.   *par=key;
  1706.   key->parent=last_element;
  1707. /* Link in list */
  1708.   if (par == &last_element->left)
  1709.   {
  1710.     key->next=last_element;
  1711.     if ((key->prev=last_element->prev))
  1712.       key->prev->next=key;
  1713.     last_element->prev=key;
  1714.   }
  1715.   else
  1716.   {
  1717.     if ((key->next=last_element->next))
  1718.       key->next->prev=key;
  1719.     key->prev=last_element;
  1720.     last_element->next=key;
  1721.   }
  1722.   key->left=key->right= &null_element;
  1723.   SEL_ARG *root=rb_insert(key); // rebalance tree
  1724.   root->use_count=this->use_count; // copy root info
  1725.   root->elements= this->elements+1;
  1726.   root->maybe_flag=this->maybe_flag;
  1727.   return root;
  1728. }
  1731. /*
  1732. ** Find best key with min <= given key
  1733. ** Because the call context this should never return 0 to get_range
  1734. */
  1736. SEL_ARG *
  1737. SEL_ARG::find_range(SEL_ARG *key)
  1738. {
  1739.   SEL_ARG *element=this,*found=0;
  1741.   for (;;)
  1742.   {
  1743.     if (element == &null_element)
  1744.       return found;
  1745.     int cmp=element->cmp_min_to_min(key);
  1746.     if (cmp == 0)
  1747.       return element;
  1748.     if (cmp < 0)
  1749.     {
  1750.       found=element;
  1751.       element=element->right;
  1752.     }
  1753.     else
  1754.       element=element->left;
  1755.   }
  1756. }
  1759. /*
  1760. ** Remove a element from the tree
  1761. ** This also frees all sub trees that is used by the element
  1762. */
  1764. SEL_ARG *
  1765. SEL_ARG::tree_delete(SEL_ARG *key)
  1766. {
  1767.   enum leaf_color remove_color;
  1768.   SEL_ARG *root,*nod,**par,*fix_par;
  1769.   root=this; this->parent= 0;
  1771.   /* Unlink from list */
  1772.   if (key->prev)
  1773.     key->prev->next=key->next;
  1774.   if (key->next)
  1775.     key->next->prev=key->prev;
  1776.   key->increment_use_count(-1);
  1777.   if (!key->parent)
  1778.     par= &root;
  1779.   else
  1780.     par=key->parent_ptr();
  1782.   if (key->left == &null_element)
  1783.   {
  1784.     *par=nod=key->right;
  1785.     fix_par=key->parent;
  1786.     if (nod != &null_element)
  1787.       nod->parent=fix_par;
  1788.     remove_color= key->color;
  1789.   }
  1790.   else if (key->right == &null_element)
  1791.   {
  1792.     *par= nod=key->left;
  1793.     nod->parent=fix_par=key->parent;
  1794.     remove_color= key->color;
  1795.   }
  1796.   else
  1797.   {
  1798.     SEL_ARG *tmp=key->next; // next bigger key (exist!)
  1799.     nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
  1800.     fix_par=tmp->parent;
  1801.     if (nod != &null_element)
  1802.       nod->parent=fix_par;
  1803.     remove_color= tmp->color;
  1805.     tmp->parent=key->parent; // Move node in place of key
  1806.     (tmp->left=key->left)->parent=tmp;
  1807.     if ((tmp->right=key->right) != &null_element)
  1808.       tmp->right->parent=tmp;
  1809.     tmp->color=key->color;
  1810.     *par=tmp;
  1811.     if (fix_par == key) // key->right == key->next
  1812.       fix_par=tmp; // new parent of nod
  1813.   }
  1815.   if (root == &null_element)
  1816.     return 0; // Maybe root later
  1817.   if (remove_color == BLACK)
  1818.     root=rb_delete_fixup(root,nod,fix_par);
  1819.   test_rb_tree(root,root->parent);
  1821.   root->use_count=this->use_count; // Fix root counters
  1822.   root->elements=this->elements-1;
  1823.   root->maybe_flag=this->maybe_flag;
  1824.   return root;
  1825. }
  1828. /* Functions to fix up the tree after insert and delete */
  1830. static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
  1831. {
  1832.   SEL_ARG *y=leaf->right;
  1833.   leaf->right=y->left;
  1834.   if (y->left != &null_element)
  1835.     y->left->parent=leaf;
  1836.   if (!(y->parent=leaf->parent))
  1837.     *root=y;
  1838.   else
  1839.     *leaf->parent_ptr()=y;
  1840.   y->left=leaf;
  1841.   leaf->parent=y;
  1842. }
  1844. static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
  1845. {
  1846.   SEL_ARG *y=leaf->left;
  1847.   leaf->left=y->right;
  1848.   if (y->right != &null_element)
  1849.     y->right->parent=leaf;
  1850.   if (!(y->parent=leaf->parent))
  1851.     *root=y;
  1852.   else
  1853.     *leaf->parent_ptr()=y;
  1854.   y->right=leaf;
  1855.   leaf->parent=y;
  1856. }
  1859. SEL_ARG *
  1860. SEL_ARG::rb_insert(SEL_ARG *leaf)
  1861. {
  1862.   SEL_ARG *y,*par,*par2,*root;
  1863.   root= this; root->parent= 0;
  1865.   leaf->color=RED;
  1866.   while (leaf != root && (par= leaf->parent)->color == RED)
  1867.   { // This can't be root or 1 level under
  1868.     if (par == (par2= leaf->parent->parent)->left)
  1869.     {
  1870.       y= par2->right;
  1871.       if (y->color == RED)
  1872.       {
  1873. par->color=BLACK;
  1874. y->color=BLACK;
  1875. leaf=par2;
  1876. leaf->color=RED; /* And the loop continues */
  1877.       }
  1878.       else
  1879.       {
  1880. if (leaf == par->right)
  1881. {
  1882.   left_rotate(&root,leaf->parent);
  1883.   par=leaf; /* leaf is now parent to old leaf */
  1884. }
  1885. par->color=BLACK;
  1886. par2->color=RED;
  1887. right_rotate(&root,par2);
  1888. break;
  1889.       }
  1890.     }
  1891.     else
  1892.     {
  1893.       y= par2->left;
  1894.       if (y->color == RED)
  1895.       {
  1896. par->color=BLACK;
  1897. y->color=BLACK;
  1898. leaf=par2;
  1899. leaf->color=RED; /* And the loop continues */
  1900.       }
  1901.       else
  1902.       {
  1903. if (leaf == par->left)
  1904. {
  1905.   right_rotate(&root,par);
  1906.   par=leaf;
  1907. }
  1908. par->color=BLACK;
  1909. par2->color=RED;
  1910. left_rotate(&root,par2);
  1911. break;
  1912.       }
  1913.     }
  1914.   }
  1915.   root->color=BLACK;
  1916.   test_rb_tree(root,root->parent);
  1917.   return root;
  1918. }
  1921. SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
  1922. {
  1923.   SEL_ARG *x,*w;
  1924.   root->parent=0;
  1926.   x= key;
  1927.   while (x != root && x->color == SEL_ARG::BLACK)
  1928.   {
  1929.     if (x == par->left)
  1930.     {
  1931.       w=par->right;
  1932.       if (w->color == SEL_ARG::RED)
  1933.       {
  1934. w->color=SEL_ARG::BLACK;
  1935. par->color=SEL_ARG::RED;
  1936. left_rotate(&root,par);
  1937. w=par->right;
  1938.       }
  1939.       if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
  1940.       {
  1941. w->color=SEL_ARG::RED;
  1942. x=par;
  1943.       }
  1944.       else
  1945.       {
  1946. if (w->right->color == SEL_ARG::BLACK)
  1947. {
  1948.   w->left->color=SEL_ARG::BLACK;
  1949.   w->color=SEL_ARG::RED;
  1950.   right_rotate(&root,w);
  1951.   w=par->right;
  1952. }
  1953. w->color=par->color;
  1954. par->color=SEL_ARG::BLACK;
  1955. w->right->color=SEL_ARG::BLACK;
  1956. left_rotate(&root,par);
  1957. x=root;
  1958. break;
  1959.       }
  1960.     }
  1961.     else
  1962.     {
  1963.       w=par->left;
  1964.       if (w->color == SEL_ARG::RED)
  1965.       {
  1966. w->color=SEL_ARG::BLACK;
  1967. par->color=SEL_ARG::RED;
  1968. right_rotate(&root,par);
  1969. w=par->left;
  1970.       }
  1971.       if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
  1972.       {
  1973. w->color=SEL_ARG::RED;
  1974. x=par;
  1975.       }
  1976.       else
  1977.       {
  1978. if (w->left->color == SEL_ARG::BLACK)
  1979. {
  1980.   w->right->color=SEL_ARG::BLACK;
  1981.   w->color=SEL_ARG::RED;
  1982.   left_rotate(&root,w);
  1983.   w=par->left;
  1984. }
  1985. w->color=par->color;
  1986. par->color=SEL_ARG::BLACK;
  1987. w->left->color=SEL_ARG::BLACK;
  1988. right_rotate(&root,par);
  1989. x=root;
  1990. break;
  1991.       }
  1992.     }
  1993.     par=x->parent;
  1994.   }
  1995.   x->color=SEL_ARG::BLACK;
  1996.   return root;
  1997. }
  2000. /* Test that the proporties for a red-black tree holds */
  2002. #ifdef EXTRA_DEBUG
  2003. int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
  2004. {
  2005.   int count_l,count_r;
  2007.   if (element == &null_element)
  2008.     return 0; // Found end of tree
  2009.   if (element->parent != parent)
  2010.   {
  2011.     sql_print_error("Wrong tree: Parent doesn't point at parent");
  2012.     return -1;
  2013.   }
  2014.   if (element->color == SEL_ARG::RED &&
  2015.       (element->left->color == SEL_ARG::RED ||
  2016.        element->right->color == SEL_ARG::RED))
  2017.   {
  2018.     sql_print_error("Wrong tree: Found two red in a row");
  2019.     return -1;
  2020.   }
  2021.   if (element->left == element->right && element->left != &null_element)
  2022.   { // Dummy test
  2023.     sql_print_error("Wrong tree: Found right == left");
  2024.     return -1;
  2025.   }
  2026.   count_l=test_rb_tree(element->left,element);
  2027.   count_r=test_rb_tree(element->right,element);
  2028.   if (count_l >= 0 && count_r >= 0)
  2029.   {
  2030.     if (count_l == count_r)
  2031.       return count_l+(element->color == SEL_ARG::BLACK);
  2032.     sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
  2033.     count_l,count_r);
  2034.   }
  2035.   return -1; // Error, no more warnings
  2036. }
  2038. static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
  2039. {
  2040.   ulong count= 0;
  2041.   for (root=root->first(); root ; root=root->next)
  2042.   {
  2043.     if (root->next_key_part)
  2044.     {
  2045.       if (root->next_key_part == key)
  2046. count++;
  2047.       if (root->next_key_part->part < key->part)
  2048. count+=count_key_part_usage(root->next_key_part,key);
  2049.     }
  2050.   }
  2051.   return count;
  2052. }
  2055. void SEL_ARG::test_use_count(SEL_ARG *root)
  2056. {
  2057.   if (this == root && use_count != 1)
  2058.   {
  2059.     sql_print_error("Use_count: Wrong count %lu for root",use_count);
  2060.     return;
  2061.   }
  2062.   if (this->type != SEL_ARG::KEY_RANGE)
  2063.     return;
  2064.   uint e_count=0;
  2065.   for (SEL_ARG *pos=first(); pos ; pos=pos->next)
  2066.   {
  2067.     e_count++;
  2068.     if (pos->next_key_part)
  2069.     {
  2070.       ulong count=count_key_part_usage(root,pos->next_key_part);
  2071.       if (count > pos->next_key_part->use_count)
  2072.       {
  2073. sql_print_error("Use_count: Wrong count for key at %lx, %lu should be %lu",
  2074. pos,pos->next_key_part->use_count,count);
  2075. return;
  2076.       }
  2077.       pos->next_key_part->test_use_count(root);
  2078.     }
  2079.   }
  2080.   if (e_count != elements)
  2081.     sql_print_error("Wrong use count: %u for tree at %lx", e_count,
  2082.     (gptr) this);
  2083. }
  2085. #endif
  2089. /*****************************************************************************
  2090. ** Check how many records we will find by using the found tree
  2091. *****************************************************************************/
  2093. static ha_rows
  2094. check_quick_select(PARAM *param,uint idx,SEL_ARG *tree)
  2095. {
  2096.   ha_rows records;
  2097.   DBUG_ENTER("check_quick_select");
  2099.   if (!tree)
  2100.     DBUG_RETURN(HA_POS_ERROR); // Can't use it
  2101.   if (tree->type == SEL_ARG::IMPOSSIBLE)
  2102.     DBUG_RETURN(0L); // Impossible select. return
  2103.   if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
  2104.     DBUG_RETURN(HA_POS_ERROR); // Don't use tree
  2105.   param->max_key_part=0;
  2106.   records=check_quick_keys(param,idx,tree,param->min_key,0,param->max_key,0);
  2107.   if (records != HA_POS_ERROR)
  2108.   {
  2109.     uint key=param->real_keynr[idx];
  2110.     param->table->quick_keys|= (key_map) 1 << key;
  2111.     param->table->quick_rows[key]=records;
  2112.     param->table->quick_key_parts[key]=param->max_key_part+1;
  2113.   }
  2114.   DBUG_RETURN(records);
  2115. }
  2118. static ha_rows
  2119. check_quick_keys(PARAM *param,uint idx,SEL_ARG *key_tree,
  2120.  char *min_key,uint min_key_flag, char *max_key,
  2121.  uint max_key_flag)
  2122. {
  2123.   ha_rows records=0,tmp;
  2125.   param->max_key_part=max(param->max_key_part,key_tree->part);
  2126.   if (key_tree->left != &null_element)
  2127.   {
  2128.     records=check_quick_keys(param,idx,key_tree->left,min_key,min_key_flag,
  2129.      max_key,max_key_flag);
  2130.     if (records == HA_POS_ERROR) // Impossible
  2131.       return records;
  2132.   }
  2134.   uint tmp_min_flag,tmp_max_flag,keynr;
  2135.   char *tmp_min_key=min_key,*tmp_max_key=max_key;
  2137.   key_tree->store(param->key[idx][key_tree->part].part_length,
  2138.   &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);
  2139.   uint min_key_length= (uint) (tmp_min_key- param->min_key);
  2140.   uint max_key_length= (uint) (tmp_max_key- param->max_key);
  2142.   if (key_tree->next_key_part &&
  2143.       key_tree->next_key_part->part == key_tree->part+1 &&
  2144.       key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  2145.   { // const key as prefix
  2146.     if (min_key_length == max_key_length &&
  2147. !memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) &&
  2148. !key_tree->min_flag && !key_tree->max_flag)
  2149.     {
  2150.       tmp=check_quick_keys(param,idx,key_tree->next_key_part,
  2151.    tmp_min_key, min_key_flag | key_tree->min_flag,
  2152.    tmp_max_key, max_key_flag | key_tree->max_flag);
  2153.       goto end; // Ugly, but efficient
  2154.     }
  2155.     tmp_min_flag=key_tree->min_flag;
  2156.     tmp_max_flag=key_tree->max_flag;
  2157.     if (!tmp_min_flag)
  2158.       key_tree->next_key_part->store_min_key(param->key[idx], &tmp_min_key,
  2159.      &tmp_min_flag);
  2160.     if (!tmp_max_flag)
  2161.       key_tree->next_key_part->store_max_key(param->key[idx], &tmp_max_key,
  2162.      &tmp_max_flag);
  2163.     min_key_length= (uint) (tmp_min_key- param->min_key);
  2164.     max_key_length= (uint) (tmp_max_key- param->max_key);
  2165.   }
  2166.   else
  2167.   {
  2168.     tmp_min_flag=min_key_flag | key_tree->min_flag;
  2169.     tmp_max_flag=max_key_flag | key_tree->max_flag;
  2170.   }
  2172.   keynr=param->real_keynr[idx];
  2173.   if (!tmp_min_flag && ! tmp_max_flag &&
  2174.       (uint) key_tree->part+1 == param->table->key_info[keynr].key_parts &&
  2175.       (param->table->key_info[keynr].flags & HA_NOSAME) &&
  2176.       min_key_length == max_key_length &&
  2177.       !memcmp(param->min_key,param->max_key,min_key_length))
  2178.     tmp=1; // Max one record
  2179.   else
  2180.       tmp=param->table->file->
  2181. records_in_range((int) keynr,
  2182.  (byte*) (!min_key_length ? NullS :
  2183.   param->min_key),
  2184.  min_key_length,
  2185.  (tmp_min_flag & NEAR_MIN ?
  2186.   HA_READ_AFTER_KEY : HA_READ_KEY_EXACT),
  2187.  (byte*) (!max_key_length ? NullS :
  2188.   param->max_key),
  2189.  max_key_length,
  2190.  (tmp_max_flag & NEAR_MAX ?
  2191.   HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY));
  2192.  end:
  2193.   if (tmp == HA_POS_ERROR) // Impossible range
  2194.     return tmp;
  2195.   records+=tmp;
  2196.   if (key_tree->right != &null_element)
  2197.   {
  2198.     tmp=check_quick_keys(param,idx,key_tree->right,min_key,min_key_flag,
  2199.  max_key,max_key_flag);
  2200.     if (tmp == HA_POS_ERROR)
  2201.       return tmp;
  2202.     records+=tmp;
  2203.   }
  2204.   return records;
  2205. }
  2208. /****************************************************************************
  2209. ** change a tree to a structure to be used by quick_select
  2210. ** This uses it's own malloc tree
  2211. ****************************************************************************/
  2213. static QUICK_SELECT *
  2214. get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree)
  2215. {
  2216.   QUICK_SELECT *quick;
  2217.   DBUG_ENTER("get_quick_select");
  2218.   if ((quick=new QUICK_SELECT(param->table,param->real_keynr[idx])))
  2219.   {
  2220.     if (quick->error ||
  2221. get_quick_keys(param,quick,param->key[idx],key_tree,param->min_key,0,
  2222.        param->max_key,0))
  2223.     {
  2224.       delete quick;
  2225.       quick=0;
  2226.     }
  2227.     else
  2228.     {
  2229.       quick->key_parts=(KEY_PART*)
  2230. sql_memdup(param->key[idx],
  2231.    sizeof(KEY_PART)*
  2232.    param->table->key_info[param->real_keynr[idx]].key_parts);
  2233.     }
  2234.   }
  2235.   DBUG_RETURN(quick);
  2236. }
  2239. /*
  2240. ** Fix this to get all possible sub_ranges
  2241. */
  2243. static bool
  2244. get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
  2245.        SEL_ARG *key_tree,char *min_key,uint min_key_flag,
  2246.        char *max_key, uint max_key_flag)
  2247. {
  2248.   QUICK_RANGE *range;
  2249.   uint flag;
  2251.   if (key_tree->left != &null_element)
  2252.   {
  2253.     if (get_quick_keys(param,quick,key,key_tree->left,
  2254.        min_key,min_key_flag, max_key, max_key_flag))
  2255.       return 1;
  2256.   }
  2257.   char *tmp_min_key=min_key,*tmp_max_key=max_key;
  2258.   key_tree->store(key[key_tree->part].part_length,
  2259.   &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);
  2261.   if (key_tree->next_key_part &&
  2262.       key_tree->next_key_part->part == key_tree->part+1 &&
  2263.       key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  2264.   {   // const key as prefix
  2265.     if (!((tmp_min_key - min_key) != (tmp_max_key - max_key) ||
  2266.   memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) ||
  2267.   key_tree->min_flag || key_tree->max_flag))
  2268.     {
  2269.       if (get_quick_keys(param,quick,key,key_tree->next_key_part,
  2270.  tmp_min_key, min_key_flag | key_tree->min_flag,
  2271.  tmp_max_key, max_key_flag | key_tree->max_flag))
  2272. return 1;
  2273.       goto end; // Ugly, but efficient
  2274.     }
  2275.     {
  2276.       uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
  2277.       if (!tmp_min_flag)
  2278. key_tree->next_key_part->store_min_key(key, &tmp_min_key,
  2279.        &tmp_min_flag);
  2280.       if (!tmp_max_flag)
  2281. key_tree->next_key_part->store_max_key(key, &tmp_max_key,
  2282.        &tmp_max_flag);
  2283.       flag=tmp_min_flag | tmp_max_flag;
  2284.     }
  2285.   }
  2286.   else
  2287.     flag=key_tree->min_flag | key_tree->max_flag;
  2289.   /* Ensure that some part of min_key and max_key are used.  If not,
  2290.      regard this as no lower/upper range */
  2291.   if (tmp_min_key != param->min_key)
  2292.     flag&= ~NO_MIN_RANGE;
  2293.   else
  2294.     flag|= NO_MIN_RANGE;
  2295.   if (tmp_max_key != param->max_key)
  2296.     flag&= ~NO_MAX_RANGE;
  2297.   else
  2298.     flag|= NO_MAX_RANGE;
  2300.   if (flag == 0)
  2301.   {
  2302.     uint length= (uint) (tmp_min_key - param->min_key);
  2303.     if (length == (uint) (tmp_max_key - param->max_key) &&
  2304. !memcmp(param->min_key,param->max_key,length))
  2305.     {
  2306.       KEY *table_key=quick->head->key_info+quick->index;
  2307.       flag=EQ_RANGE;
  2308.       if (table_key->flags & HA_NOSAME && key->part == table_key->key_parts-1)
  2309. flag|= UNIQUE_RANGE;
  2310.     }
  2311.   }
  2313.   /* Get range for retrieving rows in QUICK_SELECT::get_next */
  2314.   range= new QUICK_RANGE(param->min_key,
  2315.  (uint) (tmp_min_key - param->min_key),
  2316.  param->max_key,
  2317.  (uint) (tmp_max_key - param->max_key),
  2318.  flag);
  2319.   set_if_bigger(quick->max_used_key_length,range->min_length);
  2320.   set_if_bigger(quick->max_used_key_length,range->max_length);
  2321.   if (!range) // Not enough memory
  2322.     return 1;
  2323.   quick->ranges.push_back(range);
  2325.  end:
  2326.   if (key_tree->right != &null_element)
  2327.     return get_quick_keys(param,quick,key,key_tree->right,
  2328.   min_key,min_key_flag,
  2329.   max_key,max_key_flag);
  2330.   return 0;
  2331. }
  2333. /*
  2334.   Return 1 if there is only one range and this uses the whole primary key
  2335. */
  2337. bool QUICK_SELECT::unique_key_range()
  2338. {
  2339.   if (ranges.elements == 1)
  2340.   {
  2341.     QUICK_RANGE *tmp;
  2342.     if ((tmp=ranges.head())->flag & EQ_RANGE)
  2343.     {
  2344.       KEY *key=head->key_info+index;
  2345.       return ((key->flags & HA_NOSAME) &&
  2346.       key->key_length == tmp->min_length);
  2347.     }
  2348.   }
  2349.   return 0;
  2350. }
  2352. /****************************************************************************
  2353. ** Create a QUICK RANGE based on a key
  2354. ****************************************************************************/
  2356. QUICK_SELECT *get_quick_select_for_ref(TABLE *table, TABLE_REF *ref)
  2357. {
  2358.   table->file->index_end(); // Remove old cursor
  2359.   QUICK_SELECT *quick=new QUICK_SELECT(table, ref->key, 1);
  2360.   KEY *key_info = &table->key_info[ref->key];
  2361.   KEY_PART *key_part;
  2362.   uint part;
  2364.   if (!quick)
  2365.     return 0;
  2366.   QUICK_RANGE *range= new QUICK_RANGE();
  2367.   if (!range || cp_buffer_from_ref(ref))
  2368.     goto err;
  2369.   range->min_key=range->max_key=(char*) ref->key_buff;
  2370.   range->min_length=range->max_length=ref->key_length;
  2371.   range->flag= ((ref->key_length == key_info->key_length &&
  2372.  (key_info->flags & HA_NOSAME)) ? EQ_RANGE : 0);
  2374.   if (!(quick->key_parts=key_part=(KEY_PART *)
  2375. sql_alloc(sizeof(KEY_PART)*ref->key_parts)))
  2376.     goto err;
  2378.   for (part=0 ; part < ref->key_parts ;part++,key_part++)
  2379.   {
  2380.     key_part->part=part;
  2381.     key_part->field=        key_info->key_part[part].field;
  2382.     key_part->part_length=  key_info->key_part[part].length;
  2383.     if (key_part->field->type() == FIELD_TYPE_BLOB)
  2384.       key_part->part_length+=HA_KEY_BLOB_LENGTH;
  2385.     key_part->null_bit=     key_info->key_part[part].null_bit;
  2386.   }
  2387.   if (!quick->ranges.push_back(range))
  2388.     return quick;
  2390. err:
  2391.   delete quick;
  2392.   return 0;
  2393. }
  2395. /* get next possible record using quick-struct */
  2397. int QUICK_SELECT::get_next()
  2398. {
  2399.   DBUG_ENTER("get_next");
  2401.   for (;;)
  2402.   {
  2403.     if (range)
  2404.     { // Already read through key
  2405.       int result=((range->flag & EQ_RANGE) ?
  2406.   file->index_next_same(record, (byte*) range->min_key,
  2407. range->min_length) :
  2408.   file->index_next(record));
  2409.       if (!result && !cmp_next(*it.ref()))
  2410. DBUG_RETURN(0);
  2411.     }
  2412.     if (!(range=it++))
  2413.       DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used
  2414.     if (range->flag & NO_MIN_RANGE) // Read first record
  2415.     {
  2416.       int error;
  2417.       if ((error=file->index_first(record)))
  2418. DBUG_RETURN(error); // Empty table
  2419.       if (cmp_next(range) == 0)
  2420. DBUG_RETURN(0); // No matching records
  2421.       range=0; // To next range
  2422.       continue;
  2423.     }
  2424.     if (file->index_read(record,(byte*) range->min_key,
  2425.  range->min_length,
  2426.  ((range->flag & NEAR_MIN) ?
  2427.   HA_READ_AFTER_KEY:
  2428.   (range->flag & EQ_RANGE) ?
  2429.   HA_READ_KEY_EXACT :
  2430.   HA_READ_KEY_OR_NEXT)))
  2432.     {
  2433.       range=0; // Not found, to next range
  2434.       continue;
  2435.     }
  2436.     if (cmp_next(range) == 0)
  2437.     {
  2438.       if (range->flag == (UNIQUE_RANGE | EQ_RANGE))
  2439. range=0; // Stop searching
  2440.       DBUG_RETURN(0); // Found key is in range
  2441.     }
  2442.     range=0; // To next range
  2443.   }
  2444. }
  2446. /* compare if found key is over max-value */
  2447. /* Returns 0 if key <= range->max_key */
  2449. int QUICK_SELECT::cmp_next(QUICK_RANGE *range)
  2450. {
  2451.   if (range->flag & NO_MAX_RANGE)
  2452.     return (0); /* key can't be to large */
  2454.   KEY_PART *key_part=key_parts;
  2455.   for (char *key=range->max_key, *end=key+range->max_length;
  2456.        key < end;
  2457.        key+= key_part++->part_length)
  2458.   {
  2459.     int cmp;
  2460.     if (key_part->null_bit)
  2461.     {
  2462.       if (*key++)
  2463.       {
  2464. if (!key_part->field->is_null())
  2465.   return 1;
  2466. continue;
  2467.       }
  2468.       else if (key_part->field->is_null())
  2469. return 0;
  2470.     }
  2471.     if ((cmp=key_part->field->key_cmp((byte*) key, key_part->part_length)) < 0)
  2472.       return 0;
  2473.     if (cmp > 0)
  2474.       return 1;
  2475.   }
  2476.   return (range->flag & NEAR_MAX) ? 1 : 0; // Exact match
  2477. }
  2479. /*****************************************************************************
  2480. ** Print a quick range for debugging
  2481. ** TODO:
  2482. ** This should be changed to use a String to store each row instead
  2483. ** of locking the DEBUG stream !
  2484. *****************************************************************************/
  2486. #ifndef DBUG_OFF
  2488. static void
  2489. print_key(KEY_PART *key_part,const char *key,uint used_length)
  2490. {
  2491.   char buff[1024];
  2492.   String tmp(buff,sizeof(buff));
  2494.   for (uint length=0;
  2495.        length < used_length ;
  2496.        length+=key_part->part_length, key+=key_part->part_length, key_part++)
  2497.   {
  2498.     Field *field=key_part->field;
  2499.     if (length != 0)
  2500.       fputc('/',DBUG_FILE);
  2501.     if (field->real_maybe_null())
  2502.     {
  2503.       length++; // null byte is not in part_length 
  2504.       if (*key++)
  2505.       {
  2506. fwrite("NULL",sizeof(char),4,DBUG_FILE);
  2507. continue;
  2508.       }
  2509.     }
  2510.     field->set_key_image((char*) key,key_part->part_length -
  2511.  ((field->type() == FIELD_TYPE_BLOB) ?
  2512.   HA_KEY_BLOB_LENGTH : 0));
  2513.     field->val_str(&tmp,&tmp);
  2514.     fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
  2515.   }
  2516. }
  2518. static void print_quick(QUICK_SELECT *quick,key_map needed_reg)
  2519. {
  2520.   QUICK_RANGE *range;
  2521.   DBUG_ENTER("print_param");
  2522.   if (! _db_on_ || !quick)
  2523.     DBUG_VOID_RETURN;
  2525.   List_iterator<QUICK_RANGE> li(quick->ranges);
  2526.   DBUG_LOCK_FILE;
  2527.   fprintf(DBUG_FILE,"Used quick_range on key: %d (other_keys: %lu):n",
  2528.   quick->index, (ulong) needed_reg);
  2529.   while ((range=li++))
  2530.   {
  2531.     if (!(range->flag & NO_MIN_RANGE))
  2532.     {
  2533.       print_key(quick->key_parts,range->min_key,range->min_length);
  2534.       if (range->flag & NEAR_MIN)
  2535. fputs(" < ",DBUG_FILE);
  2536.       else
  2537. fputs(" <= ",DBUG_FILE);
  2538.     }
  2539.     fputs("X",DBUG_FILE);
  2541.     if (!(range->flag & NO_MAX_RANGE))
  2542.     {
  2543.       if (range->flag & NEAR_MAX)
  2544. fputs(" < ",DBUG_FILE);
  2545.       else
  2546. fputs(" <= ",DBUG_FILE);
  2547.       print_key(quick->key_parts,range->max_key,range->max_length);
  2548.     }
  2549.     fputs("n",DBUG_FILE);
  2550.   }
  2551.   DBUG_UNLOCK_FILE;
  2552.   DBUG_VOID_RETURN;
  2553. }
  2555. #endif
  2557. /*****************************************************************************
  2558. ** Instansiate templates
  2559. *****************************************************************************/
  2561. #ifdef __GNUC__
  2562. template class List<QUICK_RANGE>;
  2563. template class List_iterator<QUICK_RANGE>;
  2564. #endif