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