drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
mf_radix.cc
1/* Copyright (C) 2000 MySQL AB
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16/*
17 Radixsort for pointers to fixed length strings.
18 A very quick sort for not to long (< 20 char) strings.
19 Neads a extra buffers of number_of_elements pointers but is
20 2-3 times faster than quicksort
21*/
22
23#include <config.h>
24
25#include <drizzled/internal/my_sys.h>
26#include <drizzled/internal/m_string.h>
27
28namespace drizzled
29{
30namespace internal
31{
32
33 /* Radixsort */
34
35void radixsort_for_str_ptr(unsigned char **base, uint32_t number_of_elements, size_t size_of_element, unsigned char **buffer)
36{
37 unsigned char **end,**ptr,**buffer_ptr;
38 uint32_t *count_ptr,*count_end,count[256];
39 int pass;
40
41 end=base+number_of_elements; count_end=count+256;
42 for (pass=(int) size_of_element-1 ; pass >= 0 ; pass--)
43 {
44 memset(count, 0, sizeof(uint32_t)*256);
45 for (ptr= base ; ptr < end ; ptr++)
46 count[ptr[0][pass]]++;
47 if (count[0] == number_of_elements)
48 goto next;
49 for (count_ptr=count+1 ; count_ptr < count_end ; count_ptr++)
50 {
51 if (*count_ptr == number_of_elements)
52 goto next;
53 (*count_ptr)+= *(count_ptr-1);
54 }
55 for (ptr= end ; ptr-- != base ;)
56 buffer[--count[ptr[0][pass]]]= *ptr;
57 for (ptr=base, buffer_ptr=buffer ; ptr < end ;)
58 (*ptr++) = *buffer_ptr++;
59 next:;
60 }
61}
62
63} /* namespace internal */
64} /* namespace drizzled */
TODO: Rename this file - func.h is stupid.