1
/* Copyright (C) 2000 MySQL AB
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
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
25
#include "drizzled/internal/my_sys.h"
26
#include "drizzled/internal/m_string.h"
35
void radixsort_for_str_ptr(unsigned char **base, uint32_t number_of_elements, size_t size_of_element, unsigned char **buffer)
37
unsigned char **end,**ptr,**buffer_ptr;
38
uint32_t *count_ptr,*count_end,count[256];
41
end=base+number_of_elements; count_end=count+256;
42
for (pass=(int) size_of_element-1 ; pass >= 0 ; pass--)
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)
49
for (count_ptr=count+1 ; count_ptr < count_end ; count_ptr++)
51
if (*count_ptr == number_of_elements)
53
(*count_ptr)+= *(count_ptr-1);
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++;
63
} /* namespace internal */
64
} /* namespace drizzled */