Adding upstream version 1:10.11.6.upstream/1%10.11.6upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 633 insertions, 0 deletions

diff --git a/mysys/my_compare.c b/mysys/my_compare.c
new file mode 100644
index 00000000..d1326dc9
--- /dev/null
+++ b/mysys/my_compare.c
@@ -0,0 +1,633 @@
+/* Copyright (c) 2011, Oracle and/or its affiliates.
+   Copyright (c) 2009, 2020, MariaDB Corporation.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+   
+#include <my_global.h>
+#include <m_ctype.h>
+#include <my_base.h>
+#include <my_compare.h>
+#include <my_sys.h>
+
+
+static int compare_bin(const uchar *a, uint a_length,
+                       const uchar *b, uint b_length,
+                       my_bool part_key, my_bool skip_end_space)
+{
+  uint length= MY_MIN(a_length,b_length);
+  const uchar *end= a+ length;
+  int flag;
+
+  while (a < end)
+    if ((flag= (int) *a++ - (int) *b++))
+      return flag;
+  if (part_key && b_length < a_length)
+    return 0;
+  if (skip_end_space && a_length != b_length)
+  {
+    int swap= 1;
+    /*
+      We are using space compression. We have to check if longer key
+      has next character < ' ', in which case it's less than the shorter
+      key that has an implicite space afterwards.
+
+      This code is identical to the one in
+      strings/ctype-simple.c:my_strnncollsp_simple
+    */
+    if (a_length < b_length)
+    {
+      /* put shorter key in a */
+      a_length= b_length;
+      a= b;
+      swap= -1;					/* swap sign of result */
+    }
+    for (end= a + a_length-length; a < end ; a++)
+    {
+      if (*a != ' ')
+	return (*a < ' ') ? -swap : swap;
+    }
+    return 0;
+  }
+  return (int) (a_length-b_length);
+}
+
+
+/*
+  Compare two keys
+
+  SYNOPSIS
+    ha_key_cmp()
+    keyseg	Array of key segments of key to compare
+    a		First key to compare, in format from _mi_pack_key()
+		This is always from the row
+    b		Second key to compare.  This is from the row or the user
+    key_length	Length of key to compare, based on key b.  This can be shorter
+		than b to just compare sub keys
+    next_flag	How keys should be compared
+		If bit SEARCH_FIND is not set the keys includes the row
+		position and this should also be compared
+                If SEARCH_PAGE_KEY_HAS_TRANSID is set then 'a' has transid
+                If SEARCH_USER_KEY_HAS_TRANSID is set then 'b' has transid
+    diff_pos    OUT Number of first keypart where values differ, counting 
+                from one.
+    diff_pos[1] OUT  (b + diff_pos[1]) points to first value in tuple b
+                      that is different from corresponding value in tuple a.
+  
+  EXAMPLES 
+   Example1: if the function is called for tuples
+     ('aaa','bbb') and ('eee','fff'), then
+     diff_pos[0] = 1 (as 'aaa' != 'eee')
+     diff_pos[1] = 0 (offset from beginning of tuple b to 'eee' keypart).
+
+   Example2: if the index function is called for tuples
+     ('aaa','bbb') and ('aaa','fff'),
+     diff_pos[0] = 2 (as 'aaa' != 'eee')
+     diff_pos[1] = 3 (offset from beginning of tuple b to 'fff' keypart,
+                      here we assume that first key part is CHAR(3) NOT NULL)
+
+  NOTES
+    Number-keys can't be splited
+
+  RETURN VALUES
+    <0	If a < b
+    0	If a == b
+    >0	If a > b
+*/
+
+#define FCMP(A,B) ((int) (A) - (int) (B))
+
+int ha_key_cmp(HA_KEYSEG *keyseg, const uchar *a,
+               const uchar *b, uint key_length, uint32 nextflag,
+	       uint *diff_pos)
+{
+  int flag;
+  int16 s_1,s_2;
+  int32 l_1,l_2;
+  uint32 u_1,u_2;
+  float f_1,f_2;
+  double d_1,d_2;
+  uint next_key_length;
+  const uchar *orig_b= b;
+
+  *diff_pos=0;
+  for ( ; (int) key_length >0 ; key_length=next_key_length, keyseg++)
+  {
+    const uchar *end;
+    uint piks=! (keyseg->flag & HA_NO_SORT);
+    (*diff_pos)++;
+    diff_pos[1]= (uint)(b - orig_b);
+
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      key_length--;
+      if (*a != *b && piks)
+      {
+        flag = (int) *a - (int) *b;
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      }
+      b++;
+      if (!*a++)                                /* If key was NULL */
+      {
+        if ((nextflag & (SEARCH_FIND | SEARCH_UPDATE | SEARCH_INSERT |
+                         SEARCH_NULL_ARE_EQUAL)) ==
+            (SEARCH_FIND | SEARCH_UPDATE | SEARCH_INSERT))
+        {
+          /* Allow duplicate keys */
+          nextflag= (nextflag & ~(SEARCH_FIND | SEARCH_UPDATE)) | SEARCH_SAME;
+        }
+  	else if (nextflag & SEARCH_NULL_ARE_NOT_EQUAL)
+	{
+	  /*
+	    This is only used from mi_check() to calculate cardinality.
+	    It can't be used when searching for a key as this would cause
+	    compare of (a,b) and (b,a) to return the same value.
+	  */
+	  return -1;
+	}
+        next_key_length=key_length;
+        continue;                               /* To next key part */
+      }
+    }
+    end= a+ MY_MIN(keyseg->length,key_length);
+    next_key_length=key_length-keyseg->length;
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:                       /* Ascii; Key is converted */
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if (piks &&
+            (flag= ha_compare_char_fixed(keyseg->charset,
+                                 a, a_length,
+                                 b, b_length,
+                                 keyseg->length / keyseg->charset->mbmaxlen,
+                                 (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                            next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+	uint length=(uint) (end-a), a_length=length, b_length=length;
+        if (piks &&
+            (flag= ha_compare_char_fixed(keyseg->charset,
+                                 a, a_length,
+                                 b, b_length,
+                                 keyseg->length / keyseg->charset->mbmaxlen,
+                                 (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                            next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=end;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_BIT:
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if (piks &&
+	    (flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0),1)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+        uint length=keyseg->length;
+        if (piks &&
+	    (flag=compare_bin(a,length,b,length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0),0)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=length;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_VARTEXT1:
+    case HA_KEYTYPE_VARTEXT2:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if (piks &&
+            (flag= ha_compare_char_varying(keyseg->charset,
+                                   a, a_length,
+                                   b, b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+= a_length;
+        b+= b_length;
+        break;
+      }
+      break;
+    case HA_KEYTYPE_VARBINARY1:
+    case HA_KEYTYPE_VARBINARY2:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if (piks &&
+            (flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0), 0)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+      }
+      break;
+    case HA_KEYTYPE_INT8:
+    {
+      int i_1= (int) *((signed char*) a);
+      int i_2= (int) *((signed char*) b);
+      if (piks && (flag = CMP_NUM(i_1,i_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a= end;
+      b++;
+      break;
+    }
+    case HA_KEYTYPE_SHORT_INT:
+      s_1= mi_sint2korr(a);
+      s_2= mi_sint2korr(b);
+      if (piks && (flag = CMP_NUM(s_1,s_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 2; /* sizeof(short int); */
+      break;
+    case HA_KEYTYPE_USHORT_INT:
+      {
+        uint16 us_1,us_2;
+        us_1= mi_sint2korr(a);
+        us_2= mi_sint2korr(b);
+        if (piks && (flag = CMP_NUM(us_1,us_2)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=  end;
+        b+=2; /* sizeof(short int); */
+        break;
+      }
+    case HA_KEYTYPE_LONG_INT:
+      l_1= mi_sint4korr(a);
+      l_2= mi_sint4korr(b);
+      if (piks && (flag = CMP_NUM(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_ULONG_INT:
+      u_1= mi_sint4korr(a);
+      u_2= mi_sint4korr(b);
+      if (piks && (flag = CMP_NUM(u_1,u_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_INT24:
+      l_1=mi_sint3korr(a);
+      l_2=mi_sint3korr(b);
+      if (piks && (flag = CMP_NUM(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_UINT24:
+      l_1=mi_uint3korr(a);
+      l_2=mi_uint3korr(b);
+      if (piks && (flag = CMP_NUM(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_FLOAT:
+      mi_float4get(f_1,a);
+      mi_float4get(f_2,b);
+      /*
+        The following may give a compiler warning about floating point
+        comparison not being safe, but this is ok in this context as
+        we are bascily doing sorting
+      */
+      if (piks && (flag = CMP_NUM(f_1,f_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(float); */
+      break;
+    case HA_KEYTYPE_DOUBLE:
+      mi_float8get(d_1,a);
+      mi_float8get(d_2,b);
+      /*
+        The following may give a compiler warning about floating point
+        comparison not being safe, but this is ok in this context as
+        we are bascily doing sorting
+      */
+      if (piks && (flag = CMP_NUM(d_1,d_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;  /* sizeof(double); */
+      break;
+    case HA_KEYTYPE_NUM:                                /* Numeric key */
+    {
+      int swap_flag= 0;
+      int alength,blength;
+
+      if (keyseg->flag & HA_REVERSE_SORT)
+      {
+        swap_variables(const uchar*, a, b);
+        swap_flag=1;                            /* Remember swap of a & b */
+        end= a+ (int) (end-b);
+      }
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        alength= *a++; blength= *b++;
+        end=a+alength;
+        next_key_length=key_length-blength-1;
+      }
+      else
+      {
+        alength= (int) (end-a);
+        blength=keyseg->length;
+        /* remove pre space from keys */
+        for ( ; alength && *a == ' ' ; a++, alength--) ;
+        for ( ; blength && *b == ' ' ; b++, blength--) ;
+      }
+      if (piks)
+      {
+	if (*a == '-')
+	{
+	  if (*b != '-')
+	    return -1;
+	  a++; b++;
+	  swap_variables(const uchar*, a, b);
+	  swap_variables(int, alength, blength);
+	  swap_flag=1-swap_flag;
+	  alength--; blength--;
+	  end=a+alength;
+	}
+	else if (*b == '-')
+	  return 1;
+	while (alength && (*a == '+' || *a == '0'))
+	{
+	  a++; alength--;
+	}
+	while (blength && (*b == '+' || *b == '0'))
+	{
+	  b++; blength--;
+	}
+	if (alength != blength)
+	  return (alength < blength) ? -1 : 1;
+	while (a < end)
+	  if (*a++ !=  *b++)
+	    return ((int) a[-1] - (int) b[-1]);
+      }
+      else
+      {
+        b+=(end-a);
+        a=end;
+      }
+
+      if (swap_flag)                            /* Restore pointers */
+        swap_variables(const uchar*, a, b);
+      break;
+    }
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+    {
+      longlong ll_a,ll_b;
+      ll_a= mi_sint8korr(a);
+      ll_b= mi_sint8korr(b);
+      if (piks && (flag = CMP_NUM(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+    case HA_KEYTYPE_ULONGLONG:
+    {
+      ulonglong ll_a,ll_b;
+      ll_a= mi_uint8korr(a);
+      ll_b= mi_uint8korr(b);
+      if (piks && (flag = CMP_NUM(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+#endif
+    case HA_KEYTYPE_END:                        /* Ready */
+      goto end;                                 /* diff_pos is incremented */
+    }
+  }
+  (*diff_pos)++;
+end:
+  if (!(nextflag & SEARCH_FIND))
+  {
+    /*
+      Compare rowid and possible transid
+      This happens in the following case:
+      - INSERT, UPDATE, DELETE when we have not unique keys or
+        are using versioning
+      - SEARCH_NEXT, SEARCH_PREVIOUS when we need to restart search
+
+      The logic for comparing transid are as follows:
+      Keys with have a transid have lowest bit in the rowidt. This means that
+      if we are comparing a key with a transid with another key that doesn't
+      have a tranid, we must reset the lowest bit for both keys.
+
+      When we have transid, the keys are compared in transid order.
+      A key without a transid is regared to be smaller than a key with
+      a transid.
+    */
+
+    uint i;
+    uchar key_mask, tmp_a, tmp_b;
+
+    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */
+      return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
+    key_mask= (uchar) 255;
+
+    if (!(nextflag & (SEARCH_USER_KEY_HAS_TRANSID |
+                      SEARCH_PAGE_KEY_HAS_TRANSID)))
+    {
+      /*
+        Neither key has a trid.  Only compare row id's and don't
+        try to store rows in trid order
+      */
+      key_length= keyseg->length;
+      nextflag&= ~SEARCH_INSERT;
+    }
+    else
+    {
+      /*
+        Set key_mask so that we reset the last bit in the rowid before
+        we compare it. This is needed as the lowest bit in the rowid is
+        used to mark if the key has a transid or not.
+      */
+      key_mask= (uchar) 254;
+      if (!test_all_bits(nextflag, (SEARCH_USER_KEY_HAS_TRANSID |
+                                    SEARCH_PAGE_KEY_HAS_TRANSID)))
+      {
+        /*
+          No transaction id for user key or for key on page 
+          Ignore transid as at least one of the keys are visible for all
+        */
+        key_length= keyseg->length;
+      }
+      else
+      {
+        /*
+          Both keys have trids. No need of special handling of incomplete
+          trids below.
+        */
+        nextflag&= ~SEARCH_INSERT;
+      }
+    }
+    DBUG_ASSERT(key_length > 0);
+
+    for (i= key_length-1 ; (int) i-- > 0 ; )
+    {
+      if (*a++ != *b++)
+      {
+        flag= FCMP(a[-1],b[-1]);
+        goto found;
+      }
+    }
+    tmp_a= *a & key_mask;
+    tmp_b= *b & key_mask;
+    flag= FCMP(tmp_a, tmp_b);
+
+    if (flag == 0 && (nextflag & SEARCH_INSERT))
+    {
+      /*
+        Ensure that on insert we get rows stored in trid order.
+        If one of the parts doesn't have a trid, this should be regarded
+        as smaller than the other
+      */
+        return (nextflag & SEARCH_USER_KEY_HAS_TRANSID) ? -1 : 1;
+    }
+found:
+    if (nextflag & SEARCH_SAME)
+      return (flag);                            /* read same */
+    if (nextflag & SEARCH_BIGGER)
+      return (flag <= 0 ? -1 : 1);              /* read next */
+    return (flag < 0 ? -1 : 1);                 /* read previous */
+  }
+  return 0;
+} /* ha_key_cmp */
+
+/*
+  Find the first NULL value in index-suffix values tuple
+
+  SYNOPSIS
+    ha_find_null()
+      keyseg     Array of keyparts for key suffix
+      a          Key suffix value tuple
+
+  DESCRIPTION
+    Find the first NULL value in index-suffix values tuple.
+
+  TODO
+    Consider optimizing this function or its use so we don't search for
+    NULL values in completely NOT NULL index suffixes.
+
+  RETURN
+    First key part that has NULL as value in values tuple, or the last key
+    part (with keyseg->type==HA_TYPE_END) if values tuple doesn't contain
+    NULLs.
+*/
+
+HA_KEYSEG *ha_find_null(HA_KEYSEG *keyseg, const uchar *a)
+{
+  for (; (enum ha_base_keytype) keyseg->type != HA_KEYTYPE_END; keyseg++)
+  {
+    const uchar *end;
+    if (keyseg->null_bit)
+    {
+      if (!*a++)
+        return keyseg;
+    }
+    end= a+ keyseg->length;
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_BIT:
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length;
+        get_key_length(a_length, a);
+        a += a_length;
+        break;
+      }
+      else
+        a= end;
+      break;
+    case HA_KEYTYPE_VARTEXT1:
+    case HA_KEYTYPE_VARTEXT2:
+    case HA_KEYTYPE_VARBINARY1:
+    case HA_KEYTYPE_VARBINARY2:
+      {
+        int a_length;
+        get_key_length(a_length, a);
+        a+= a_length;
+        break;
+      }
+    case HA_KEYTYPE_NUM:
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int alength= *a++;
+        end= a+alength;
+      }
+      a= end;
+      break;
+    case HA_KEYTYPE_INT8:
+    case HA_KEYTYPE_SHORT_INT:
+    case HA_KEYTYPE_USHORT_INT:
+    case HA_KEYTYPE_LONG_INT:
+    case HA_KEYTYPE_ULONG_INT:
+    case HA_KEYTYPE_INT24:
+    case HA_KEYTYPE_UINT24:
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+    case HA_KEYTYPE_ULONGLONG:
+#endif
+    case HA_KEYTYPE_FLOAT:
+    case HA_KEYTYPE_DOUBLE:
+      a= end;
+      break;
+    case HA_KEYTYPE_END:                        /* purecov: inspected */
+      /* keep compiler happy */
+      DBUG_ASSERT(0);
+      break;
+    }
+  }
+  return keyseg;
+}
+