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