opt_range.cpp
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:83k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. /*
  14.   TODO:
  15.   Fix that MAYBE_KEY are stored in the tree so that we can detect use
  16.   of full hash keys for queries like:
  17.   select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);
  18. */
  19. #ifdef USE_PRAGMA_IMPLEMENTATION
  20. #pragma implementation // gcc: Class implementation
  21. #endif
  22. #include "mysql_priv.h"
  23. #include <m_ctype.h>
  24. #include <nisam.h>
  25. #include "sql_select.h"
  26. #ifndef EXTRA_DEBUG
  27. #define test_rb_tree(A,B) {}
  28. #define test_use_count(A) {}
  29. #endif
  30. static int sel_cmp(Field *f,char *a,char *b,uint8 a_flag,uint8 b_flag);
  31. static char is_null_string[2]= {1,0};
  32. class SEL_ARG :public Sql_alloc
  33. {
  34. public:
  35.   uint8 min_flag,max_flag,maybe_flag;
  36.   uint8 part; // Which key part
  37.   uint8 maybe_null;
  38.   uint16 elements; // Elements in tree
  39.   ulong use_count; // use of this sub_tree
  40.   Field *field;
  41.   char *min_value,*max_value; // Pointer to range
  42.   SEL_ARG *left,*right,*next,*prev,*parent,*next_key_part;
  43.   enum leaf_color { BLACK,RED } color;
  44.   enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
  45.   SEL_ARG() {}
  46.   SEL_ARG(SEL_ARG &);
  47.   SEL_ARG(Field *,const char *,const char *);
  48.   SEL_ARG(Field *field, uint8 part, char *min_value, char *max_value,
  49.   uint8 min_flag, uint8 max_flag, uint8 maybe_flag);
  50.   SEL_ARG(enum Type type_arg)
  51.     :elements(1),use_count(1),left(0),next_key_part(0),color(BLACK),
  52.      type(type_arg)
  53.   {}
  54.   inline bool is_same(SEL_ARG *arg)
  55.   {
  56.     if (type != arg->type || part != arg->part)
  57.       return 0;
  58.     if (type != KEY_RANGE)
  59.       return 1;
  60.     return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
  61.   }
  62.   inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
  63.   inline void maybe_smaller() { maybe_flag=1; }
  64.   inline int cmp_min_to_min(SEL_ARG* arg)
  65.   {
  66.     return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
  67.   }
  68.   inline int cmp_min_to_max(SEL_ARG* arg)
  69.   {
  70.     return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
  71.   }
  72.   inline int cmp_max_to_max(SEL_ARG* arg)
  73.   {
  74.     return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
  75.   }
  76.   inline int cmp_max_to_min(SEL_ARG* arg)
  77.   {
  78.     return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
  79.   }
  80.   SEL_ARG *clone_and(SEL_ARG* arg)
  81.   { // Get overlapping range
  82.     char *new_min,*new_max;
  83.     uint8 flag_min,flag_max;
  84.     if (cmp_min_to_min(arg) >= 0)
  85.     {
  86.       new_min=min_value; flag_min=min_flag;
  87.     }
  88.     else
  89.     {
  90.       new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
  91.     }
  92.     if (cmp_max_to_max(arg) <= 0)
  93.     {
  94.       new_max=max_value; flag_max=max_flag;
  95.     }
  96.     else
  97.     {
  98.       new_max=arg->max_value; flag_max=arg->max_flag;
  99.     }
  100.     return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
  101.        test(maybe_flag && arg->maybe_flag));
  102.   }
  103.   SEL_ARG *clone_first(SEL_ARG *arg)
  104.   { // min <= X < arg->min
  105.     return new SEL_ARG(field,part, min_value, arg->min_value,
  106.        min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
  107.        maybe_flag | arg->maybe_flag);
  108.   }
  109.   SEL_ARG *clone_last(SEL_ARG *arg)
  110.   { // min <= X <= key_max
  111.     return new SEL_ARG(field, part, min_value, arg->max_value,
  112.        min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
  113.   }
  114.   SEL_ARG *clone(SEL_ARG *new_parent,SEL_ARG **next);
  115.   bool copy_min(SEL_ARG* arg)
  116.   { // Get overlapping range
  117.     if (cmp_min_to_min(arg) > 0)
  118.     {
  119.       min_value=arg->min_value; min_flag=arg->min_flag;
  120.       if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
  121.   (NO_MAX_RANGE | NO_MIN_RANGE))
  122. return 1; // Full range
  123.     }
  124.     maybe_flag|=arg->maybe_flag;
  125.     return 0;
  126.   }
  127.   bool copy_max(SEL_ARG* arg)
  128.   { // Get overlapping range
  129.     if (cmp_max_to_max(arg) <= 0)
  130.     {
  131.       max_value=arg->max_value; max_flag=arg->max_flag;
  132.       if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
  133.   (NO_MAX_RANGE | NO_MIN_RANGE))
  134. return 1; // Full range
  135.     }
  136.     maybe_flag|=arg->maybe_flag;
  137.     return 0;
  138.   }
  139.   void copy_min_to_min(SEL_ARG *arg)
  140.   {
  141.     min_value=arg->min_value; min_flag=arg->min_flag;
  142.   }
  143.   void copy_min_to_max(SEL_ARG *arg)
  144.   {
  145.     max_value=arg->min_value;
  146.     max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
  147.   }
  148.   void copy_max_to_min(SEL_ARG *arg)
  149.   {
  150.     min_value=arg->max_value;
  151.     min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
  152.   }
  153.   void store(uint length,char **min_key,uint min_key_flag,
  154.      char **max_key, uint max_key_flag)
  155.   {
  156.     if ((min_flag & GEOM_FLAG) ||
  157.         (!(min_flag & NO_MIN_RANGE) &&
  158. !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
  159.     {
  160.       if (maybe_null && *min_value)
  161.       {
  162. **min_key=1;
  163. bzero(*min_key+1,length-1);
  164.       }
  165.       else
  166. memcpy(*min_key,min_value,length);
  167.       (*min_key)+= length;
  168.     }
  169.     if (!(max_flag & NO_MAX_RANGE) &&
  170. !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
  171.     {
  172.       if (maybe_null && *max_value)
  173.       {
  174. **max_key=1;
  175. bzero(*max_key+1,length-1);
  176.       }
  177.       else
  178. memcpy(*max_key,max_value,length);
  179.       (*max_key)+= length;
  180.     }
  181.   }
  182.   void store_min_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  183.   {
  184.     SEL_ARG *key_tree= first();
  185.     key_tree->store(key[key_tree->part].store_length,
  186.     range_key,*range_key_flag,range_key,NO_MAX_RANGE);
  187.     *range_key_flag|= key_tree->min_flag;
  188.     if (key_tree->next_key_part &&
  189. key_tree->next_key_part->part == key_tree->part+1 &&
  190. !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
  191. key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  192.       key_tree->next_key_part->store_min_key(key,range_key, range_key_flag);
  193.   }
  194.   void store_max_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  195.   {
  196.     SEL_ARG *key_tree= last();
  197.     key_tree->store(key[key_tree->part].store_length,
  198.     range_key, NO_MIN_RANGE, range_key,*range_key_flag);
  199.     (*range_key_flag)|= key_tree->max_flag;
  200.     if (key_tree->next_key_part &&
  201. key_tree->next_key_part->part == key_tree->part+1 &&
  202. !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
  203. key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  204.       key_tree->next_key_part->store_max_key(key,range_key, range_key_flag);
  205.   }
  206.   SEL_ARG *insert(SEL_ARG *key);
  207.   SEL_ARG *tree_delete(SEL_ARG *key);
  208.   SEL_ARG *find_range(SEL_ARG *key);
  209.   SEL_ARG *rb_insert(SEL_ARG *leaf);
  210.   friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
  211. #ifdef EXTRA_DEBUG
  212.   friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
  213.   void test_use_count(SEL_ARG *root);
  214. #endif
  215.   SEL_ARG *first();
  216.   SEL_ARG *last();
  217.   void make_root();
  218.   inline bool simple_key()
  219.   {
  220.     return !next_key_part && elements == 1;
  221.   }
  222.   void increment_use_count(long count)
  223.   {
  224.     if (next_key_part)
  225.     {
  226.       next_key_part->use_count+=count;
  227.       count*= (next_key_part->use_count-count);
  228.       for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
  229. if (pos->next_key_part)
  230.   pos->increment_use_count(count);
  231.     }
  232.   }
  233.   void free_tree()
  234.   {
  235.     for (SEL_ARG *pos=first(); pos ; pos=pos->next)
  236.       if (pos->next_key_part)
  237.       {
  238. pos->next_key_part->use_count--;
  239. pos->next_key_part->free_tree();
  240.       }
  241.   }
  242.   inline SEL_ARG **parent_ptr()
  243.   {
  244.     return parent->left == this ? &parent->left : &parent->right;
  245.   }
  246.   SEL_ARG *clone_tree();
  247. };
  248. class SEL_TREE :public Sql_alloc
  249. {
  250. public:
  251.   enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
  252.   SEL_TREE(enum Type type_arg) :type(type_arg) {}
  253.   SEL_TREE() :type(KEY) { bzero((char*) keys,sizeof(keys));}
  254.   SEL_ARG *keys[MAX_KEY];
  255. };
  256. typedef struct st_qsel_param {
  257.   THD *thd;
  258.   TABLE *table;
  259.   KEY_PART *key_parts,*key_parts_end,*key[MAX_KEY];
  260.   MEM_ROOT *mem_root;
  261.   table_map prev_tables,read_tables,current_table;
  262.   uint baseflag, keys, max_key_part, range_count;
  263.   uint real_keynr[MAX_KEY];
  264.   char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
  265.     max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
  266.   bool quick; // Don't calulate possible keys
  267.   COND *cond;
  268. } PARAM;
  269. static SEL_TREE * get_mm_parts(PARAM *param,COND *cond_func,Field *field,
  270.        Item_func::Functype type,Item *value,
  271.        Item_result cmp_type);
  272. static SEL_ARG *get_mm_leaf(PARAM *param,COND *cond_func,Field *field,
  273.     KEY_PART *key_part,
  274.     Item_func::Functype type,Item *value);
  275. static SEL_TREE *get_mm_tree(PARAM *param,COND *cond);
  276. static ha_rows check_quick_select(PARAM *param,uint index,SEL_ARG *key_tree);
  277. static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
  278. char *min_key,uint min_key_flag,
  279. char *max_key, uint max_key_flag);
  280. static QUICK_SELECT *get_quick_select(PARAM *param,uint index,
  281.       SEL_ARG *key_tree);
  282. #ifndef DBUG_OFF
  283. static void print_quick(QUICK_SELECT *quick,const key_map* needed_reg);
  284. #endif
  285. static SEL_TREE *tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
  286. static SEL_TREE *tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
  287. static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
  288. static SEL_ARG *key_or(SEL_ARG *key1,SEL_ARG *key2);
  289. static SEL_ARG *key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag);
  290. static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
  291. static bool get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
  292.    SEL_ARG *key_tree,char *min_key,uint min_key_flag,
  293.    char *max_key,uint max_key_flag);
  294. static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
  295. static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
  296. static bool null_part_in_key(KEY_PART *key_part, const char *key, uint length);
  297. /***************************************************************************
  298. ** Basic functions for SQL_SELECT and QUICK_SELECT
  299. ***************************************************************************/
  300. /* make a select from mysql info
  301.    Error is set as following:
  302.    0 = ok
  303.    1 = Got some error (out of memory?)
  304.    */
  305. SQL_SELECT *make_select(TABLE *head, table_map const_tables,
  306. table_map read_tables, COND *conds, int *error)
  307. {
  308.   SQL_SELECT *select;
  309.   DBUG_ENTER("make_select");
  310.   *error=0;
  311.   if (!conds)
  312.     DBUG_RETURN(0);
  313.   if (!(select= new SQL_SELECT))
  314.   {
  315.     *error= 1; // out of memory
  316.     DBUG_RETURN(0); /* purecov: inspected */
  317.   }
  318.   select->read_tables=read_tables;
  319.   select->const_tables=const_tables;
  320.   select->head=head;
  321.   select->cond=conds;
  322.   if (head->sort.io_cache)
  323.   {
  324.     select->file= *head->sort.io_cache;
  325.     select->records=(ha_rows) (select->file.end_of_file/
  326.        head->file->ref_length);
  327.     my_free((gptr) (head->sort.io_cache),MYF(0));
  328.     head->sort.io_cache=0;
  329.   }
  330.   DBUG_RETURN(select);
  331. }
  332. SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
  333. {
  334.   quick_keys.clear_all(); needed_reg.clear_all();
  335.   my_b_clear(&file);
  336. }
  337. void SQL_SELECT::cleanup()
  338. {
  339.   delete quick;
  340.   quick= 0;
  341.   if (free_cond)
  342.   {
  343.     free_cond=0;
  344.     delete cond;
  345.     cond= 0;
  346.   }    
  347.   close_cached_file(&file);
  348. }
  349. SQL_SELECT::~SQL_SELECT()
  350. {
  351.   cleanup();
  352. }
  353. #undef index // Fix for Unixware 7
  354. QUICK_SELECT::QUICK_SELECT(THD *thd, TABLE *table, uint key_nr, bool no_alloc)
  355.   :dont_free(0),sorted(0),error(0),index(key_nr),max_used_key_length(0),
  356.    used_key_parts(0), head(table), it(ranges),range(0)
  357. {
  358.   if (!no_alloc)
  359.   {
  360.     // Allocates everything through the internal memroot
  361.     init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
  362.     thd->mem_root= &alloc;
  363.   }
  364.   else
  365.     bzero((char*) &alloc,sizeof(alloc));
  366.   file=head->file;
  367.   record=head->record[0];
  368.   init();
  369. }
  370. QUICK_SELECT::~QUICK_SELECT()
  371. {
  372.   if (!dont_free)
  373.   {
  374.     if (file->inited)
  375.       file->ha_index_end();
  376.     free_root(&alloc,MYF(0));
  377.   }
  378. }
  379. QUICK_RANGE::QUICK_RANGE()
  380.   :min_key(0),max_key(0),min_length(0),max_length(0),
  381.    flag(NO_MIN_RANGE | NO_MAX_RANGE)
  382. {}
  383. SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
  384. {
  385.   type=arg.type;
  386.   min_flag=arg.min_flag;
  387.   max_flag=arg.max_flag;
  388.   maybe_flag=arg.maybe_flag;
  389.   maybe_null=arg.maybe_null;
  390.   part=arg.part;
  391.   field=arg.field;
  392.   min_value=arg.min_value;
  393.   max_value=arg.max_value;
  394.   next_key_part=arg.next_key_part;
  395.   use_count=1; elements=1;
  396. }
  397. inline void SEL_ARG::make_root()
  398. {
  399.   left=right= &null_element;
  400.   color=BLACK;
  401.   next=prev=0;
  402.   use_count=0; elements=1;
  403. }
  404. SEL_ARG::SEL_ARG(Field *f,const char *min_value_arg,const char *max_value_arg)
  405.   :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
  406.    elements(1), use_count(1), field(f), min_value((char*) min_value_arg),
  407.    max_value((char*) max_value_arg), next(0),prev(0),
  408.    next_key_part(0),color(BLACK),type(KEY_RANGE)
  409. {
  410.   left=right= &null_element;
  411. }
  412. SEL_ARG::SEL_ARG(Field *field_,uint8 part_,char *min_value_,char *max_value_,
  413.  uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_)
  414.   :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
  415.    part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
  416.    field(field_), min_value(min_value_), max_value(max_value_),
  417.    next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
  418. {
  419.   left=right= &null_element;
  420. }
  421. SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg)
  422. {
  423.   SEL_ARG *tmp;
  424.   if (type != KEY_RANGE)
  425.   {
  426.     if (!(tmp= new SEL_ARG(type)))
  427.       return 0; // out of memory
  428.     tmp->prev= *next_arg; // Link into next/prev chain
  429.     (*next_arg)->next=tmp;
  430.     (*next_arg)= tmp;
  431.   }
  432.   else
  433.   {
  434.     if (!(tmp= new SEL_ARG(field,part, min_value,max_value,
  435.    min_flag, max_flag, maybe_flag)))
  436.       return 0; // OOM
  437.     tmp->parent=new_parent;
  438.     tmp->next_key_part=next_key_part;
  439.     if (left != &null_element)
  440.       tmp->left=left->clone(tmp,next_arg);
  441.     tmp->prev= *next_arg; // Link into next/prev chain
  442.     (*next_arg)->next=tmp;
  443.     (*next_arg)= tmp;
  444.     if (right != &null_element)
  445.       if (!(tmp->right= right->clone(tmp,next_arg)))
  446. return 0; // OOM
  447.   }
  448.   increment_use_count(1);
  449.   tmp->color= color;
  450.   return tmp;
  451. }
  452. SEL_ARG *SEL_ARG::first()
  453. {
  454.   SEL_ARG *next_arg=this;
  455.   if (!next_arg->left)
  456.     return 0; // MAYBE_KEY
  457.   while (next_arg->left != &null_element)
  458.     next_arg=next_arg->left;
  459.   return next_arg;
  460. }
  461. SEL_ARG *SEL_ARG::last()
  462. {
  463.   SEL_ARG *next_arg=this;
  464.   if (!next_arg->right)
  465.     return 0; // MAYBE_KEY
  466.   while (next_arg->right != &null_element)
  467.     next_arg=next_arg->right;
  468.   return next_arg;
  469. }
  470. /*
  471.   Check if a compare is ok, when one takes ranges in account
  472.   Returns -2 or 2 if the ranges where 'joined' like  < 2 and >= 2
  473. */
  474. static int sel_cmp(Field *field, char *a,char *b,uint8 a_flag,uint8 b_flag)
  475. {
  476.   int cmp;
  477.   /* First check if there was a compare to a min or max element */
  478.   if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
  479.   {
  480.     if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
  481. (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
  482.       return 0;
  483.     return (a_flag & NO_MIN_RANGE) ? -1 : 1;
  484.   }
  485.   if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
  486.     return (b_flag & NO_MIN_RANGE) ? 1 : -1;
  487.   if (field->real_maybe_null()) // If null is part of key
  488.   {
  489.     if (*a != *b)
  490.     {
  491.       return *a ? -1 : 1;
  492.     }
  493.     if (*a)
  494.       goto end; // NULL where equal
  495.     a++; b++; // Skip NULL marker
  496.   }
  497.   cmp=field->key_cmp((byte*) a,(byte*) b);
  498.   if (cmp) return cmp < 0 ? -1 : 1; // The values differed
  499.   // Check if the compared equal arguments was defined with open/closed range
  500.  end:
  501.   if (a_flag & (NEAR_MIN | NEAR_MAX))
  502.   {
  503.     if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
  504.       return 0;
  505.     if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
  506.       return (a_flag & NEAR_MIN) ? 2 : -2;
  507.     return (a_flag & NEAR_MIN) ? 1 : -1;
  508.   }
  509.   if (b_flag & (NEAR_MIN | NEAR_MAX))
  510.     return (b_flag & NEAR_MIN) ? -2 : 2;
  511.   return 0; // The elements where equal
  512. }
  513. SEL_ARG *SEL_ARG::clone_tree()
  514. {
  515.   SEL_ARG tmp_link,*next_arg,*root;
  516.   next_arg= &tmp_link;
  517.   root= clone((SEL_ARG *) 0, &next_arg);
  518.   next_arg->next=0; // Fix last link
  519.   tmp_link.next->prev=0; // Fix first link
  520.   if (root) // If not OOM
  521.     root->use_count= 0;
  522.   return root;
  523. }
  524. /*
  525.   Find the best index to retrieve first N records in given order
  526.   SYNOPSIS
  527.     get_index_for_order()
  528.       table  Table to be accessed
  529.       order  Required ordering
  530.       limit  Number of records that will be retrieved
  531.   DESCRIPTION
  532.     Find the best index that allows to retrieve first #limit records in the 
  533.     given order cheaper then one would retrieve them using full table scan.
  534.   IMPLEMENTATION
  535.     Run through all table indexes and find the shortest index that allows
  536.     records to be retrieved in given order. We look for the shortest index
  537.     as we will have fewer index pages to read with it.
  538.     This function is used only by UPDATE/DELETE, so we take into account how
  539.     the UPDATE/DELETE code will work:
  540.      * index can only be scanned in forward direction
  541.      * HA_EXTRA_KEYREAD will not be used
  542.     Perhaps these assumptions could be relaxed
  543.   RETURN
  544.     index number
  545.     MAX_KEY if no such index was found.
  546. */
  547. uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit)
  548. {
  549.   uint idx;
  550.   uint match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
  551.   ORDER *ord;
  552.   
  553.   for (ord= order; ord; ord= ord->next)
  554.     if (!ord->asc)
  555.       return MAX_KEY;
  556.   for (idx= 0; idx < table->keys; idx++)
  557.   {
  558.     if (!(table->keys_in_use_for_query.is_set(idx)))
  559.       continue;
  560.     KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
  561.     uint partno= 0;
  562.     
  563.     /* 
  564.       The below check is sufficient considering we now have either BTREE 
  565.       indexes (records are returned in order for any index prefix) or HASH 
  566.       indexes (records are not returned in order for any index prefix).
  567.     */
  568.     if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
  569.       continue;
  570.     for (ord= order; ord; ord= ord->next, partno++)
  571.     {
  572.       Item *item= order->item[0];
  573.       if (!(item->type() == Item::FIELD_ITEM &&
  574.            ((Item_field*)item)->field->eq(keyinfo[partno].field)))
  575.         break;
  576.     }
  577.     
  578.     if (!ord && table->key_info[idx].key_length < match_key_len)
  579.     {
  580.       /* 
  581.         Ok, the ordering is compatible and this key is shorter then
  582.         previous match (we want shorter keys as we'll have to read fewer
  583.         index pages for the same number of records)
  584.       */
  585.       match_key= idx;
  586.       match_key_len= table->key_info[idx].key_length;
  587.     }
  588.   }
  589.   if (match_key != MAX_KEY)
  590.   {
  591.     /* 
  592.       Found an index that allows records to be retrieved in the requested 
  593.       order. Now we'll check if using the index is cheaper then doing a table
  594.       scan.
  595.     */
  596.     double full_scan_time= table->file->scan_time();
  597.     double index_scan_time= table->file->read_time(match_key, 1, limit);
  598.     if (index_scan_time > full_scan_time)
  599.       match_key= MAX_KEY;
  600.   }
  601.   return match_key;
  602. }
  603. /*
  604.   Test if a key can be used in different ranges
  605.   SYNOPSIS
  606.    SQL_SELECT::test_quick_select(thd,keys_to_use, prev_tables,
  607.                                  limit, force_quick_range)
  608.    Updates the following in the select parameter:
  609.     needed_reg - Bits for keys with may be used if all prev regs are read
  610.     quick      - Parameter to use when reading records.
  611.    In the table struct the following information is updated:
  612.     quick_keys - Which keys can be used
  613.     quick_rows - How many rows the key matches
  614.  RETURN VALUES
  615.   -1 if impossible select
  616.    0 if can't use quick_select
  617.    1 if found usable range
  618.  TODO
  619.    check if the function really needs to modify keys_to_use, and change the
  620.    code to pass it by reference if not
  621. */
  622. int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
  623.   table_map prev_tables,
  624.   ha_rows limit, bool force_quick_range)
  625. {
  626.   uint idx;
  627.   double scan_time;
  628.   DBUG_ENTER("test_quick_select");
  629.   DBUG_PRINT("enter",("keys_to_use: %lu  prev_tables: %lu  const_tables: %lu",
  630.       keys_to_use.to_ulonglong(), (ulong) prev_tables,
  631.       (ulong) const_tables));
  632.   delete quick;
  633.   quick=0;
  634.   needed_reg.clear_all(); quick_keys.clear_all();
  635.   if (!cond || (specialflag & SPECIAL_SAFE_MODE) && ! force_quick_range ||
  636.       !limit)
  637.     DBUG_RETURN(0); /* purecov: inspected */
  638.   if (keys_to_use.is_clear_all())
  639.     DBUG_RETURN(0);
  640.   records=head->file->records;
  641.   if (!records)
  642.     records++; /* purecov: inspected */
  643.   scan_time=(double) records / TIME_FOR_COMPARE+1;
  644.   read_time=(double) head->file->scan_time()+ scan_time + 1.1;
  645.   if (head->force_index)
  646.     scan_time= read_time= DBL_MAX;
  647.   if (limit < records)
  648.     read_time=(double) records+scan_time+1; // Force to use index
  649.   else if (read_time <= 2.0 && !force_quick_range)
  650.     DBUG_RETURN(0); /* No need for quick select */
  651.   DBUG_PRINT("info",("Time to scan table: %g", read_time));
  652.   keys_to_use.intersect(head->keys_in_use_for_query);
  653.   if (!keys_to_use.is_clear_all())
  654.   {
  655.     MEM_ROOT *old_root,alloc;
  656.     SEL_TREE *tree;
  657.     KEY_PART *key_parts;
  658.     KEY *key_info;
  659.     PARAM param;
  660.     /* set up parameter that is passed to all functions */
  661.     param.thd= thd;
  662.     param.baseflag=head->file->table_flags();
  663.     param.prev_tables=prev_tables | const_tables;
  664.     param.read_tables=read_tables;
  665.     param.current_table= head->map;
  666.     param.table=head;
  667.     param.keys=0;
  668.     param.mem_root= &alloc;
  669.     thd->no_errors=1; // Don't warn about NULL
  670.     init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
  671.     if (!(param.key_parts = (KEY_PART*) alloc_root(&alloc,
  672.    sizeof(KEY_PART)*
  673.    head->key_parts)))
  674.     {
  675.       thd->no_errors=0;
  676.       free_root(&alloc,MYF(0)); // Return memory & allocator
  677.       DBUG_RETURN(0); // Can't use range
  678.     }
  679.     key_parts= param.key_parts;
  680.     old_root= thd->mem_root;
  681.     thd->mem_root= &alloc;
  682.     key_info= head->key_info;
  683.     for (idx=0 ; idx < head->keys ; idx++, key_info++)
  684.     {
  685.       KEY_PART_INFO *key_part_info;
  686.       if (!keys_to_use.is_set(idx))
  687. continue;
  688.       if (key_info->flags & HA_FULLTEXT)
  689. continue;    // ToDo: ft-keys in non-ft ranges, if possible   SerG
  690.       param.key[param.keys]=key_parts;
  691.       key_part_info= key_info->key_part;
  692.       for (uint part=0 ; part < key_info->key_parts ;
  693.    part++, key_parts++, key_part_info++)
  694.       {
  695. key_parts->key=  param.keys;
  696. key_parts->part=  part;
  697. key_parts->length=       key_part_info->length;
  698. key_parts->store_length= key_part_info->store_length;
  699. key_parts->field=  key_part_info->field;
  700. key_parts->null_bit=  key_part_info->null_bit;
  701.         key_parts->image_type =
  702.           (key_info->flags & HA_SPATIAL) ? Field::itMBR : Field::itRAW;
  703.       }
  704.       param.real_keynr[param.keys++]=idx;
  705.     }
  706.     param.key_parts_end=key_parts;
  707.     if ((tree=get_mm_tree(&param,cond)))
  708.     {
  709.       if (tree->type == SEL_TREE::IMPOSSIBLE)
  710.       {
  711. records=0L; // Return -1 from this function
  712. read_time= (double) HA_POS_ERROR;
  713.       }
  714.       else if (tree->type == SEL_TREE::KEY ||
  715.        tree->type == SEL_TREE::KEY_SMALLER)
  716.       {
  717. SEL_ARG **key,**end,**best_key=0;
  718. for (idx=0,key=tree->keys, end=key+param.keys ;
  719.      key != end ;
  720.      key++,idx++)
  721. {
  722.   ha_rows found_records;
  723.   double found_read_time;
  724.   if (*key)
  725.   {
  726.     uint keynr= param.real_keynr[idx];
  727.     if ((*key)->type == SEL_ARG::MAYBE_KEY ||
  728. (*key)->maybe_flag)
  729.         needed_reg.set_bit(keynr);
  730.     found_records=check_quick_select(&param, idx, *key);
  731.     if (found_records != HA_POS_ERROR && found_records > 2 &&
  732. head->used_keys.is_set(keynr) &&
  733. (head->file->index_flags(keynr, param.max_key_part, 1) &
  734.                  HA_KEYREAD_ONLY))
  735.     {
  736.       /*
  737. We can resolve this by only reading through this key.
  738. Assume that we will read trough the whole key range
  739. and that all key blocks are half full (normally things are
  740. much better).
  741.       */
  742.       uint keys_per_block= (head->file->block_size/2/
  743.     (head->key_info[keynr].key_length+
  744.      head->file->ref_length) + 1);
  745.       found_read_time=((double) (found_records+keys_per_block-1)/
  746.        (double) keys_per_block);
  747.     }
  748.     else
  749.       found_read_time= (head->file->read_time(keynr,
  750.       param.range_count,
  751.       found_records)+
  752. (double) found_records / TIME_FOR_COMPARE);
  753.             DBUG_PRINT("info",("read_time: %g  found_read_time: %g",
  754.                                read_time, found_read_time));
  755.     if (read_time > found_read_time && found_records != HA_POS_ERROR)
  756.     {
  757.       read_time=found_read_time;
  758.       records=found_records;
  759.       best_key=key;
  760.     }
  761.   }
  762. }
  763. if (best_key && records)
  764. {
  765.   if ((quick=get_quick_select(&param,(uint) (best_key-tree->keys),
  766.       *best_key)))
  767.   {
  768.     quick->records=records;
  769.     quick->read_time=read_time;
  770.   }
  771. }
  772.       }
  773.     }
  774.     free_root(&alloc,MYF(0)); // Return memory & allocator
  775.     thd->mem_root= old_root;
  776.     thd->no_errors=0;
  777.   }
  778.   DBUG_EXECUTE("info",print_quick(quick,&needed_reg););
  779.   /*
  780.     Assume that if the user is using 'limit' we will only need to scan
  781.     limit rows if we are using a key
  782.   */
  783.   DBUG_RETURN(records ? test(quick) : -1);
  784. }
  785. /* make a select tree of all keys in condition */
  786. static SEL_TREE *get_mm_tree(PARAM *param,COND *cond)
  787. {
  788.   SEL_TREE *tree=0;
  789.   DBUG_ENTER("get_mm_tree");
  790.   if (cond->type() == Item::COND_ITEM)
  791.   {
  792.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  793.     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  794.     {
  795.       tree=0;
  796.       Item *item;
  797.       while ((item=li++))
  798.       {
  799. SEL_TREE *new_tree=get_mm_tree(param,item);
  800. if (param->thd->is_fatal_error)
  801.   DBUG_RETURN(0); // out of memory
  802. tree=tree_and(param,tree,new_tree);
  803. if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
  804.   break;
  805.       }
  806.     }
  807.     else
  808.     { // COND OR
  809.       tree=get_mm_tree(param,li++);
  810.       if (tree)
  811.       {
  812. Item *item;
  813. while ((item=li++))
  814. {
  815.   SEL_TREE *new_tree=get_mm_tree(param,item);
  816.   if (!new_tree)
  817.     DBUG_RETURN(0); // out of memory
  818.   tree=tree_or(param,tree,new_tree);
  819.   if (!tree || tree->type == SEL_TREE::ALWAYS)
  820.     break;
  821. }
  822.       }
  823.     }
  824.     DBUG_RETURN(tree);
  825.   }
  826.   /* Here when simple cond */
  827.   if (cond->const_item())
  828.   {
  829.     if (cond->val_int())
  830.       DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));
  831.     DBUG_RETURN(new SEL_TREE(SEL_TREE::IMPOSSIBLE));
  832.   }
  833.   table_map ref_tables=cond->used_tables();
  834.   if (cond->type() != Item::FUNC_ITEM)
  835.   { // Should be a field
  836.     if ((ref_tables & param->current_table) ||
  837. (ref_tables & ~(param->prev_tables | param->read_tables)))
  838.       DBUG_RETURN(0);
  839.     DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE));
  840.   }
  841.   Item_func *cond_func= (Item_func*) cond;
  842.   if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
  843.     DBUG_RETURN(0); // Can't be calculated
  844.   param->cond= cond;
  845.   if (cond_func->functype() == Item_func::BETWEEN)
  846.   {
  847.     if (!((Item_func_between *)(cond_func))->negated &&
  848.         cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  849.     {
  850.       Field *field=((Item_field*) (cond_func->arguments()[0]))->field;
  851.       Item_result cmp_type=field->cmp_type();
  852.       DBUG_RETURN(tree_and(param,
  853.    get_mm_parts(param, cond_func, field,
  854. Item_func::GE_FUNC,
  855. cond_func->arguments()[1], cmp_type),
  856.    get_mm_parts(param, cond_func, field,
  857. Item_func::LE_FUNC,
  858. cond_func->arguments()[2], cmp_type)));
  859.     }
  860.     DBUG_RETURN(0);
  861.   }
  862.   if (cond_func->functype() == Item_func::IN_FUNC)
  863.   { // COND OR
  864.     Item_func_in *func=(Item_func_in*) cond_func;
  865.     if (!func->negated && func->key_item()->type() == Item::FIELD_ITEM)
  866.     {
  867.       Field *field=((Item_field*) (func->key_item()))->field;
  868.       Item_result cmp_type=field->cmp_type();
  869.       tree= get_mm_parts(param,cond_func,field,Item_func::EQ_FUNC,
  870.  func->arguments()[1],cmp_type);
  871.       if (!tree)
  872. DBUG_RETURN(tree); // Not key field
  873.       for (uint i=2 ; i < func->argument_count(); i++)
  874.       {
  875. SEL_TREE *new_tree=get_mm_parts(param,cond_func,field,
  876. Item_func::EQ_FUNC,
  877. func->arguments()[i],cmp_type);
  878. tree=tree_or(param,tree,new_tree);
  879.       }
  880.       DBUG_RETURN(tree);
  881.     }
  882.     DBUG_RETURN(0); // Can't optimize this IN
  883.   }
  884.   if (ref_tables & ~(param->prev_tables | param->read_tables |
  885.      param->current_table))
  886.     DBUG_RETURN(0); // Can't be calculated yet
  887.   if (!(ref_tables & param->current_table))
  888.     DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE)); // This may be false or true
  889.   /* check field op const */
  890.   /* btw, ft_func's arguments()[0] isn't FIELD_ITEM.  SerG*/
  891.   if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  892.   {
  893.     tree= get_mm_parts(param, cond_func,
  894.        ((Item_field*) (cond_func->arguments()[0]))->field,
  895.        cond_func->functype(),
  896.        cond_func->arg_count > 1 ? cond_func->arguments()[1] :
  897.        0,
  898.        ((Item_field*) (cond_func->arguments()[0]))->field->
  899.        cmp_type());
  900.   }
  901.   /* check const op field */
  902.   if (!tree &&
  903.       cond_func->have_rev_func() &&
  904.       cond_func->arguments()[1]->type() == Item::FIELD_ITEM)
  905.   {
  906.     DBUG_RETURN(get_mm_parts(param, cond_func,
  907.      ((Item_field*)
  908.       (cond_func->arguments()[1]))->field,
  909.      ((Item_bool_func2*) cond_func)->rev_functype(),
  910.      cond_func->arguments()[0],
  911.      ((Item_field*)
  912.       (cond_func->arguments()[1]))->field->cmp_type()
  913.      ));
  914.   }
  915.   DBUG_RETURN(tree);
  916. }
  917. static SEL_TREE *
  918. get_mm_parts(PARAM *param, COND *cond_func, Field *field,
  919.      Item_func::Functype type, 
  920.      Item *value, Item_result cmp_type)
  921. {
  922.   bool ne_func= FALSE;
  923.   DBUG_ENTER("get_mm_parts");
  924.   if (field->table != param->table)
  925.     DBUG_RETURN(0);
  926.   if (type == Item_func::NE_FUNC)
  927.   {
  928.     ne_func= TRUE;
  929.     type= Item_func::LT_FUNC;
  930.   }
  931.   KEY_PART *key_part = param->key_parts;
  932.   KEY_PART *end = param->key_parts_end;
  933.   SEL_TREE *tree=0;
  934.   if (value &&
  935.       value->used_tables() & ~(param->prev_tables | param->read_tables))
  936.     DBUG_RETURN(0);
  937.   for (; key_part != end ; key_part++)
  938.   {
  939.     if (field->eq(key_part->field))
  940.     {
  941.       SEL_ARG *sel_arg=0;
  942.       if (!tree && !(tree=new SEL_TREE()))
  943. DBUG_RETURN(0); // OOM
  944.       if (!value || !(value->used_tables() & ~param->read_tables))
  945.       {
  946. sel_arg=get_mm_leaf(param,cond_func,
  947.     key_part->field,key_part,type,value);
  948. if (!sel_arg)
  949.   continue;
  950. if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
  951. {
  952.   tree->type=SEL_TREE::IMPOSSIBLE;
  953.           /* If this is an NE_FUNC, we still need to check GT_FUNC. */
  954.           if (!ne_func)
  955.             DBUG_RETURN(tree);
  956. }
  957.       }
  958.       else
  959.       {
  960. // This key may be used later
  961. if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY))) 
  962.   DBUG_RETURN(0); // OOM
  963.       }
  964.       sel_arg->part=(uchar) key_part->part;
  965.       tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
  966.     }
  967.   }
  968.   if (ne_func)
  969.   {
  970.     SEL_TREE *tree2= get_mm_parts(param, cond_func,
  971.   field, Item_func::GT_FUNC,
  972.                                   value, cmp_type);
  973.     /* tree_or() will return 0 if tree2 is 0 */
  974.     tree= tree_or(param,tree,tree2);
  975.   }
  976.   DBUG_RETURN(tree);
  977. }
  978. static SEL_ARG *
  979. get_mm_leaf(PARAM *param, COND *conf_func, Field *field, KEY_PART *key_part,
  980.     Item_func::Functype type,Item *value)
  981. {
  982.   uint maybe_null=(uint) field->real_maybe_null(), copies;
  983.   uint field_length=field->pack_length()+maybe_null;
  984.   SEL_ARG *tree;
  985.   char *str, *str2;
  986.   DBUG_ENTER("get_mm_leaf");
  987.   if (!value) // IS NULL or IS NOT NULL
  988.   {
  989.     if (field->table->outer_join) // Can't use a key on this
  990.       DBUG_RETURN(0);
  991.     if (!maybe_null) // Not null field
  992.       DBUG_RETURN(type == Item_func::ISNULL_FUNC ? &null_element : 0);
  993.     if (!(tree=new SEL_ARG(field,is_null_string,is_null_string)))
  994.       DBUG_RETURN(0); // out of memory
  995.     if (type == Item_func::ISNOTNULL_FUNC)
  996.     {
  997.       tree->min_flag=NEAR_MIN;     /* IS NOT NULL ->  X > NULL */
  998.       tree->max_flag=NO_MAX_RANGE;
  999.     }
  1000.     DBUG_RETURN(tree);
  1001.   }
  1002.   /*
  1003.     1. Usually we can't use an index if the column collation
  1004.        differ from the operation collation.
  1005.     2. However, we can reuse a case insensitive index for
  1006.        the binary searches:
  1007.        WHERE latin1_swedish_ci_column = 'a' COLLATE lati1_bin;
  1008.        WHERE latin1_swedish_ci_colimn = BINARY 'a '
  1009.   */
  1010.   if (field->result_type() == STRING_RESULT &&
  1011.       value->result_type() == STRING_RESULT &&
  1012.       key_part->image_type == Field::itRAW &&
  1013.       ((Field_str*)field)->charset() != conf_func->compare_collation() &&
  1014.       !(conf_func->compare_collation()->state & MY_CS_BINSORT))
  1015.     DBUG_RETURN(0);
  1016.   if (type == Item_func::LIKE_FUNC)
  1017.   {
  1018.     bool like_error;
  1019.     char buff1[MAX_FIELD_WIDTH],*min_str,*max_str;
  1020.     String tmp(buff1,sizeof(buff1),value->collation.collation),*res;
  1021.     uint length,offset,min_length,max_length;
  1022.     if (!field->optimize_range(param->real_keynr[key_part->key],
  1023.                                key_part->part))
  1024.       DBUG_RETURN(0); // Can't optimize this
  1025.     if (!(res= value->val_str(&tmp)))
  1026.       DBUG_RETURN(&null_element);
  1027.     /*
  1028.       TODO:
  1029.       Check if this was a function. This should have be optimized away
  1030.       in the sql_select.cc
  1031.     */
  1032.     if (res != &tmp)
  1033.     {
  1034.       tmp.copy(*res); // Get own copy
  1035.       res= &tmp;
  1036.     }
  1037.     if (field->cmp_type() != STRING_RESULT)
  1038.       DBUG_RETURN(0); // Can only optimize strings
  1039.     offset=maybe_null;
  1040.     length=key_part->store_length;
  1041.     if (length != key_part->length  + maybe_null)
  1042.     {
  1043.       /* key packed with length prefix */
  1044.       offset+= HA_KEY_BLOB_LENGTH;
  1045.       field_length= length - HA_KEY_BLOB_LENGTH;
  1046.     }
  1047.     else
  1048.     {
  1049.       if (unlikely(length < field_length))
  1050.       {
  1051. /*
  1052.   This can only happen in a table created with UNIREG where one key
  1053.   overlaps many fields
  1054. */
  1055. length= field_length;
  1056.       }
  1057.       else
  1058. field_length= length;
  1059.     }
  1060.     length+=offset;
  1061.     if (!(min_str= (char*) alloc_root(param->mem_root, length*2)))
  1062.       DBUG_RETURN(0);
  1063.     max_str=min_str+length;
  1064.     if (maybe_null)
  1065.       max_str[0]= min_str[0]=0;
  1066.     like_error= my_like_range(field->charset(),
  1067.       res->ptr(), res->length(),
  1068.       ((Item_func_like*)(param->cond))->escape,
  1069.       wild_one, wild_many,
  1070.       field_length-maybe_null,
  1071.       min_str+offset, max_str+offset,
  1072.       &min_length, &max_length);
  1073.     if (like_error) // Can't optimize with LIKE
  1074.       DBUG_RETURN(0);
  1075.     if (offset != maybe_null) // Blob
  1076.     {
  1077.       int2store(min_str+maybe_null,min_length);
  1078.       int2store(max_str+maybe_null,max_length);
  1079.     }
  1080.     DBUG_RETURN(new SEL_ARG(field,min_str,max_str));
  1081.   }
  1082.   if (!field->optimize_range(param->real_keynr[key_part->key],
  1083.                              key_part->part) &&
  1084.       type != Item_func::EQ_FUNC &&
  1085.       type != Item_func::EQUAL_FUNC)
  1086.     DBUG_RETURN(0); // Can't optimize this
  1087.   /*
  1088.     We can't always use indexes when comparing a string index to a number
  1089.     cmp_type() is checked to allow compare of dates to numbers
  1090.   */
  1091.   if (field->result_type() == STRING_RESULT &&
  1092.       value->result_type() != STRING_RESULT &&
  1093.       field->cmp_type() != value->result_type())
  1094.     DBUG_RETURN(0);
  1095.  
  1096.   if (value->save_in_field(field, 1) < 0)
  1097.   {
  1098.     /* This happens when we try to insert a NULL field in a not null column */
  1099.     DBUG_RETURN(&null_element); // cmp with NULL is never true
  1100.   }
  1101.   /* Get local copy of key */
  1102.   copies= 1;
  1103.   if (field->key_type() == HA_KEYTYPE_VARTEXT)
  1104.     copies= 2;
  1105.   str= str2= (char*) alloc_root(param->mem_root,
  1106. (key_part->store_length)*copies+1);
  1107.   if (!str)
  1108.     DBUG_RETURN(0);
  1109.   if (maybe_null)
  1110.     *str= (char) field->is_real_null(); // Set to 1 if null
  1111.   field->get_key_image(str+maybe_null, key_part->length,
  1112.        field->charset(), key_part->image_type);
  1113.   if (copies == 2)
  1114.   {
  1115.     /*
  1116.       The key is stored as 2 byte length + key
  1117.       key doesn't match end space. In other words, a key 'X ' should match
  1118.       all rows between 'X' and 'X           ...'
  1119.     */
  1120.     uint length= uint2korr(str+maybe_null);
  1121.     str2= str+ key_part->store_length;
  1122.     /* remove end space */
  1123.     while (length > 0 && str[length+HA_KEY_BLOB_LENGTH+maybe_null-1] == ' ')
  1124.       length--;
  1125.     int2store(str+maybe_null, length);
  1126.     /* Create key that is space filled */
  1127.     memcpy(str2, str, length + HA_KEY_BLOB_LENGTH + maybe_null);
  1128.     my_fill_8bit(field->charset(),
  1129.  str2+ length+ HA_KEY_BLOB_LENGTH +maybe_null,
  1130.  key_part->length-length, ' ');
  1131.     int2store(str2+maybe_null, key_part->length);
  1132.   }
  1133.   if (!(tree=new SEL_ARG(field,str,str2)))
  1134.     DBUG_RETURN(0); // out of memory
  1135.   /*
  1136.     Check if we are comparing an UNSIGNED integer with a negative constant.
  1137.     In this case we know that:
  1138.     (a) (unsigned_int [< | <=] negative_constant) == FALSE
  1139.     (b) (unsigned_int [> | >=] negative_constant) == TRUE
  1140.     In case (a) the condition is false for all values, and in case (b) it
  1141.     is true for all values, so we can avoid unnecessary retrieval and condition
  1142.     testing, and we also get correct comparison of unsinged integers with
  1143.     negative integers (which otherwise fails because at query execution time
  1144.     negative integers are cast to unsigned if compared with unsigned).
  1145.    */
  1146.   Item_result field_result_type= field->result_type();
  1147.   Item_result value_result_type= value->result_type();
  1148.   if (field_result_type == INT_RESULT && value_result_type == INT_RESULT &&
  1149.       ((Field_num*)field)->unsigned_flag && !((Item_int*)value)->unsigned_flag)
  1150.   {
  1151.     longlong item_val= value->val_int();
  1152.     if (item_val < 0)
  1153.     {
  1154.       if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
  1155.       {
  1156.         tree->type= SEL_ARG::IMPOSSIBLE;
  1157.         DBUG_RETURN(tree);
  1158.       }
  1159.       if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
  1160.         DBUG_RETURN(0);
  1161.     }
  1162.   }
  1163.   switch (type) {
  1164.   case Item_func::LT_FUNC:
  1165.     if (field_is_equal_to_item(field,value))
  1166.       tree->max_flag=NEAR_MAX;
  1167.     /* fall through */
  1168.   case Item_func::LE_FUNC:
  1169.     if (!maybe_null)
  1170.       tree->min_flag=NO_MIN_RANGE; /* From start */
  1171.     else
  1172.     { // > NULL
  1173.       tree->min_value=is_null_string;
  1174.       tree->min_flag=NEAR_MIN;
  1175.     }
  1176.     break;
  1177.   case Item_func::GT_FUNC:
  1178.     if (field_is_equal_to_item(field,value))
  1179.       tree->min_flag=NEAR_MIN;
  1180.     /* fall through */
  1181.   case Item_func::GE_FUNC:
  1182.     tree->max_flag=NO_MAX_RANGE;
  1183.     break;
  1184.   case Item_func::SP_EQUALS_FUNC:
  1185.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_EQUAL;// NEAR_MIN;//512;
  1186.     tree->max_flag=NO_MAX_RANGE;
  1187.     break;
  1188.   case Item_func::SP_DISJOINT_FUNC:
  1189.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_DISJOINT;// NEAR_MIN;//512;
  1190.     tree->max_flag=NO_MAX_RANGE;
  1191.     break;
  1192.   case Item_func::SP_INTERSECTS_FUNC:
  1193.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
  1194.     tree->max_flag=NO_MAX_RANGE;
  1195.     break;
  1196.   case Item_func::SP_TOUCHES_FUNC:
  1197.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
  1198.     tree->max_flag=NO_MAX_RANGE;
  1199.     break;
  1200.   case Item_func::SP_CROSSES_FUNC:
  1201.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
  1202.     tree->max_flag=NO_MAX_RANGE;
  1203.     break;
  1204.   case Item_func::SP_WITHIN_FUNC:
  1205.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_WITHIN;// NEAR_MIN;//512;
  1206.     tree->max_flag=NO_MAX_RANGE;
  1207.     break;
  1208.   case Item_func::SP_CONTAINS_FUNC:
  1209.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_CONTAIN;// NEAR_MIN;//512;
  1210.     tree->max_flag=NO_MAX_RANGE;
  1211.     break;
  1212.   case Item_func::SP_OVERLAPS_FUNC:
  1213.     tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
  1214.     tree->max_flag=NO_MAX_RANGE;
  1215.     break;
  1216.   default:
  1217.     break;
  1218.   }
  1219.   DBUG_RETURN(tree);
  1220. }
  1221. /******************************************************************************
  1222. ** Tree manipulation functions
  1223. ** If tree is 0 it means that the condition can't be tested. It refers
  1224. ** to a non existent table or to a field in current table with isn't a key.
  1225. ** The different tree flags:
  1226. ** IMPOSSIBLE:  Condition is never true
  1227. ** ALWAYS:  Condition is always true
  1228. ** MAYBE:  Condition may exists when tables are read
  1229. ** MAYBE_KEY:  Condition refers to a key that may be used in join loop
  1230. ** KEY_RANGE:  Condition uses a key
  1231. ******************************************************************************/
  1232. /*
  1233.   Add a new key test to a key when scanning through all keys
  1234.   This will never be called for same key parts.
  1235. */
  1236. static SEL_ARG *
  1237. sel_add(SEL_ARG *key1,SEL_ARG *key2)
  1238. {
  1239.   SEL_ARG *root,**key_link;
  1240.   if (!key1)
  1241.     return key2;
  1242.   if (!key2)
  1243.     return key1;
  1244.   key_link= &root;
  1245.   while (key1 && key2)
  1246.   {
  1247.     if (key1->part < key2->part)
  1248.     {
  1249.       *key_link= key1;
  1250.       key_link= &key1->next_key_part;
  1251.       key1=key1->next_key_part;
  1252.     }
  1253.     else
  1254.     {
  1255.       *key_link= key2;
  1256.       key_link= &key2->next_key_part;
  1257.       key2=key2->next_key_part;
  1258.     }
  1259.   }
  1260.   *key_link=key1 ? key1 : key2;
  1261.   return root;
  1262. }
  1263. #define CLONE_KEY1_MAYBE 1
  1264. #define CLONE_KEY2_MAYBE 2
  1265. #define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
  1266. static SEL_TREE *
  1267. tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
  1268. {
  1269.   DBUG_ENTER("tree_and");
  1270.   if (!tree1)
  1271.     DBUG_RETURN(tree2);
  1272.   if (!tree2)
  1273.     DBUG_RETURN(tree1);
  1274.   if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
  1275.     DBUG_RETURN(tree1);
  1276.   if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
  1277.     DBUG_RETURN(tree2);
  1278.   if (tree1->type == SEL_TREE::MAYBE)
  1279.   {
  1280.     if (tree2->type == SEL_TREE::KEY)
  1281.       tree2->type=SEL_TREE::KEY_SMALLER;
  1282.     DBUG_RETURN(tree2);
  1283.   }
  1284.   if (tree2->type == SEL_TREE::MAYBE)
  1285.   {
  1286.     tree1->type=SEL_TREE::KEY_SMALLER;
  1287.     DBUG_RETURN(tree1);
  1288.   }
  1289.   /* Join the trees key per key */
  1290.   SEL_ARG **key1,**key2,**end;
  1291.   for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
  1292.        key1 != end ; key1++,key2++)
  1293.   {
  1294.     uint flag=0;
  1295.     if (*key1 || *key2)
  1296.     {
  1297.       if (*key1 && !(*key1)->simple_key())
  1298. flag|=CLONE_KEY1_MAYBE;
  1299.       if (*key2 && !(*key2)->simple_key())
  1300. flag|=CLONE_KEY2_MAYBE;
  1301.       *key1=key_and(*key1,*key2,flag);
  1302.       if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
  1303.       {
  1304. tree1->type= SEL_TREE::IMPOSSIBLE;
  1305. #ifdef EXTRA_DEBUG
  1306.         (*key1)->test_use_count(*key1);
  1307. #endif
  1308. break;
  1309.       }
  1310.     }
  1311.   }
  1312.   DBUG_RETURN(tree1);
  1313. }
  1314. static SEL_TREE *
  1315. tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
  1316. {
  1317.   DBUG_ENTER("tree_or");
  1318.   if (!tree1 || !tree2)
  1319.     DBUG_RETURN(0);
  1320.   if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
  1321.     DBUG_RETURN(tree2);
  1322.   if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
  1323.     DBUG_RETURN(tree1);
  1324.   if (tree1->type == SEL_TREE::MAYBE)
  1325.     DBUG_RETURN(tree1); // Can't use this
  1326.   if (tree2->type == SEL_TREE::MAYBE)
  1327.     DBUG_RETURN(tree2);
  1328.   /* Join the trees key per key */
  1329.   SEL_ARG **key1,**key2,**end;
  1330.   SEL_TREE *result=0;
  1331.   for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
  1332.        key1 != end ; key1++,key2++)
  1333.   {
  1334.     *key1=key_or(*key1,*key2);
  1335.     if (*key1)
  1336.     {
  1337.       result=tree1; // Added to tree1
  1338. #ifdef EXTRA_DEBUG
  1339.       (*key1)->test_use_count(*key1);
  1340. #endif
  1341.     }
  1342.   }
  1343.   DBUG_RETURN(result);
  1344. }
  1345. /* And key trees where key1->part < key2 -> part */
  1346. static SEL_ARG *
  1347. and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
  1348. {
  1349.   SEL_ARG *next;
  1350.   ulong use_count=key1->use_count;
  1351.   if (key1->elements != 1)
  1352.   {
  1353.     key2->use_count+=key1->elements-1;
  1354.     key2->increment_use_count((int) key1->elements-1);
  1355.   }
  1356.   if (key1->type == SEL_ARG::MAYBE_KEY)
  1357.   {
  1358.     key1->right= key1->left= &null_element;
  1359.     key1->next= key1->prev= 0;
  1360.   }
  1361.   for (next=key1->first(); next ; next=next->next)
  1362.   {
  1363.     if (next->next_key_part)
  1364.     {
  1365.       SEL_ARG *tmp=key_and(next->next_key_part,key2,clone_flag);
  1366.       if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE)
  1367.       {
  1368. key1=key1->tree_delete(next);
  1369. continue;
  1370.       }
  1371.       next->next_key_part=tmp;
  1372.       if (use_count)
  1373. next->increment_use_count(use_count);
  1374.     }
  1375.     else
  1376.       next->next_key_part=key2;
  1377.   }
  1378.   if (!key1)
  1379.     return &null_element; // Impossible ranges
  1380.   key1->use_count++;
  1381.   return key1;
  1382. }
  1383. static SEL_ARG *
  1384. key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
  1385. {
  1386.   if (!key1)
  1387.     return key2;
  1388.   if (!key2)
  1389.     return key1;
  1390.   if (key1->part != key2->part)
  1391.   {
  1392.     if (key1->part > key2->part)
  1393.     {
  1394.       swap_variables(SEL_ARG *, key1, key2);
  1395.       clone_flag=swap_clone_flag(clone_flag);
  1396.     }
  1397.     // key1->part < key2->part
  1398.     key1->use_count--;
  1399.     if (key1->use_count > 0)
  1400.       if (!(key1= key1->clone_tree()))
  1401. return 0; // OOM
  1402.     return and_all_keys(key1,key2,clone_flag);
  1403.   }
  1404.   if (((clone_flag & CLONE_KEY2_MAYBE) &&
  1405.        !(clone_flag & CLONE_KEY1_MAYBE) &&
  1406.        key2->type != SEL_ARG::MAYBE_KEY) ||
  1407.       key1->type == SEL_ARG::MAYBE_KEY)
  1408.   { // Put simple key in key2
  1409.     swap_variables(SEL_ARG *, key1, key2);
  1410.     clone_flag=swap_clone_flag(clone_flag);
  1411.   }
  1412.   // If one of the key is MAYBE_KEY then the found region may be smaller
  1413.   if (key2->type == SEL_ARG::MAYBE_KEY)
  1414.   {
  1415.     if (key1->use_count > 1)
  1416.     {
  1417.       key1->use_count--;
  1418.       if (!(key1=key1->clone_tree()))
  1419. return 0; // OOM
  1420.       key1->use_count++;
  1421.     }
  1422.     if (key1->type == SEL_ARG::MAYBE_KEY)
  1423.     { // Both are maybe key
  1424.       key1->next_key_part=key_and(key1->next_key_part,key2->next_key_part,
  1425.  clone_flag);
  1426.       if (key1->next_key_part &&
  1427.   key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
  1428. return key1;
  1429.     }
  1430.     else
  1431.     {
  1432.       key1->maybe_smaller();
  1433.       if (key2->next_key_part)
  1434.       {
  1435. key1->use_count--; // Incremented in and_all_keys
  1436. return and_all_keys(key1,key2,clone_flag);
  1437.       }
  1438.       key2->use_count--; // Key2 doesn't have a tree
  1439.     }
  1440.     return key1;
  1441.   }
  1442.   if ((key1->min_flag | key2->min_flag) & GEOM_FLAG)
  1443.   {
  1444.     key1->free_tree();
  1445.     key2->free_tree();
  1446.     return 0; // Can't optimize this
  1447.   }
  1448.   key1->use_count--;
  1449.   key2->use_count--;
  1450.   SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;
  1451.   while (e1 && e2)
  1452.   {
  1453.     int cmp=e1->cmp_min_to_min(e2);
  1454.     if (cmp < 0)
  1455.     {
  1456.       if (get_range(&e1,&e2,key1))
  1457. continue;
  1458.     }
  1459.     else if (get_range(&e2,&e1,key2))
  1460.       continue;
  1461.     SEL_ARG *next=key_and(e1->next_key_part,e2->next_key_part,clone_flag);
  1462.     e1->increment_use_count(1);
  1463.     e2->increment_use_count(1);
  1464.     if (!next || next->type != SEL_ARG::IMPOSSIBLE)
  1465.     {
  1466.       SEL_ARG *new_arg= e1->clone_and(e2);
  1467.       if (!new_arg)
  1468. return &null_element; // End of memory
  1469.       new_arg->next_key_part=next;
  1470.       if (!new_tree)
  1471.       {
  1472. new_tree=new_arg;
  1473.       }
  1474.       else
  1475. new_tree=new_tree->insert(new_arg);
  1476.     }
  1477.     if (e1->cmp_max_to_max(e2) < 0)
  1478.       e1=e1->next; // e1 can't overlapp next e2
  1479.     else
  1480.       e2=e2->next;
  1481.   }
  1482.   key1->free_tree();
  1483.   key2->free_tree();
  1484.   if (!new_tree)
  1485.     return &null_element; // Impossible range
  1486.   return new_tree;
  1487. }
  1488. static bool
  1489. get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1)
  1490. {
  1491.   (*e1)=root1->find_range(*e2); // first e1->min < e2->min
  1492.   if ((*e1)->cmp_max_to_min(*e2) < 0)
  1493.   {
  1494.     if (!((*e1)=(*e1)->next))
  1495.       return 1;
  1496.     if ((*e1)->cmp_min_to_max(*e2) > 0)
  1497.     {
  1498.       (*e2)=(*e2)->next;
  1499.       return 1;
  1500.     }
  1501.   }
  1502.   return 0;
  1503. }
  1504. static SEL_ARG *
  1505. key_or(SEL_ARG *key1,SEL_ARG *key2)
  1506. {
  1507.   if (!key1)
  1508.   {
  1509.     if (key2)
  1510.     {
  1511.       key2->use_count--;
  1512.       key2->free_tree();
  1513.     }
  1514.     return 0;
  1515.   }
  1516.   if (!key2)
  1517.   {
  1518.     key1->use_count--;
  1519.     key1->free_tree();
  1520.     return 0;
  1521.   }
  1522.   key1->use_count--;
  1523.   key2->use_count--;
  1524.   if (key1->part != key2->part || 
  1525.       (key1->min_flag | key2->min_flag) & GEOM_FLAG)
  1526.   {
  1527.     key1->free_tree();
  1528.     key2->free_tree();
  1529.     return 0; // Can't optimize this
  1530.   }
  1531.   // If one of the key is MAYBE_KEY then the found region may be bigger
  1532.   if (key1->type == SEL_ARG::MAYBE_KEY)
  1533.   {
  1534.     key2->free_tree();
  1535.     key1->use_count++;
  1536.     return key1;
  1537.   }
  1538.   if (key2->type == SEL_ARG::MAYBE_KEY)
  1539.   {
  1540.     key1->free_tree();
  1541.     key2->use_count++;
  1542.     return key2;
  1543.   }
  1544.   if (key1->use_count > 0)
  1545.   {
  1546.     if (key2->use_count == 0 || key1->elements > key2->elements)
  1547.     {
  1548.       swap_variables(SEL_ARG *,key1,key2);
  1549.     }
  1550.     if (key1->use_count > 0 || !(key1=key1->clone_tree()))
  1551.       return 0; // OOM
  1552.   }
  1553.   // Add tree at key2 to tree at key1
  1554.   bool key2_shared=key2->use_count != 0;
  1555.   key1->maybe_flag|=key2->maybe_flag;
  1556.   for (key2=key2->first(); key2; )
  1557.   {
  1558.     SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
  1559.     int cmp;
  1560.     if (!tmp)
  1561.     {
  1562.       tmp=key1->first(); // tmp.min > key2.min
  1563.       cmp= -1;
  1564.     }
  1565.     else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
  1566.     { // Found tmp.max < key2.min
  1567.       SEL_ARG *next=tmp->next;
  1568.       if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
  1569.       {
  1570. // Join near ranges like tmp.max < 0 and key2.min >= 0
  1571. SEL_ARG *key2_next=key2->next;
  1572. if (key2_shared)
  1573. {
  1574.   if (!(key2=new SEL_ARG(*key2)))
  1575.     return 0; // out of memory
  1576.   key2->increment_use_count(key1->use_count+1);
  1577.   key2->next=key2_next; // New copy of key2
  1578. }
  1579. key2->copy_min(tmp);
  1580. if (!(key1=key1->tree_delete(tmp)))
  1581. { // Only one key in tree
  1582.   key1=key2;
  1583.   key1->make_root();
  1584.   key2=key2_next;
  1585.   break;
  1586. }
  1587.       }
  1588.       if (!(tmp=next)) // tmp.min > key2.min
  1589. break; // Copy rest of key2
  1590.     }
  1591.     if (cmp < 0)
  1592.     { // tmp.min > key2.min
  1593.       int tmp_cmp;
  1594.       if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
  1595.       {
  1596. if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
  1597. { // ranges are connected
  1598.   tmp->copy_min_to_min(key2);
  1599.   key1->merge_flags(key2);
  1600.   if (tmp->min_flag & NO_MIN_RANGE &&
  1601.       tmp->max_flag & NO_MAX_RANGE)
  1602.   {
  1603.     if (key1->maybe_flag)
  1604.       return new SEL_ARG(SEL_ARG::MAYBE_KEY);
  1605.     return 0;
  1606.   }
  1607.   key2->increment_use_count(-1); // Free not used tree
  1608.   key2=key2->next;
  1609.   continue;
  1610. }
  1611. else
  1612. {
  1613.   SEL_ARG *next=key2->next; // Keys are not overlapping
  1614.   if (key2_shared)
  1615.   {
  1616.     SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
  1617.     if (!cpy)
  1618.       return 0; // OOM
  1619.     key1=key1->insert(cpy);
  1620.     key2->increment_use_count(key1->use_count+1);
  1621.   }
  1622.   else
  1623.     key1=key1->insert(key2); // Will destroy key2_root
  1624.   key2=next;
  1625.   continue;
  1626. }
  1627.       }
  1628.     }
  1629.     // tmp.max >= key2.min && tmp.min <= key.max  (overlapping ranges)
  1630.     if (eq_tree(tmp->next_key_part,key2->next_key_part))
  1631.     {
  1632.       if (tmp->is_same(key2))
  1633.       {
  1634. tmp->merge_flags(key2); // Copy maybe flags
  1635. key2->increment_use_count(-1); // Free not used tree
  1636.       }
  1637.       else
  1638.       {
  1639. SEL_ARG *last=tmp;
  1640. while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
  1641.        eq_tree(last->next->next_key_part,key2->next_key_part))
  1642. {
  1643.   SEL_ARG *save=last;
  1644.   last=last->next;
  1645.   key1=key1->tree_delete(save);
  1646. }
  1647.         last->copy_min(tmp);
  1648. if (last->copy_min(key2) || last->copy_max(key2))
  1649. { // Full range
  1650.   key1->free_tree();
  1651.   for (; key2 ; key2=key2->next)
  1652.     key2->increment_use_count(-1); // Free not used tree
  1653.   if (key1->maybe_flag)
  1654.     return new SEL_ARG(SEL_ARG::MAYBE_KEY);
  1655.   return 0;
  1656. }
  1657.       }
  1658.       key2=key2->next;
  1659.       continue;
  1660.     }
  1661.     if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
  1662.     { // tmp.min <= x < key2.min
  1663.       SEL_ARG *new_arg=tmp->clone_first(key2);
  1664.       if (!new_arg)
  1665. return 0; // OOM
  1666.       if ((new_arg->next_key_part= key1->next_key_part))
  1667. new_arg->increment_use_count(key1->use_count+1);
  1668.       tmp->copy_min_to_min(key2);
  1669.       key1=key1->insert(new_arg);
  1670.     }
  1671.     // tmp.min >= key2.min && tmp.min <= key2.max
  1672.     SEL_ARG key(*key2); // Get copy we can modify
  1673.     for (;;)
  1674.     {
  1675.       if (tmp->cmp_min_to_min(&key) > 0)
  1676.       { // key.min <= x < tmp.min
  1677. SEL_ARG *new_arg=key.clone_first(tmp);
  1678. if (!new_arg)
  1679.   return 0; // OOM
  1680. if ((new_arg->next_key_part=key.next_key_part))
  1681.   new_arg->increment_use_count(key1->use_count+1);
  1682. key1=key1->insert(new_arg);
  1683.       }
  1684.       if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
  1685.       { // tmp.min. <= x <= tmp.max
  1686. tmp->maybe_flag|= key.maybe_flag;
  1687. key.increment_use_count(key1->use_count+1);
  1688. tmp->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
  1689. if (!cmp) // Key2 is ready
  1690.   break;
  1691. key.copy_max_to_min(tmp);
  1692. if (!(tmp=tmp->next))
  1693. {
  1694.   SEL_ARG *tmp2= new SEL_ARG(key);
  1695.   if (!tmp2)
  1696.     return 0; // OOM
  1697.   key1=key1->insert(tmp2);
  1698.   key2=key2->next;
  1699.   goto end;
  1700. }
  1701. if (tmp->cmp_min_to_max(&key) > 0)
  1702. {
  1703.   SEL_ARG *tmp2= new SEL_ARG(key);
  1704.   if (!tmp2)
  1705.     return 0; // OOM
  1706.   key1=key1->insert(tmp2);
  1707.   break;
  1708. }
  1709.       }
  1710.       else
  1711.       {
  1712. SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
  1713. if (!new_arg)
  1714.   return 0; // OOM
  1715. tmp->copy_max_to_min(&key);
  1716. tmp->increment_use_count(key1->use_count+1);
  1717. /* Increment key count as it may be used for next loop */
  1718. key.increment_use_count(1);
  1719. new_arg->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
  1720. key1=key1->insert(new_arg);
  1721. break;
  1722.       }
  1723.     }
  1724.     key2=key2->next;
  1725.   }
  1726. end:
  1727.   while (key2)
  1728.   {
  1729.     SEL_ARG *next=key2->next;
  1730.     if (key2_shared)
  1731.     {
  1732.       SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
  1733.       if (!tmp)
  1734. return 0;
  1735.       key2->increment_use_count(key1->use_count+1);
  1736.       key1=key1->insert(tmp);
  1737.     }
  1738.     else
  1739.       key1=key1->insert(key2); // Will destroy key2_root
  1740.     key2=next;
  1741.   }
  1742.   key1->use_count++;
  1743.   return key1;
  1744. }
  1745. /* Compare if two trees are equal */
  1746. static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
  1747. {
  1748.   if (a == b)
  1749.     return 1;
  1750.   if (!a || !b || !a->is_same(b))
  1751.     return 0;
  1752.   if (a->left != &null_element && b->left != &null_element)
  1753.   {
  1754.     if (!eq_tree(a->left,b->left))
  1755.       return 0;
  1756.   }
  1757.   else if (a->left != &null_element || b->left != &null_element)
  1758.     return 0;
  1759.   if (a->right != &null_element && b->right != &null_element)
  1760.   {
  1761.     if (!eq_tree(a->right,b->right))
  1762.       return 0;
  1763.   }
  1764.   else if (a->right != &null_element || b->right != &null_element)
  1765.     return 0;
  1766.   if (a->next_key_part != b->next_key_part)
  1767.   { // Sub range
  1768.     if (!a->next_key_part != !b->next_key_part ||
  1769. !eq_tree(a->next_key_part, b->next_key_part))
  1770.       return 0;
  1771.   }
  1772.   return 1;
  1773. }
  1774. SEL_ARG *
  1775. SEL_ARG::insert(SEL_ARG *key)
  1776. {
  1777.   SEL_ARG *element,**par,*last_element;
  1778.   LINT_INIT(par); LINT_INIT(last_element);
  1779.   for (element= this; element != &null_element ; )
  1780.   {
  1781.     last_element=element;
  1782.     if (key->cmp_min_to_min(element) > 0)
  1783.     {
  1784.       par= &element->right; element= element->right;
  1785.     }
  1786.     else
  1787.     {
  1788.       par = &element->left; element= element->left;
  1789.     }
  1790.   }
  1791.   *par=key;
  1792.   key->parent=last_element;
  1793. /* Link in list */
  1794.   if (par == &last_element->left)
  1795.   {
  1796.     key->next=last_element;
  1797.     if ((key->prev=last_element->prev))
  1798.       key->prev->next=key;
  1799.     last_element->prev=key;
  1800.   }
  1801.   else
  1802.   {
  1803.     if ((key->next=last_element->next))
  1804.       key->next->prev=key;
  1805.     key->prev=last_element;
  1806.     last_element->next=key;
  1807.   }
  1808.   key->left=key->right= &null_element;
  1809.   SEL_ARG *root=rb_insert(key); // rebalance tree
  1810.   root->use_count=this->use_count; // copy root info
  1811.   root->elements= this->elements+1;
  1812.   root->maybe_flag=this->maybe_flag;
  1813.   return root;
  1814. }
  1815. /*
  1816. ** Find best key with min <= given key
  1817. ** Because the call context this should never return 0 to get_range
  1818. */
  1819. SEL_ARG *
  1820. SEL_ARG::find_range(SEL_ARG *key)
  1821. {
  1822.   SEL_ARG *element=this,*found=0;
  1823.   for (;;)
  1824.   {
  1825.     if (element == &null_element)
  1826.       return found;
  1827.     int cmp=element->cmp_min_to_min(key);
  1828.     if (cmp == 0)
  1829.       return element;
  1830.     if (cmp < 0)
  1831.     {
  1832.       found=element;
  1833.       element=element->right;
  1834.     }
  1835.     else
  1836.       element=element->left;
  1837.   }
  1838. }
  1839. /*
  1840.   Remove a element from the tree
  1841.   SYNOPSIS
  1842.     tree_delete()
  1843.     key Key that is to be deleted from tree (this)
  1844.     
  1845.   NOTE
  1846.     This also frees all sub trees that is used by the element
  1847.   RETURN
  1848.     root of new tree (with key deleted)
  1849. */
  1850. SEL_ARG *
  1851. SEL_ARG::tree_delete(SEL_ARG *key)
  1852. {
  1853.   enum leaf_color remove_color;
  1854.   SEL_ARG *root,*nod,**par,*fix_par;
  1855.   DBUG_ENTER("tree_delete");
  1856.   root=this;
  1857.   this->parent= 0;
  1858.   /* Unlink from list */
  1859.   if (key->prev)
  1860.     key->prev->next=key->next;
  1861.   if (key->next)
  1862.     key->next->prev=key->prev;
  1863.   key->increment_use_count(-1);
  1864.   if (!key->parent)
  1865.     par= &root;
  1866.   else
  1867.     par=key->parent_ptr();
  1868.   if (key->left == &null_element)
  1869.   {
  1870.     *par=nod=key->right;
  1871.     fix_par=key->parent;
  1872.     if (nod != &null_element)
  1873.       nod->parent=fix_par;
  1874.     remove_color= key->color;
  1875.   }
  1876.   else if (key->right == &null_element)
  1877.   {
  1878.     *par= nod=key->left;
  1879.     nod->parent=fix_par=key->parent;
  1880.     remove_color= key->color;
  1881.   }
  1882.   else
  1883.   {
  1884.     SEL_ARG *tmp=key->next; // next bigger key (exist!)
  1885.     nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
  1886.     fix_par=tmp->parent;
  1887.     if (nod != &null_element)
  1888.       nod->parent=fix_par;
  1889.     remove_color= tmp->color;
  1890.     tmp->parent=key->parent; // Move node in place of key
  1891.     (tmp->left=key->left)->parent=tmp;
  1892.     if ((tmp->right=key->right) != &null_element)
  1893.       tmp->right->parent=tmp;
  1894.     tmp->color=key->color;
  1895.     *par=tmp;
  1896.     if (fix_par == key) // key->right == key->next
  1897.       fix_par=tmp; // new parent of nod
  1898.   }
  1899.   if (root == &null_element)
  1900.     DBUG_RETURN(0); // Maybe root later
  1901.   if (remove_color == BLACK)
  1902.     root=rb_delete_fixup(root,nod,fix_par);
  1903.   test_rb_tree(root,root->parent);
  1904.   root->use_count=this->use_count; // Fix root counters
  1905.   root->elements=this->elements-1;
  1906.   root->maybe_flag=this->maybe_flag;
  1907.   DBUG_RETURN(root);
  1908. }
  1909. /* Functions to fix up the tree after insert and delete */
  1910. static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
  1911. {
  1912.   SEL_ARG *y=leaf->right;
  1913.   leaf->right=y->left;
  1914.   if (y->left != &null_element)
  1915.     y->left->parent=leaf;
  1916.   if (!(y->parent=leaf->parent))
  1917.     *root=y;
  1918.   else
  1919.     *leaf->parent_ptr()=y;
  1920.   y->left=leaf;
  1921.   leaf->parent=y;
  1922. }
  1923. static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
  1924. {
  1925.   SEL_ARG *y=leaf->left;
  1926.   leaf->left=y->right;
  1927.   if (y->right != &null_element)
  1928.     y->right->parent=leaf;
  1929.   if (!(y->parent=leaf->parent))
  1930.     *root=y;
  1931.   else
  1932.     *leaf->parent_ptr()=y;
  1933.   y->right=leaf;
  1934.   leaf->parent=y;
  1935. }
  1936. SEL_ARG *
  1937. SEL_ARG::rb_insert(SEL_ARG *leaf)
  1938. {
  1939.   SEL_ARG *y,*par,*par2,*root;
  1940.   root= this; root->parent= 0;
  1941.   leaf->color=RED;
  1942.   while (leaf != root && (par= leaf->parent)->color == RED)
  1943.   { // This can't be root or 1 level under
  1944.     if (par == (par2= leaf->parent->parent)->left)
  1945.     {
  1946.       y= par2->right;
  1947.       if (y->color == RED)
  1948.       {
  1949. par->color=BLACK;
  1950. y->color=BLACK;
  1951. leaf=par2;
  1952. leaf->color=RED; /* And the loop continues */
  1953.       }
  1954.       else
  1955.       {
  1956. if (leaf == par->right)
  1957. {
  1958.   left_rotate(&root,leaf->parent);
  1959.   par=leaf; /* leaf is now parent to old leaf */
  1960. }
  1961. par->color=BLACK;
  1962. par2->color=RED;
  1963. right_rotate(&root,par2);
  1964. break;
  1965.       }
  1966.     }
  1967.     else
  1968.     {
  1969.       y= par2->left;
  1970.       if (y->color == RED)
  1971.       {
  1972. par->color=BLACK;
  1973. y->color=BLACK;
  1974. leaf=par2;
  1975. leaf->color=RED; /* And the loop continues */
  1976.       }
  1977.       else
  1978.       {
  1979. if (leaf == par->left)
  1980. {
  1981.   right_rotate(&root,par);
  1982.   par=leaf;
  1983. }
  1984. par->color=BLACK;
  1985. par2->color=RED;
  1986. left_rotate(&root,par2);
  1987. break;
  1988.       }
  1989.     }
  1990.   }
  1991.   root->color=BLACK;
  1992.   test_rb_tree(root,root->parent);
  1993.   return root;
  1994. }
  1995. SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
  1996. {
  1997.   SEL_ARG *x,*w;
  1998.   root->parent=0;
  1999.   x= key;
  2000.   while (x != root && x->color == SEL_ARG::BLACK)
  2001.   {
  2002.     if (x == par->left)
  2003.     {
  2004.       w=par->right;
  2005.       if (w->color == SEL_ARG::RED)
  2006.       {
  2007. w->color=SEL_ARG::BLACK;
  2008. par->color=SEL_ARG::RED;
  2009. left_rotate(&root,par);
  2010. w=par->right;
  2011.       }
  2012.       if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
  2013.       {
  2014. w->color=SEL_ARG::RED;
  2015. x=par;
  2016.       }
  2017.       else
  2018.       {
  2019. if (w->right->color == SEL_ARG::BLACK)
  2020. {
  2021.   w->left->color=SEL_ARG::BLACK;
  2022.   w->color=SEL_ARG::RED;
  2023.   right_rotate(&root,w);
  2024.   w=par->right;
  2025. }
  2026. w->color=par->color;
  2027. par->color=SEL_ARG::BLACK;
  2028. w->right->color=SEL_ARG::BLACK;
  2029. left_rotate(&root,par);
  2030. x=root;
  2031. break;
  2032.       }
  2033.     }
  2034.     else
  2035.     {
  2036.       w=par->left;
  2037.       if (w->color == SEL_ARG::RED)
  2038.       {
  2039. w->color=SEL_ARG::BLACK;
  2040. par->color=SEL_ARG::RED;
  2041. right_rotate(&root,par);
  2042. w=par->left;
  2043.       }
  2044.       if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
  2045.       {
  2046. w->color=SEL_ARG::RED;
  2047. x=par;
  2048.       }
  2049.       else
  2050.       {
  2051. if (w->left->color == SEL_ARG::BLACK)
  2052. {
  2053.   w->right->color=SEL_ARG::BLACK;
  2054.   w->color=SEL_ARG::RED;
  2055.   left_rotate(&root,w);
  2056.   w=par->left;
  2057. }
  2058. w->color=par->color;
  2059. par->color=SEL_ARG::BLACK;
  2060. w->left->color=SEL_ARG::BLACK;
  2061. right_rotate(&root,par);
  2062. x=root;
  2063. break;
  2064.       }
  2065.     }
  2066.     par=x->parent;
  2067.   }
  2068.   x->color=SEL_ARG::BLACK;
  2069.   return root;
  2070. }
  2071. /* Test that the proporties for a red-black tree holds */
  2072. #ifdef EXTRA_DEBUG
  2073. int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
  2074. {
  2075.   int count_l,count_r;
  2076.   if (element == &null_element)
  2077.     return 0; // Found end of tree
  2078.   if (element->parent != parent)
  2079.   {
  2080.     sql_print_error("Wrong tree: Parent doesn't point at parent");
  2081.     return -1;
  2082.   }
  2083.   if (element->color == SEL_ARG::RED &&
  2084.       (element->left->color == SEL_ARG::RED ||
  2085.        element->right->color == SEL_ARG::RED))
  2086.   {
  2087.     sql_print_error("Wrong tree: Found two red in a row");
  2088.     return -1;
  2089.   }
  2090.   if (element->left == element->right && element->left != &null_element)
  2091.   { // Dummy test
  2092.     sql_print_error("Wrong tree: Found right == left");
  2093.     return -1;
  2094.   }
  2095.   count_l=test_rb_tree(element->left,element);
  2096.   count_r=test_rb_tree(element->right,element);
  2097.   if (count_l >= 0 && count_r >= 0)
  2098.   {
  2099.     if (count_l == count_r)
  2100.       return count_l+(element->color == SEL_ARG::BLACK);
  2101.     sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
  2102.     count_l,count_r);
  2103.   }
  2104.   return -1; // Error, no more warnings
  2105. }
  2106. static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
  2107. {
  2108.   ulong count= 0;
  2109.   for (root=root->first(); root ; root=root->next)
  2110.   {
  2111.     if (root->next_key_part)
  2112.     {
  2113.       if (root->next_key_part == key)
  2114. count++;
  2115.       if (root->next_key_part->part < key->part)
  2116. count+=count_key_part_usage(root->next_key_part,key);
  2117.     }
  2118.   }
  2119.   return count;
  2120. }
  2121. void SEL_ARG::test_use_count(SEL_ARG *root)
  2122. {
  2123.   uint e_count=0;
  2124.   if (this == root && use_count != 1)
  2125.   {
  2126.     sql_print_information("Use_count: Wrong count %lu for root",use_count);
  2127.     return;
  2128.   }
  2129.   if (this->type != SEL_ARG::KEY_RANGE)
  2130.     return;
  2131.   for (SEL_ARG *pos=first(); pos ; pos=pos->next)
  2132.   {
  2133.     e_count++;
  2134.     if (pos->next_key_part)
  2135.     {
  2136.       ulong count=count_key_part_usage(root,pos->next_key_part);
  2137.       if (count > pos->next_key_part->use_count)
  2138.       {
  2139. sql_print_information("Use_count: Wrong count for key at %lx, %lu should be %lu",
  2140. pos,pos->next_key_part->use_count,count);
  2141. return;
  2142.       }
  2143.       pos->next_key_part->test_use_count(root);
  2144.     }
  2145.   }
  2146.   if (e_count != elements)
  2147.     sql_print_warning("Wrong use count: %u (should be %u) for tree at %lx",
  2148.     e_count, elements, (gptr) this);
  2149. }
  2150. #endif
  2151. /*****************************************************************************
  2152. ** Check how many records we will find by using the found tree
  2153. *****************************************************************************/
  2154. static ha_rows
  2155. check_quick_select(PARAM *param,uint idx,SEL_ARG *tree)
  2156. {
  2157.   ha_rows records;
  2158.   DBUG_ENTER("check_quick_select");
  2159.   if (!tree)
  2160.     DBUG_RETURN(HA_POS_ERROR); // Can't use it
  2161.   param->max_key_part=0;
  2162.   param->range_count=0;
  2163.   if (tree->type == SEL_ARG::IMPOSSIBLE)
  2164.     DBUG_RETURN(0L); // Impossible select. return
  2165.   if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
  2166.     DBUG_RETURN(HA_POS_ERROR); // Don't use tree
  2167.   records=check_quick_keys(param,idx,tree,param->min_key,0,param->max_key,0);
  2168.   if (records != HA_POS_ERROR)
  2169.   {
  2170.     uint key=param->real_keynr[idx];
  2171.     param->table->quick_keys.set_bit(key);
  2172.     param->table->quick_rows[key]=records;
  2173.     param->table->quick_key_parts[key]=param->max_key_part+1;
  2174.   }
  2175.   DBUG_PRINT("exit", ("Records: %lu", (ulong) records));
  2176.   DBUG_RETURN(records);
  2177. }
  2178. static ha_rows
  2179. check_quick_keys(PARAM *param,uint idx,SEL_ARG *key_tree,
  2180.  char *min_key,uint min_key_flag, char *max_key,
  2181.  uint max_key_flag)
  2182. {
  2183.   ha_rows records=0,tmp;
  2184.   param->max_key_part=max(param->max_key_part,key_tree->part);
  2185.   if (key_tree->left != &null_element)
  2186.   {
  2187.     records=check_quick_keys(param,idx,key_tree->left,min_key,min_key_flag,
  2188.      max_key,max_key_flag);
  2189.     if (records == HA_POS_ERROR) // Impossible
  2190.       return records;
  2191.   }
  2192.   uint tmp_min_flag,tmp_max_flag,keynr;
  2193.   char *tmp_min_key=min_key,*tmp_max_key=max_key;
  2194.   key_tree->store(param->key[idx][key_tree->part].store_length,
  2195.   &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);
  2196.   uint min_key_length= (uint) (tmp_min_key- param->min_key);
  2197.   uint max_key_length= (uint) (tmp_max_key- param->max_key);
  2198.   if (key_tree->next_key_part &&
  2199.       key_tree->next_key_part->part == key_tree->part+1 &&
  2200.       key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  2201.   { // const key as prefix
  2202.     if (min_key_length == max_key_length &&
  2203. !memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) &&
  2204. !key_tree->min_flag && !key_tree->max_flag)
  2205.     {
  2206.       tmp=check_quick_keys(param,idx,key_tree->next_key_part,
  2207.    tmp_min_key, min_key_flag | key_tree->min_flag,
  2208.    tmp_max_key, max_key_flag | key_tree->max_flag);
  2209.       goto end; // Ugly, but efficient
  2210.     }
  2211.     tmp_min_flag=key_tree->min_flag;
  2212.     tmp_max_flag=key_tree->max_flag;
  2213.     if (!tmp_min_flag)
  2214.       key_tree->next_key_part->store_min_key(param->key[idx], &tmp_min_key,
  2215.      &tmp_min_flag);
  2216.     if (!tmp_max_flag)
  2217.       key_tree->next_key_part->store_max_key(param->key[idx], &tmp_max_key,
  2218.      &tmp_max_flag);
  2219.     min_key_length= (uint) (tmp_min_key- param->min_key);
  2220.     max_key_length= (uint) (tmp_max_key- param->max_key);
  2221.   }
  2222.   else
  2223.   {
  2224.     tmp_min_flag=min_key_flag | key_tree->min_flag;
  2225.     tmp_max_flag=max_key_flag | key_tree->max_flag;
  2226.   }
  2227.   keynr=param->real_keynr[idx];
  2228.   param->range_count++;
  2229.   if (!tmp_min_flag && ! tmp_max_flag &&
  2230.       (uint) key_tree->part+1 == param->table->key_info[keynr].key_parts &&
  2231.       (param->table->key_info[keynr].flags & (HA_NOSAME | HA_END_SPACE_KEY)) ==
  2232.       HA_NOSAME &&
  2233.       min_key_length == max_key_length &&
  2234.       !memcmp(param->min_key,param->max_key,min_key_length))
  2235.     tmp=1; // Max one record
  2236.   else
  2237.   {
  2238.     if (tmp_min_flag & GEOM_FLAG)
  2239.     {
  2240.       key_range min_range;
  2241.       min_range.key=    (byte*) param->min_key;
  2242.       min_range.length= min_key_length;
  2243.       /* In this case tmp_min_flag contains the handler-read-function */
  2244.       min_range.flag=   (ha_rkey_function) (tmp_min_flag ^ GEOM_FLAG);
  2245.       tmp= param->table->file->records_in_range(keynr, &min_range,
  2246.                                                 (key_range*) 0);
  2247.     }
  2248.     else
  2249.     {
  2250.       key_range min_range, max_range;
  2251.       min_range.key=    (byte*) param->min_key;
  2252.       min_range.length= min_key_length;
  2253.       min_range.flag=   (tmp_min_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
  2254.                          HA_READ_KEY_EXACT);
  2255.       max_range.key=    (byte*) param->max_key;
  2256.       max_range.length= max_key_length;
  2257.       max_range.flag=   (tmp_max_flag & NEAR_MAX ?
  2258.                          HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY);
  2259.       tmp=param->table->file->records_in_range(keynr,
  2260.                                                (min_key_length ? &min_range :
  2261.                                                 (key_range*) 0),
  2262.                                                (max_key_length ? &max_range :
  2263.                                                 (key_range*) 0));
  2264.     }
  2265.   }
  2266.  end:
  2267.   if (tmp == HA_POS_ERROR) // Impossible range
  2268.     return tmp;
  2269.   records+=tmp;
  2270.   if (key_tree->right != &null_element)
  2271.   {
  2272.     tmp=check_quick_keys(param,idx,key_tree->right,min_key,min_key_flag,
  2273.  max_key,max_key_flag);
  2274.     if (tmp == HA_POS_ERROR)
  2275.       return tmp;
  2276.     records+=tmp;
  2277.   }
  2278.   return records;
  2279. }
  2280. /****************************************************************************
  2281. ** change a tree to a structure to be used by quick_select
  2282. ** This uses it's own malloc tree
  2283. ****************************************************************************/
  2284. static QUICK_SELECT *
  2285. get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree)
  2286. {
  2287.   QUICK_SELECT *quick;
  2288.   DBUG_ENTER("get_quick_select");
  2289.   if (param->table->key_info[param->real_keynr[idx]].flags & HA_SPATIAL)
  2290.     quick=new QUICK_SELECT_GEOM(param->thd, param->table, param->real_keynr[idx],
  2291. 0);
  2292.   else
  2293.     quick=new QUICK_SELECT(param->thd, param->table, param->real_keynr[idx]);
  2294.   if (quick)
  2295.   {
  2296.     if (quick->error ||
  2297. get_quick_keys(param,quick,param->key[idx],key_tree,param->min_key,0,
  2298.        param->max_key,0))
  2299.     {
  2300.       delete quick;
  2301.       quick=0;
  2302.     }
  2303.     else
  2304.     {
  2305.       quick->key_parts=(KEY_PART*)
  2306. memdup_root(&quick->alloc,(char*) param->key[idx],
  2307.    sizeof(KEY_PART)*
  2308.    param->table->key_info[param->real_keynr[idx]].key_parts);
  2309.     }
  2310.   }
  2311.   DBUG_RETURN(quick);
  2312. }
  2313. /*
  2314. ** Fix this to get all possible sub_ranges
  2315. */
  2316. static bool
  2317. get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
  2318.        SEL_ARG *key_tree,char *min_key,uint min_key_flag,
  2319.        char *max_key, uint max_key_flag)
  2320. {
  2321.   QUICK_RANGE *range;
  2322.   uint flag;
  2323.   if (key_tree->left != &null_element)
  2324.   {
  2325.     if (get_quick_keys(param,quick,key,key_tree->left,
  2326.        min_key,min_key_flag, max_key, max_key_flag))
  2327.       return 1;
  2328.   }
  2329.   char *tmp_min_key=min_key,*tmp_max_key=max_key;
  2330.   key_tree->store(key[key_tree->part].store_length,
  2331.   &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);
  2332.   if (key_tree->next_key_part &&
  2333.       key_tree->next_key_part->part == key_tree->part+1 &&
  2334.       key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  2335.   {   // const key as prefix
  2336.     if (!((tmp_min_key - min_key) != (tmp_max_key - max_key) ||
  2337.   memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) ||
  2338.   key_tree->min_flag || key_tree->max_flag))
  2339.     {
  2340.       if (get_quick_keys(param,quick,key,key_tree->next_key_part,
  2341.  tmp_min_key, min_key_flag | key_tree->min_flag,
  2342.  tmp_max_key, max_key_flag | key_tree->max_flag))
  2343. return 1;
  2344.       goto end; // Ugly, but efficient
  2345.     }
  2346.     {
  2347.       uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
  2348.       if (!tmp_min_flag)
  2349. key_tree->next_key_part->store_min_key(key, &tmp_min_key,
  2350.        &tmp_min_flag);
  2351.       if (!tmp_max_flag)
  2352. key_tree->next_key_part->store_max_key(key, &tmp_max_key,
  2353.        &tmp_max_flag);
  2354.       flag=tmp_min_flag | tmp_max_flag;
  2355.     }
  2356.   }
  2357.   else
  2358.   {
  2359.     flag = (key_tree->min_flag & GEOM_FLAG) ?
  2360.       key_tree->min_flag : key_tree->min_flag | key_tree->max_flag;
  2361.   }
  2362.   /*
  2363.     Ensure that some part of min_key and max_key are used.  If not,
  2364.     regard this as no lower/upper range
  2365.   */
  2366.   if ((flag & GEOM_FLAG) == 0)
  2367.   {
  2368.     if (tmp_min_key != param->min_key)
  2369.       flag&= ~NO_MIN_RANGE;
  2370.     else
  2371.       flag|= NO_MIN_RANGE;
  2372.     if (tmp_max_key != param->max_key)
  2373.       flag&= ~NO_MAX_RANGE;
  2374.     else
  2375.       flag|= NO_MAX_RANGE;
  2376.   }
  2377.   if (flag == 0)
  2378.   {
  2379.     uint length= (uint) (tmp_min_key - param->min_key);
  2380.     if (length == (uint) (tmp_max_key - param->max_key) &&
  2381. !memcmp(param->min_key,param->max_key,length))
  2382.     {
  2383.       KEY *table_key=quick->head->key_info+quick->index;
  2384.       flag=EQ_RANGE;
  2385.       if ((table_key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME &&
  2386.   key->part == table_key->key_parts-1)
  2387.       {
  2388. if (!(table_key->flags & HA_NULL_PART_KEY) ||
  2389.     !null_part_in_key(key,
  2390.       param->min_key,
  2391.       (uint) (tmp_min_key - param->min_key)))
  2392.   flag|= UNIQUE_RANGE;
  2393. else
  2394.   flag|= NULL_RANGE;
  2395.       }
  2396.     }
  2397.   }
  2398.   /* Get range for retrieving rows in QUICK_SELECT::get_next */
  2399.   if (!(range= new QUICK_RANGE((const char *) param->min_key,
  2400.        (uint) (tmp_min_key - param->min_key),
  2401.        (const char *) param->max_key,
  2402.        (uint) (tmp_max_key - param->max_key),
  2403.        flag)))
  2404.     return 1; // out of memory
  2405.   set_if_bigger(quick->max_used_key_length,range->min_length);
  2406.   set_if_bigger(quick->max_used_key_length,range->max_length);
  2407.   set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1);
  2408.   quick->ranges.push_back(range);
  2409.  end:
  2410.   if (key_tree->right != &null_element)
  2411.     return get_quick_keys(param,quick,key,key_tree->right,
  2412.   min_key,min_key_flag,
  2413.   max_key,max_key_flag);
  2414.   return 0;
  2415. }
  2416. /*
  2417.   Return 1 if there is only one range and this uses the whole primary key
  2418. */
  2419. bool QUICK_SELECT::unique_key_range()
  2420. {
  2421.   if (ranges.elements == 1)
  2422.   {
  2423.     QUICK_RANGE *tmp;
  2424.     if (((tmp=ranges.head())->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
  2425.     {
  2426.       KEY *key=head->key_info+index;
  2427.       return ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME &&
  2428.       key->key_length == tmp->min_length);
  2429.     }
  2430.   }
  2431.   return 0;
  2432. }
  2433. /* Returns true if any part of the key is NULL */
  2434. static bool null_part_in_key(KEY_PART *key_part, const char *key, uint length)
  2435. {
  2436.   for (const char *end=key+length ; 
  2437.        key < end;
  2438.        key+= key_part++->store_length)
  2439.   {
  2440.     if (key_part->null_bit && *key)
  2441.       return 1;
  2442.   }
  2443.   return 0;
  2444. }
  2445. /****************************************************************************
  2446.   Create a QUICK RANGE based on a key
  2447. ****************************************************************************/
  2448. QUICK_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, TABLE_REF *ref)
  2449. {
  2450.   MEM_ROOT *old_root= thd->mem_root;
  2451.   /* The following call may change thd->mem_root */
  2452.   QUICK_SELECT *quick= new QUICK_SELECT(thd, table, ref->key);
  2453.   KEY *key_info = &table->key_info[ref->key];
  2454.   KEY_PART *key_part;
  2455.   QUICK_RANGE *range;
  2456.   uint part;
  2457.   if (!quick)
  2458.     return 0; /* no ranges found */
  2459.   if (cp_buffer_from_ref(thd, ref))
  2460.   {
  2461.     if (thd->is_fatal_error)
  2462.       goto err; // out of memory
  2463.     goto ok;                                    // empty range
  2464.   }
  2465.   if (!(range= new QUICK_RANGE()))
  2466.     goto err; // out of memory
  2467.   range->min_key=range->max_key=(char*) ref->key_buff;
  2468.   range->min_length=range->max_length=ref->key_length;
  2469.   range->flag= ((ref->key_length == key_info->key_length &&
  2470.  (key_info->flags & (HA_NOSAME | HA_END_SPACE_KEY)) ==
  2471.  HA_NOSAME) ? EQ_RANGE : 0);
  2472.   if (!(quick->key_parts=key_part=(KEY_PART *)
  2473. alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
  2474.     goto err;
  2475.   for (part=0 ; part < ref->key_parts ;part++,key_part++)
  2476.   {
  2477.     key_part->part=part;
  2478.     key_part->field=        key_info->key_part[part].field;
  2479.     key_part->length=       key_info->key_part[part].length;
  2480.     key_part->store_length= key_info->key_part[part].store_length;
  2481.     key_part->null_bit=     key_info->key_part[part].null_bit;
  2482.   }
  2483.   if (quick->ranges.push_back(range))
  2484.     goto err;
  2485.   /* 
  2486.      Add a NULL range if REF_OR_NULL optimization is used.
  2487.      For example:
  2488.        if we have "WHERE A=2 OR A IS NULL" we created the (A=2) range above
  2489.        and have ref->null_ref_key set. Will create a new NULL range here.
  2490.   */
  2491.   if (ref->null_ref_key)
  2492.   {
  2493.     QUICK_RANGE *null_range;
  2494.     *ref->null_ref_key= 1; // Set null byte then create a range
  2495.     if (!(null_range= new QUICK_RANGE((char*)ref->key_buff, ref->key_length,
  2496.       (char*)ref->key_buff, ref->key_length,
  2497.       EQ_RANGE)))
  2498.       goto err;
  2499.     *ref->null_ref_key= 0; // Clear null byte
  2500.     if (quick->ranges.push_back(null_range))
  2501.       goto err;
  2502.   }
  2503. ok:
  2504.   thd->mem_root= old_root;
  2505.   return quick;
  2506. err:
  2507.   thd->mem_root= old_root;
  2508.   delete quick;
  2509.   return 0;
  2510. }
  2511. /* get next possible record using quick-struct */
  2512. int QUICK_SELECT::get_next()
  2513. {
  2514.   DBUG_ENTER("get_next");
  2515.   for (;;)
  2516.   {
  2517.     int result;
  2518.     key_range start_key, end_key;
  2519.     if (range)
  2520.     {
  2521.       // Already read through key
  2522.       result= file->read_range_next();
  2523.       if (result != HA_ERR_END_OF_FILE)
  2524. DBUG_RETURN(result);
  2525.     }
  2526.     if (!(range= it++))
  2527.       DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used
  2528.     start_key.key=    (const byte*) range->min_key;
  2529.     start_key.length= range->min_length;
  2530.     start_key.flag=   ((range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
  2531.        (range->flag & EQ_RANGE) ?
  2532.        HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
  2533.     end_key.key=      (const byte*) range->max_key;
  2534.     end_key.length=   range->max_length;
  2535.     /*
  2536.       We use READ_AFTER_KEY here because if we are reading on a key
  2537.       prefix we want to find all keys with this prefix
  2538.     */
  2539.     end_key.flag=     (range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
  2540.        HA_READ_AFTER_KEY);
  2541.     result= file->read_range_first(range->min_length ? &start_key : 0,
  2542.    range->max_length ? &end_key : 0,
  2543.                                    test(range->flag & EQ_RANGE),
  2544.    sorted);
  2545.     if (range->flag == (UNIQUE_RANGE | EQ_RANGE))
  2546.       range=0; // Stop searching
  2547.     if (result != HA_ERR_END_OF_FILE)
  2548.       DBUG_RETURN(result);
  2549.     range=0; // No matching rows; go to next range
  2550.   }
  2551. }
  2552. /* Get next for geometrical indexes */
  2553. int QUICK_SELECT_GEOM::get_next()
  2554. {
  2555.   DBUG_ENTER(" QUICK_SELECT_GEOM::get_next");
  2556.   for (;;)
  2557.   {
  2558.     int result;
  2559.     if (range)
  2560.     {
  2561.       // Already read through key
  2562.       result= file->index_next_same(record, (byte*) range->min_key,
  2563.     range->min_length);
  2564.       if (result != HA_ERR_END_OF_FILE)
  2565. DBUG_RETURN(result);
  2566.     }
  2567.     if (!(range= it++))
  2568.       DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used
  2569.     result= file->index_read(record,
  2570.      (byte*) range->min_key,
  2571.      range->min_length,
  2572.      (ha_rkey_function)(range->flag ^ GEOM_FLAG));
  2573.     if (result != HA_ERR_KEY_NOT_FOUND)
  2574.       DBUG_RETURN(result);
  2575.     range=0; // Not found, to next range
  2576.   }
  2577. }
  2578. /*
  2579.   This is a hack: we inherit from QUICK_SELECT so that we can use the
  2580.   get_next() interface, but we have to hold a pointer to the original
  2581.   QUICK_SELECT because its data are used all over the place.  What
  2582.   should be done is to factor out the data that is needed into a base
  2583.   class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
  2584.   which handle the ranges and implement the get_next() function.  But
  2585.   for now, this seems to work right at least.
  2586.  */
  2587. QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_SELECT *q, uint used_key_parts)
  2588.   : QUICK_SELECT(*q), rev_it(rev_ranges)
  2589. {
  2590.   QUICK_RANGE *r;
  2591.   it.rewind();
  2592.   for (r = it++; r; r = it++)
  2593.   {
  2594.     rev_ranges.push_front(r);
  2595.   }
  2596.   /* Remove EQ_RANGE flag for keys that are not using the full key */
  2597.   for (r = rev_it++; r; r = rev_it++)
  2598.   {
  2599.     if ((r->flag & EQ_RANGE) &&
  2600. head->key_info[index].key_length != r->max_length)
  2601.       r->flag&= ~EQ_RANGE;
  2602.   }
  2603.   rev_it.rewind();
  2604.   q->dont_free=1; // Don't free shared mem
  2605.   delete q;
  2606. }
  2607. int QUICK_SELECT_DESC::get_next()
  2608. {
  2609.   DBUG_ENTER("QUICK_SELECT_DESC::get_next");
  2610.   /* The max key is handled as follows:
  2611.    *   - if there is NO_MAX_RANGE, start at the end and move backwards
  2612.    *   - if it is an EQ_RANGE, which means that max key covers the entire
  2613.    *     key, go directly to the key and read through it (sorting backwards is
  2614.    *     same as sorting forwards)
  2615.    *   - if it is NEAR_MAX, go to the key or next, step back once, and
  2616.    *     move backwards
  2617.    *   - otherwise (not NEAR_MAX == include the key), go after the key,
  2618.    *     step back once, and move backwards
  2619.    */
  2620.   for (;;)
  2621.   {
  2622.     int result;
  2623.     if (range)
  2624.     { // Already read through key
  2625.       result = ((range->flag & EQ_RANGE)
  2626. ? file->index_next_same(record, (byte*) range->min_key,
  2627. range->min_length) :
  2628. file->index_prev(record));
  2629.       if (!result)
  2630.       {
  2631. if (cmp_prev(*rev_it.ref()) == 0)
  2632.   DBUG_RETURN(0);
  2633.       }
  2634.       else if (result != HA_ERR_END_OF_FILE)
  2635. DBUG_RETURN(result);
  2636.     }
  2637.     if (!(range=rev_it++))
  2638.       DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used
  2639.     if (range->flag & NO_MAX_RANGE) // Read last record
  2640.     {
  2641.       int local_error;
  2642.       if ((local_error=file->index_last(record)))
  2643. DBUG_RETURN(local_error); // Empty table
  2644.       if (cmp_prev(range) == 0)
  2645. DBUG_RETURN(0);
  2646.       range=0; // No matching records; go to next range
  2647.       continue;
  2648.     }
  2649.     if (range->flag & EQ_RANGE)
  2650.     {
  2651.       result = file->index_read(record, (byte*) range->max_key,
  2652. range->max_length, HA_READ_KEY_EXACT);
  2653.     }
  2654.     else
  2655.     {
  2656.       DBUG_ASSERT(range->flag & NEAR_MAX || range_reads_after_key(range));
  2657.       result=file->index_read(record, (byte*) range->max_key,
  2658.       range->max_length,
  2659.       ((range->flag & NEAR_MAX) ?
  2660.        HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV));
  2661.     }
  2662.     if (result)
  2663.     {
  2664.       if (result != HA_ERR_KEY_NOT_FOUND)
  2665. DBUG_RETURN(result);
  2666.       range=0; // Not found, to next range
  2667.       continue;
  2668.     }
  2669.     if (cmp_prev(range) == 0)
  2670.     {
  2671.       if (range->flag == (UNIQUE_RANGE | EQ_RANGE))
  2672. range = 0; // Stop searching
  2673.       DBUG_RETURN(0); // Found key is in range
  2674.     }
  2675.     range = 0; // To next range
  2676.   }
  2677. }
  2678. /*
  2679.   Returns 0 if found key is inside range (found key >= range->min_key).
  2680. */
  2681. int QUICK_SELECT_DESC::cmp_prev(QUICK_RANGE *range_arg)
  2682. {
  2683.   int cmp;
  2684.   if (range_arg->flag & NO_MIN_RANGE)
  2685.     return 0; /* key can't be to small */
  2686.   cmp= key_cmp(key_part_info, (byte*) range_arg->min_key,
  2687.                range_arg->min_length);
  2688.   if (cmp > 0 || cmp == 0 && !(range_arg->flag & NEAR_MIN))
  2689.     return 0;
  2690.   return 1;                                     // outside of range
  2691. }
  2692. /*
  2693.  * True if this range will require using HA_READ_AFTER_KEY
  2694.    See comment in get_next() about this
  2695.  */
  2696. bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
  2697. {
  2698.   return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
  2699.   !(range_arg->flag & EQ_RANGE) ||
  2700.   head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
  2701. }
  2702. /* True if we are reading over a key that may have a NULL value */
  2703. #ifdef NOT_USED
  2704. bool QUICK_SELECT_DESC::test_if_null_range(QUICK_RANGE *range_arg,
  2705.    uint used_key_parts)
  2706. {
  2707.   uint offset, end;
  2708.   KEY_PART *key_part = key_parts,
  2709.            *key_part_end= key_part+used_key_parts;
  2710.   for (offset= 0,  end = min(range_arg->min_length, range_arg->max_length) ;
  2711.        offset < end && key_part != key_part_end ;
  2712.        offset+= key_part++->store_length)
  2713.   {
  2714.     if (!memcmp((char*) range_arg->min_key+offset,
  2715. (char*) range_arg->max_key+offset,
  2716. key_part->store_length))
  2717.       continue;
  2718.     if (key_part->null_bit && range_arg->min_key[offset])
  2719.       return 1; // min_key is null and max_key isn't
  2720.     // Range doesn't cover NULL. This is ok if there is no more null parts
  2721.     break;
  2722.   }
  2723.   /*
  2724.     If the next min_range is > NULL, then we can use this, even if
  2725.     it's a NULL key
  2726.     Example:  SELECT * FROM t1 WHERE a = 2 AND b >0 ORDER BY a DESC,b DESC;
  2727.   */
  2728.   if (key_part != key_part_end && key_part->null_bit)
  2729.   {
  2730.     if (offset >= range_arg->min_length || range_arg->min_key[offset])
  2731.       return 1; // Could be null
  2732.     key_part++;
  2733.   }
  2734.   /*
  2735.     If any of the key parts used in the ORDER BY could be NULL, we can't
  2736.     use the key to sort the data.
  2737.   */
  2738.   for (; key_part != key_part_end ; key_part++)
  2739.     if (key_part->null_bit)
  2740.       return 1; // Covers null part
  2741.   return 0;
  2742. }
  2743. #endif
  2744. /*****************************************************************************
  2745. ** Print a quick range for debugging
  2746. ** TODO:
  2747. ** This should be changed to use a String to store each row instead
  2748. ** of locking the DEBUG stream !
  2749. *****************************************************************************/
  2750. #ifndef DBUG_OFF
  2751. static void
  2752. print_key(KEY_PART *key_part,const char *key,uint used_length)
  2753. {
  2754.   char buff[1024];
  2755.   const char *key_end= key+used_length;
  2756.   String tmp(buff,sizeof(buff),&my_charset_bin);
  2757.   uint store_length;
  2758.   for (; key < key_end; key+=store_length, key_part++)
  2759.   {
  2760.     Field *field=      key_part->field;
  2761.     store_length= key_part->store_length;
  2762.     if (field->real_maybe_null())
  2763.     {
  2764.       if (*key)
  2765.       {
  2766. fwrite("NULL",sizeof(char),4,DBUG_FILE);
  2767. continue;
  2768.       }
  2769.       key++; // Skip null byte
  2770.       store_length--;
  2771.     }
  2772.     field->set_key_image((char*) key, key_part->length, field->charset());
  2773.     field->val_str(&tmp);
  2774.     fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
  2775.     if (key+store_length < key_end)
  2776.       fputc('/',DBUG_FILE);
  2777.   }
  2778. }
  2779. static void print_quick(QUICK_SELECT *quick,const key_map* needed_reg)
  2780. {
  2781.   QUICK_RANGE *range;
  2782.   char buf[MAX_KEY/8+1];
  2783.   DBUG_ENTER("print_param");
  2784.   if (! _db_on_ || !quick)
  2785.     DBUG_VOID_RETURN;
  2786.   List_iterator<QUICK_RANGE> li(quick->ranges);
  2787.   DBUG_LOCK_FILE;
  2788.   fprintf(DBUG_FILE,"Used quick_range on key: %d (other_keys: 0x%s):n",
  2789.   quick->index, needed_reg->print(buf));
  2790.   while ((range=li++))
  2791.   {
  2792.     if (!(range->flag & NO_MIN_RANGE))
  2793.     {
  2794.       print_key(quick->key_parts,range->min_key,range->min_length);
  2795.       if (range->flag & NEAR_MIN)
  2796. fputs(" < ",DBUG_FILE);
  2797.       else
  2798. fputs(" <= ",DBUG_FILE);
  2799.     }
  2800.     fputs("X",DBUG_FILE);
  2801.     if (!(range->flag & NO_MAX_RANGE))
  2802.     {
  2803.       if (range->flag & NEAR_MAX)
  2804. fputs(" < ",DBUG_FILE);
  2805.       else
  2806. fputs(" <= ",DBUG_FILE);
  2807.       print_key(quick->key_parts,range->max_key,range->max_length);
  2808.     }
  2809.     fputs("n",DBUG_FILE);
  2810.   }
  2811.   DBUG_UNLOCK_FILE;
  2812.   DBUG_VOID_RETURN;
  2813. }
  2814. #endif
  2815. /*****************************************************************************
  2816. ** Instansiate templates
  2817. *****************************************************************************/
  2818. #ifdef __GNUC__
  2819. template class List<QUICK_RANGE>;
  2820. template class List_iterator<QUICK_RANGE>;
  2821. #endif