Add psort library
[tedtools.git] / psort.c
1 /*
2  * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *        notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *        notice, this list of conditions and the following disclaimer in the
12  *        documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the author nor the names of any co-contributors
14  *        may be used to endorse or promote products derived from this software
15  *        without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
18  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <math.h>
33 #include <string.h>
34
35 #include "tmalloc.h"
36 #include "psort.h"
37
38 /*
39  * this defines only for faster code
40  */
41 #define insert_full(val)  do {                                             \
42         tmp = sobj->last;                                                  \
43         if ( sobj->free )                                                  \
44                 (*(sobj->free))( tmp->value );                             \
45         sobj->last = sobj->last->prev; /* current last */                  \
46         tmp->value = (val);                                                \
47         curitem = sobj->last;                                              \
48         curitem->next = tmp->prev = tmp->next = NULL;                      \
49                                                                            \
50         do {                                                               \
51                 if ( (*(sobj->cmpr))( curitem->value, (val) ) <= 0 ) {     \
52                         tmp->next = curitem->next;                         \
53                         tmp->prev = curitem;                               \
54                                                                            \
55                         if ( curitem->next ) /* not last */                \
56                                 curitem->next->prev = tmp;                 \
57                         else                                               \
58                                 sobj->last = tmp;                          \
59                         curitem->next = tmp;                               \
60                         break;                                             \
61                 }                                                          \
62                 curitem = curitem->prev;                                   \
63         } while ( curitem );                                               \
64         /* insert to first position */                                     \
65         if ( !tmp->prev ) {                                                \
66                 sobj->first->prev = tmp;                                   \
67                 tmp->next = sobj->first;                                   \
68                 sobj->first = tmp;                                         \
69         }                                                                  \
70 } while(0)
71
72 #define insert_notfull( val ) do {                                         \
73         tmp = &(sobj->buf[sobj->curlen]);                                  \
74         tmp->value = (val);                                                \
75         previtem = NULL;                                                   \
76         curitem = sobj->first;                                             \
77         do {                                                               \
78                 if ( (*(sobj->cmpr))( curitem->value, tmp->value ) > 0 ) { \
79                         tmp->next = curitem;                               \
80                         curitem->prev = tmp;                               \
81                         tmp->prev = previtem;                              \
82                         if ( previtem )                                    \
83                                 previtem->next = tmp;                      \
84                         else {                                             \
85                                 sobj->first->prev = tmp;                   \
86                                 sobj->first = tmp;                         \
87                         }                                                  \
88                         break;                                             \
89                 }                                                          \
90                 previtem = curitem;                                        \
91                 curitem = curitem->next;                                   \
92         } while( curitem );                                                \
93         if ( ! tmp->next ) { /*not inserted*/                              \
94                 sobj->last->next = tmp;                                    \
95                 tmp->prev = sobj->last;                                    \
96                 sobj->last = tmp;                                          \
97         }                                                                  \
98 } while(0) 
99
100
101
102 /*
103  * Initialization
104  * If input options are invalid, return -1
105  * if no memory return 1
106  * If success return 0
107  */
108 int 
109 PS_init( SORT* sobj, int buflen, compare_sort func, ffree ffunc ) {
110         if ( ! sobj ) return -1;
111         if ( ! func ) return -1;
112         if ( buflen <= 0 ) return -1;
113
114         sobj->buf = (SORTITEM*)tmalloc( sizeof(SORTITEM)*buflen );
115
116         memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*buflen );
117         sobj->buflen = buflen;
118         sobj->cmpr   = func;
119         sobj->free  = ffunc;
120         sobj->curlen = 0;
121
122         sobj->first = sobj->last = sobj->buf; 
123         sobj->curitem = NULL; 
124
125         return 0;
126 }
127
128 /*
129  * finish...
130  * clear memory
131  */
132 void  
133 PS_clear( SORT* sobj ) {
134         if ( sobj->free ) {
135                 int i;
136                 for(i=0; i<sobj->curlen; i++ )
137                         (*(sobj->free))( sobj->buf[i].value );
138         }
139         if ( sobj->buf ) 
140                 tfree( sobj->buf );
141         memset( (void*)sobj, 0, sizeof(SORT) );
142 }
143
144 /*
145  * Reset sort object..
146  */
147 void 
148 PS_reset( SORT* sobj ) {
149         int i;
150
151         if ( sobj->free ) {
152                 for(i=0; i<sobj->curlen; i++ );
153                         (*(sobj->free))( sobj->buf[i].value );
154         }
155         memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*sobj->buflen );
156         sobj->curlen = 0;
157         sobj->first = sobj->last = sobj->buf; 
158         sobj->curitem = NULL; 
159 }
160
161 /*
162  * Insert
163  */
164 int 
165 PS_insert( SORT* sobj, void* nobj ) {
166         SORTITEM *curitem, *previtem, *tmp;
167
168         /* first insertion */
169         if ( ! sobj->curlen  ) { 
170                 sobj->first->value = nobj;
171                 sobj->curlen++;
172                 return 1;
173         }
174
175         if ( sobj->curlen == sobj->buflen ) {
176                 if ( (*(sobj->cmpr))( sobj->last->value, nobj ) > 0 ) {
177                         if ( sobj->buflen == 1 ) {
178                                 if ( sobj->free ) 
179                                         (*(sobj->free))( sobj->last->value );
180                                 sobj->last->value = nobj;
181                         } else 
182                                 insert_full( nobj );
183                         return 1;
184                 }
185         } else {
186                 insert_notfull( nobj );
187                 sobj->curlen++;
188                 return 1;
189         }
190
191         return 0;
192 }
193
194 static compare_sort compareobject;
195 static int highlevelcompare( const void *a, const void *b ) {
196         return (*compareobject)(  *(void**)a, *(void**)b );     
197
198
199 /*
200  * Insert array, if defined free function, 
201  * unused item will be freeed
202  */
203
204 #define RECOMMEND_M(N)  ( ((N)<8000) ? ( 23.0+1.5*pow((N),0.6) ) : pow(( 8.05 * log((N)) - 53.53 ),2.0) )
205 void
206 PS_bulkinsert( SORT* sobj, void** nobjs, int len ) {
207         register SORTITEM *curitem, *tmp;
208         register void** ptr = nobjs;
209
210         if ( !sobj->curlen ) {
211                 int initlen = len;
212                 if ( len > sobj->buflen ) {
213                         if ( sobj->buflen < RECOMMEND_M( len ) )
214                                 initlen = sobj->buflen;
215                 }
216                 curitem = sobj->first;
217                 compareobject = sobj->cmpr;
218                 if ( initlen > 1 )
219                         qsort( nobjs, initlen, sizeof(void*), highlevelcompare );
220                 ptr = nobjs; 
221                 while( ptr - nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
222                         curitem->value = *ptr;
223                         if ( sobj->curlen ) {
224                                 curitem->prev = curitem - 1;
225                                 curitem->prev->next = curitem;
226                         }
227                         curitem++;
228                         sobj->curlen++;
229                         ptr++;
230                 }
231                 sobj->last = curitem-1;
232
233                 if ( sobj->free && initlen != sobj->buflen ) {
234                         while( ptr - nobjs < len ) { 
235                                 (*(sobj->free))( *ptr ); 
236                                 ptr++;
237                         }
238                         return;
239                 } 
240         } else {
241                 while( ptr - nobjs < len &&  sobj->curlen != sobj->buflen ) {
242                         PS_insert( sobj, *ptr ); /* buflen is very small, so we can use function call */ 
243                         ptr++;
244                 }
245         }
246
247         if ( sobj->free ) {
248                 while( ptr - nobjs < len ) {
249                         if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
250                                 if ( sobj->buflen == 1 ) {
251                                         (*(sobj->free))( sobj->last->value );
252                                         sobj->last->value = *ptr;
253                                 } else 
254                                         insert_full( *ptr );
255                         } else
256                                 (*(sobj->free))( *ptr );  
257                         ptr++;
258                 }
259         } else {
260                 while( ptr - nobjs < len ) {
261                         if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
262                                 if ( sobj->buflen == 1 )
263                                         sobj->last->value = *ptr;
264                                 else 
265                                         insert_full( *ptr );
266                         }
267                         ptr++;
268                 }
269         }
270
271
272 /*
273  * insert a-la qsort, require sobj->free = NULL
274  */
275 int 
276 PS_bulkplain( SORT* sobj, void* nobjs, int size, int len ) {
277         register SORTITEM *curitem, *tmp;
278         register char* ptr = (char*)nobjs;
279
280         if ( sobj->free )
281                 return 1;
282
283         if ( !sobj->curlen ) {
284                 int initlen = len;
285                 if ( len > sobj->buflen ) {
286                         if ( sobj->buflen < RECOMMEND_M( len ) )
287                                 initlen = sobj->buflen;
288                 }
289                 curitem = sobj->first;
290                 if ( initlen > 1 )
291                         qsort( nobjs, initlen, size, sobj->cmpr );
292                 ptr = (char*)nobjs; 
293                 initlen *= size;
294                 while( ptr - (char*)nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
295                         curitem->value = (void*)ptr;
296                         if ( sobj->curlen ) {
297                                 curitem->prev = curitem - 1;
298                                 curitem->prev->next = curitem;
299                         }
300                         curitem++;
301                         sobj->curlen++;
302                         ptr += size;
303                 }
304                 sobj->last = curitem-1;
305
306         } else {
307                 while( ( ptr - (char*)nobjs )/size < len &&  sobj->curlen != sobj->buflen ) {
308                         PS_insert( sobj, (void*)ptr ); /* buflen is very small, so we can use function call */ 
309                         ptr += size;
310                 }
311         }
312
313         len *= size;
314         while( ptr - (char*)nobjs < len ) {
315                 if ( (*(sobj->cmpr))( sobj->last->value, (void*)ptr ) > 0 ) {
316                         if ( sobj->buflen == 1 )
317                                 sobj->last->value = (void*)ptr;
318                         else 
319                                 insert_full( (void*)ptr );
320                 }
321                 ptr += size;
322         }
323
324         return 0;
325 }
326
327 /*
328  * init_iterator, return 0 if success
329  */
330 int 
331 PS_init_iterator( SORT* sobj, int start ) {
332         if ( sobj->curlen <= 0 || start<0 || start >= sobj->curlen )
333                 return 1;
334         sobj->curitem = sobj->first;
335         while ( start ) {
336                 sobj->curitem = sobj->curitem->next;
337                 start--;
338         }
339         return 0;
340
341
342 /*
343  * return next sorted value or NULL
344  */
345 void* 
346 PS_getnext( SORT* sobj ) {
347         void *value = NULL;
348         if ( sobj->curitem ) 
349                 value = sobj->curitem->value;
350         else 
351                 return NULL;
352
353         sobj->curitem =  ( sobj->curitem->next == NULL || sobj->curitem->next == sobj->first ) ? NULL : sobj->curitem->next; 
354
355         return value;
356 }
357
358 int
359 PS_number( SORT* sobj ) {
360         return sobj->curlen;
361 }
362