1 /*
2 radixsort.c radix sort
3
4 Copyright (C) 2014-2020 Martin Dvorak <martin.dvorak@mindforger.com>
5
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 */
18
19 #include "include/radixsort.h"
20
21 #define GET_TOP_INDEX(KEY) KEY/RADIX_SLOT_SIZE
22 #define GET_LOW_INDEX(KEY) KEY%RADIX_SLOT_SIZE
23
radixsort_init(RadixSorter * rs,unsigned keyLimit)24 void radixsort_init(RadixSorter* rs, unsigned keyLimit)
25 {
26 rs->optionBigKeys=RADIX_BIG_KEYS_SKIP;
27
28 rs->_topIndexLimit=GET_TOP_INDEX(keyLimit);
29 rs->size=0;
30 rs->topDigits=malloc(rs->_topIndexLimit * sizeof(RadixItem***));
31 memset(rs->topDigits, 0, rs->_topIndexLimit * sizeof(RadixItem***));
32 rs->maxKey=0;
33 rs->keyLimit=keyLimit;
34
35 rs->_slotDescriptors=malloc(rs->_topIndexLimit * sizeof(RadixSlot**));
36 rs->_slotsCount=0;
37 rs->_debug=RADIX_DEBUG_LEVEL_NONE;
38 }
39
radixsort_destroy(RadixSorter * rs)40 void radixsort_destroy(RadixSorter* rs)
41 {
42 // radix items: DONE (passed on dump() by reference)
43 // rs: DONE (created and destroyed by caller)
44 // slots:
45 int topIndex = GET_TOP_INDEX(rs->maxKey);
46 do {
47 if(rs->topDigits[topIndex]) {
48 free(rs->topDigits[topIndex]);
49 free(rs->_slotDescriptors[topIndex]);
50 }
51 } while(--topIndex>=0);
52 free(rs->topDigits);
53 free(rs->_slotDescriptors);
54 }
55
radixsort_set_debug_level(RadixSorter * rs,unsigned debugLevel)56 void radixsort_set_debug_level(RadixSorter* rs, unsigned debugLevel)
57 {
58 rs->_debug=debugLevel;
59 }
60
radixsort_get_slot(RadixSorter * rs,unsigned topIndex)61 RadixItem** radixsort_get_slot(RadixSorter* rs, unsigned topIndex)
62 {
63 RadixItem **slot=malloc(RADIX_SLOT_SIZE * sizeof(RadixItem*));
64 memset(slot, 0, RADIX_SLOT_SIZE * sizeof(RadixItem*));
65
66 RadixSlot *descriptor=malloc(sizeof(RadixSlot));
67 descriptor->min=rs->keyLimit;
68 descriptor->max=0;
69 descriptor->size=0;
70
71 rs->_slotDescriptors[topIndex]=descriptor;
72 rs->_slotsCount++;
73 return slot;
74 }
75
radixsort_add(RadixSorter * rs,RadixItem * item)76 void radixsort_add(RadixSorter* rs, RadixItem* item)
77 {
78 if(item->key > rs->keyLimit) {
79 if(rs->_debug > RADIX_DEBUG_LEVEL_NONE) {
80 fprintf(stderr, "WARNING: Radix sort overflow - inserted key is bigger than limit (%u): %u\n", rs->keyLimit, item->key);
81 }
82 if(rs->optionBigKeys==RADIX_BIG_KEYS_FLOOR) {
83 item->key = rs->keyLimit-1;
84 } else {
85 if(rs->optionBigKeys==RADIX_BIG_KEYS_SKIP) {
86 return;
87 } else {
88 exit(0);
89 }
90 }
91 }
92
93 unsigned topIndex = GET_TOP_INDEX(item->key);
94 unsigned lowIndex = GET_LOW_INDEX(item->key);
95
96 if(!rs->topDigits[topIndex]) {
97 rs->topDigits[topIndex]=radixsort_get_slot(rs, topIndex);
98 }
99
100 RadixItem* chain=rs->topDigits[topIndex][lowIndex];
101 rs->topDigits[topIndex][lowIndex]=item;
102 if(chain==NULL) {
103 item->next=NULL;
104 } else {
105 item->next=chain;
106 }
107
108 rs->size++;
109 rs->maxKey=MAX(rs->maxKey,item->key);
110 rs->_slotDescriptors[topIndex]->min=MIN(rs->_slotDescriptors[topIndex]->min,item->key);
111 rs->_slotDescriptors[topIndex]->max=MAX(rs->_slotDescriptors[topIndex]->max,item->key);
112 rs->_slotDescriptors[topIndex]->size++;
113 }
114
radix_dec_slot_descriptor_size(RadixSorter * rs,RadixSlot * descriptor,unsigned key,unsigned topIndex)115 void radix_dec_slot_descriptor_size(RadixSorter* rs, RadixSlot *descriptor, unsigned key, unsigned topIndex)
116 {
117 UNUSED_ARG(key);
118
119 descriptor->size--;
120 if(!descriptor->size) {
121 descriptor->min=rs->keyLimit;
122 descriptor->max=0;
123 } else {
124 if(descriptor->size==1) {
125 if(rs->topDigits[topIndex][GET_LOW_INDEX(descriptor->max)]) {
126 descriptor->min=descriptor->max;
127 } else {
128 if(rs->topDigits[topIndex][GET_LOW_INDEX(descriptor->min)]) {
129 descriptor->max=descriptor->min;
130 }
131 }
132 }
133 }
134 }
135
radix_cut(RadixSorter * rs,unsigned key,void * data)136 RadixItem* radix_cut(RadixSorter* rs, unsigned key, void* data)
137 {
138 // TODO optimization: fix min/max on cut of a value
139 if(key <= rs->maxKey) {
140 unsigned topIndex = GET_TOP_INDEX(key);
141 unsigned lowIndex = GET_LOW_INDEX(key);
142
143 if(rs->topDigits[topIndex]) {
144 RadixItem *ri=rs->topDigits[topIndex][lowIndex];
145 RadixItem *lastRi=NULL;
146 while(ri->data!=data) {
147 if(ri->next) {
148 lastRi=ri;
149 ri=ri->next;
150 } else {
151 break;
152 }
153 }
154 if(ri->data==data) {
155 if(lastRi) {
156 lastRi->next=ri->next;
157 } else {
158 rs->topDigits[topIndex][lowIndex]=ri->next;
159 }
160 ri->next=NULL;
161 rs->size--;
162 radix_dec_slot_descriptor_size(rs, rs->_slotDescriptors[topIndex], key, topIndex);
163 return ri;
164 }
165 }
166 }
167 return NULL;
168 }
169
radixsort_dump(RadixSorter * rs)170 RadixItem** radixsort_dump(RadixSorter* rs)
171 {
172 if(rs->size>0) {
173 RadixItem **result=malloc(rs->size * sizeof(RadixItem *));
174 int t = GET_TOP_INDEX(rs->maxKey);
175 int slotMin, slotSize, slotCount, l;
176 unsigned items=0;
177 do {
178 if(rs->topDigits[t]) {
179 if(rs->_slotDescriptors[t]->size>0) {
180 l=GET_LOW_INDEX(rs->_slotDescriptors[t]->max);
181 slotMin=GET_LOW_INDEX(rs->_slotDescriptors[t]->min);
182 slotSize=rs->_slotDescriptors[t]->size;
183 slotCount=0;
184 do {
185 if(rs->topDigits[t][l]) {
186 result[items++]=rs->topDigits[t][l];
187 slotCount++;
188 RadixItem *ri=rs->topDigits[t][l]->next;
189 while(ri) {
190 result[items++]=ri;
191 slotCount++;
192 ri=ri->next;
193 }
194 }
195 } while(--l>=slotMin && slotCount<slotSize);
196 }
197 }
198 } while(--t>=0);
199 return result;
200 }
201 return NULL;
202 }
203
radixsort_stat(RadixSorter * rs,bool listing)204 void radixsort_stat(RadixSorter* rs, bool listing)
205 {
206 printf("\n Radixsort (size/max/limit/slot count): %u %u %u %u", rs->size, rs->maxKey, rs->keyLimit, rs->_slotsCount);
207 unsigned memory=rs->_topIndexLimit * sizeof(RadixItem ***);
208 memory+=memory;
209 memory+=rs->_slotsCount*(RADIX_SLOT_SIZE * sizeof(RadixItem *));
210 printf("\n Memory: %u\n", memory);
211 if(listing && rs->size>0) {
212 int t = GET_TOP_INDEX(rs->maxKey);
213 int slotMin, slotSize, slotCount, l;
214 unsigned items=0;
215 do {
216 if(rs->topDigits[t]) {
217 printf("\n Slot %u (size/min/max): %u %u %u",t, rs->_slotDescriptors[t]->size, rs->_slotDescriptors[t]->min, rs->_slotDescriptors[t]->max);
218 if(rs->_slotDescriptors[t]->size>0) {
219 l=GET_LOW_INDEX(rs->_slotDescriptors[t]->max);
220 slotMin=GET_LOW_INDEX(rs->_slotDescriptors[t]->min);
221 slotSize=rs->_slotDescriptors[t]->size;
222 slotCount=0;
223 do {
224 if(rs->topDigits[t][l]) {
225 printf("\n > %d #%u",l, ++items);
226 ++slotCount;
227 RadixItem *ri=rs->topDigits[t][l]->next;
228 while(ri) {
229 printf(" #%u",++items);
230 ++slotCount;
231 ri=ri->next;
232 }
233 }
234 } while(--l>=slotMin && slotCount<slotSize);
235 printf("\n STOP @ %d",l);
236 } else {
237 printf(" > SKIPPED");
238 }
239 }
240 } while(--t>=0);
241 }
242 fflush(stdout);
243 }
244