From 354bb40e75d94466e91fe6960523612c9d17ccfb Mon Sep 17 00:00:00 2001 From: Karen Arutyunov Date: Thu, 2 Nov 2017 23:11:29 +0300 Subject: Add implementation --- mysql/mysys/my_compare.c | 474 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 474 insertions(+) create mode 100644 mysql/mysys/my_compare.c (limited to 'mysql/mysys/my_compare.c') diff --git a/mysql/mysys/my_compare.c b/mysql/mysys/my_compare.c new file mode 100644 index 0000000..a23c2a3 --- /dev/null +++ b/mysql/mysys/my_compare.c @@ -0,0 +1,474 @@ +/* Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. + + 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-1301, USA */ + +#include +#include +#include +#include +#include + +#define CMP_NUM(a,b) (((a) < (b)) ? -1 : ((a) == (b)) ? 0 : 1) + +int ha_compare_text(const CHARSET_INFO *charset_info, uchar *a, uint a_length, + uchar *b, uint b_length, my_bool part_key, + my_bool skip_end_space) +{ + if (!part_key) + return charset_info->coll->strnncollsp(charset_info, a, a_length, + b, b_length, (my_bool)!skip_end_space); + return charset_info->coll->strnncoll(charset_info, a, a_length, + b, b_length, part_key); +} + + +static int compare_bin(uchar *a, uint a_length, uchar *b, uint b_length, + my_bool part_key, my_bool skip_end_space) +{ + uint length= MY_MIN(a_length, b_length); + 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 normally key specified by user + b Second key to compare. This is always from a row + key_length Length of key to compare. This can be shorter than + a 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 + 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 beggining 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 beggining 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, uchar *a, + uchar *b, uint key_length, uint 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; + uchar *orig_b= b; + + *diff_pos=0; + for ( ; (int) key_length >0 ; key_length=next_key_length, keyseg++) + { + 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)) + nextflag=SEARCH_SAME; /* Allow duplicate keys */ + 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_text(keyseg->charset,a,a_length,b,b_length, + (my_bool) ((nextflag & SEARCH_PREFIX) && + next_key_length <= 0), + (my_bool)!(nextflag & SEARCH_PREFIX)))) + 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_text(keyseg->charset, a, a_length, b, b_length, + (my_bool) ((nextflag & SEARCH_PREFIX) && + next_key_length <= 0), + (my_bool)!(nextflag & SEARCH_PREFIX)))) + 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_text(keyseg->charset,a,a_length,b,b_length, + (my_bool) ((nextflag & SEARCH_PREFIX) && + next_key_length <= 0), + (my_bool) ((nextflag & (SEARCH_FIND | + SEARCH_UPDATE)) == + SEARCH_FIND && + ! (keyseg->flag & + HA_END_SPACE_ARE_EQUAL))))) + 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(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(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(uchar*, a, b); + break; + } + 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; + } + case HA_KEYTYPE_END: /* Ready */ + goto end; /* diff_pos is incremented */ + } + } + (*diff_pos)++; +end: + if (!(nextflag & SEARCH_FIND)) + { + uint i; + if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */ + return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1; + flag=0; + for (i=keyseg->length ; i-- > 0 ; ) + { + if (*a++ != *b++) + { + flag= FCMP(a[-1],b[-1]); + break; + } + } + 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 */ + + -- cgit v1.1