From 06eaf7232e9a920468c0f8d74dcf2fe8b555501c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 14:24:36 +0200 Subject: Adding upstream version 1:10.11.6. Signed-off-by: Daniel Baumann --- mysys/mf_radix.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 mysys/mf_radix.c (limited to 'mysys/mf_radix.c') diff --git a/mysys/mf_radix.c b/mysys/mf_radix.c new file mode 100644 index 00000000..8f044cf9 --- /dev/null +++ b/mysys/mf_radix.c @@ -0,0 +1,60 @@ +/* Copyright (c) 2000, 2007 MySQL AB + Use is subject to license terms + + 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 */ + +/* + Radixsort for pointers to fixed length strings. + A very quick sort for not to long (< 20 char) strings. + Neads a extra buffers of number_of_elements pointers but is + 2-3 times faster than quicksort +*/ + +#include "mysys_priv.h" +#include + + /* Radixsort */ + +my_bool radixsort_is_appliccable(uint n_items, size_t size_of_element) +{ + return size_of_element <= 20 && n_items >= 1000 && n_items < 100000; +} + +void radixsort_for_str_ptr(uchar **base, uint number_of_elements, size_t size_of_element, uchar **buffer) +{ + uchar **end,**ptr,**buffer_ptr; + uint32 *count_ptr,*count_end,count[256]; + int pass; + + end=base+number_of_elements; count_end=count+256; + for (pass=(int) size_of_element-1 ; pass >= 0 ; pass--) + { + bzero((uchar*) count,sizeof(uint32)*256); + for (ptr= base ; ptr < end ; ptr++) + count[ptr[0][pass]]++; + if (count[0] == number_of_elements) + goto next; + for (count_ptr=count+1 ; count_ptr < count_end ; count_ptr++) + { + if (*count_ptr == number_of_elements) + goto next; + (*count_ptr)+= *(count_ptr-1); + } + for (ptr= end ; ptr-- != base ;) + buffer[--count[ptr[0][pass]]]= *ptr; + for (ptr=base, buffer_ptr=buffer ; ptr < end ;) + (*ptr++) = *buffer_ptr++; + next:; + } +} -- cgit v1.2.3