GList - double linked abstract list implementation
[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*)t0malloc( sizeof(SORTITEM)*buflen );
115
116         sobj->buflen = buflen;
117         sobj->cmpr   = func;
118         sobj->free  = ffunc;
119         sobj->curlen = 0;
120
121         sobj->first = sobj->last = sobj->buf; 
122         sobj->curitem = NULL; 
123
124         return 0;
125 }
126
127 /*
128  * finish...
129  * clear memory
130  */
131 void  
132 PS_clear( SORT* sobj ) {
133         if ( sobj->free ) {
134                 int i;
135                 for(i=0; i<sobj->curlen; i++ )
136                         (*(sobj->free))( sobj->buf[i].value );
137         }
138         if ( sobj->buf ) 
139                 tfree( sobj->buf );
140         memset( (void*)sobj, 0, sizeof(SORT) );
141 }
142
143 /*
144  * Reset sort object..
145  */
146 void 
147 PS_reset( SORT* sobj ) {
148         int i;
149
150         if ( sobj->free ) {
151                 for(i=0; i<sobj->curlen; i++ )
152                         (*(sobj->free))( sobj->buf[i].value );
153         }
154         memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*sobj->buflen );
155         sobj->curlen = 0;
156         sobj->first = sobj->last = sobj->buf; 
157         sobj->curitem = NULL; 
158 }
159
160 /*
161  * Insert
162  */
163 int 
164 PS_insert( SORT* sobj, void* nobj ) {
165         SORTITEM *curitem, *previtem, *tmp;
166
167         /* first insertion */
168         if ( ! sobj->curlen  ) { 
169                 sobj->first->value = nobj;
170                 sobj->curlen++;
171                 return 1;
172         }
173
174         if ( sobj->curlen == sobj->buflen ) {
175                 if ( (*(sobj->cmpr))( sobj->last->value, nobj ) > 0 ) {
176                         if ( sobj->buflen == 1 ) {
177                                 if ( sobj->free ) 
178                                         (*(sobj->free))( sobj->last->value );
179                                 sobj->last->value = nobj;
180                         } else 
181                                 insert_full( nobj );
182                         return 1;
183                 }
184         } else {
185                 insert_notfull( nobj );
186                 sobj->curlen++;
187                 return 1;
188         }
189
190         return 0;
191 }
192
193 static compare_sort compareobject;
194 static int highlevelcompare( const void *a, const void *b ) {
195         return (*compareobject)(  *(void**)a, *(void**)b );     
196
197
198 /*
199  * Insert array, if defined free function, 
200  * unused item will be freeed
201  */
202
203 #define RECOMMEND_M(N)  ( ((N)<8000) ? ( 23.0+1.5*pow((N),0.6) ) : pow(( 8.05 * log((N)) - 53.53 ),2.0) )
204 void
205 PS_bulkinsert( SORT* sobj, void** nobjs, int len ) {
206         register SORTITEM *curitem, *tmp;
207         register void** ptr = nobjs;
208
209         if ( !sobj->curlen ) {
210                 int initlen = len;
211                 if ( len > sobj->buflen ) {
212                         if ( sobj->buflen < RECOMMEND_M( len ) )
213                                 initlen = sobj->buflen;
214                 }
215                 curitem = sobj->first;
216                 compareobject = sobj->cmpr;
217                 if ( initlen > 1 )
218                         qsort( nobjs, initlen, sizeof(void*), highlevelcompare );
219                 ptr = nobjs; 
220                 while( ptr - nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
221                         curitem->value = *ptr;
222                         if ( sobj->curlen ) {
223                                 curitem->prev = curitem - 1;
224                                 curitem->prev->next = curitem;
225                         }
226                         curitem++;
227                         sobj->curlen++;
228                         ptr++;
229                 }
230                 sobj->last = curitem-1;
231
232                 if ( sobj->free && initlen != sobj->buflen ) {
233                         while( ptr - nobjs < len ) { 
234                                 (*(sobj->free))( *ptr ); 
235                                 ptr++;
236                         }
237                         return;
238                 } 
239         } else {
240                 while( ptr - nobjs < len &&  sobj->curlen != sobj->buflen ) {
241                         PS_insert( sobj, *ptr ); /* buflen is very small, so we can use function call */ 
242                         ptr++;
243                 }
244         }
245
246         if ( sobj->free ) {
247                 while( ptr - nobjs < len ) {
248                         if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
249                                 if ( sobj->buflen == 1 ) {
250                                         (*(sobj->free))( sobj->last->value );
251                                         sobj->last->value = *ptr;
252                                 } else 
253                                         insert_full( *ptr );
254                         } else
255                                 (*(sobj->free))( *ptr );  
256                         ptr++;
257                 }
258         } else {
259                 while( ptr - nobjs < len ) {
260                         if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
261                                 if ( sobj->buflen == 1 )
262                                         sobj->last->value = *ptr;
263                                 else 
264                                         insert_full( *ptr );
265                         }
266                         ptr++;
267                 }
268         }
269
270
271 /*
272  * insert a-la qsort, require sobj->free = NULL
273  */
274 int 
275 PS_bulkplain( SORT* sobj, void* nobjs, int size, int len ) {
276         register SORTITEM *curitem, *tmp;
277         register char* ptr = (char*)nobjs;
278
279         if ( sobj->free )
280                 return 1;
281
282         if ( !sobj->curlen ) {
283                 int initlen = len;
284                 if ( len > sobj->buflen ) {
285                         if ( sobj->buflen < RECOMMEND_M( len ) )
286                                 initlen = sobj->buflen;
287                 }
288                 curitem = sobj->first;
289                 if ( initlen > 1 )
290                         qsort( nobjs, initlen, size, sobj->cmpr );
291                 ptr = (char*)nobjs; 
292                 initlen *= size;
293                 while( ptr - (char*)nobjs < initlen &&  sobj->curlen != sobj->buflen ) {
294                         curitem->value = (void*)ptr;
295                         if ( sobj->curlen ) {
296                                 curitem->prev = curitem - 1;
297                                 curitem->prev->next = curitem;
298                         }
299                         curitem++;
300                         sobj->curlen++;
301                         ptr += size;
302                 }
303                 sobj->last = curitem-1;
304
305         } else {
306                 while( ( ptr - (char*)nobjs )/size < len &&  sobj->curlen != sobj->buflen ) {
307                         PS_insert( sobj, (void*)ptr ); /* buflen is very small, so we can use function call */ 
308                         ptr += size;
309                 }
310         }
311
312         len *= size;
313         while( ptr - (char*)nobjs < len ) {
314                 if ( (*(sobj->cmpr))( sobj->last->value, (void*)ptr ) > 0 ) {
315                         if ( sobj->buflen == 1 )
316                                 sobj->last->value = (void*)ptr;
317                         else 
318                                 insert_full( (void*)ptr );
319                 }
320                 ptr += size;
321         }
322
323         return 0;
324 }
325
326 /*
327  * init_iterator, return 0 if success
328  */
329 int 
330 PS_init_iterator( SORT* sobj, int start ) {
331         if ( sobj->curlen <= 0 || start<0 || start >= sobj->curlen )
332                 return 1;
333         sobj->curitem = sobj->first;
334         while ( start ) {
335                 sobj->curitem = sobj->curitem->next;
336                 start--;
337         }
338         return 0;
339
340
341 /*
342  * return next sorted value or NULL
343  */
344 void* 
345 PS_getnext( SORT* sobj ) {
346         void *value = NULL;
347         if ( sobj->curitem ) 
348                 value = sobj->curitem->value;
349         else 
350                 return NULL;
351
352         sobj->curitem =  ( sobj->curitem->next == NULL || sobj->curitem->next == sobj->first ) ? NULL : sobj->curitem->next; 
353
354         return value;
355 }
356
357 int
358 PS_number( SORT* sobj ) {
359         return sobj->curlen;
360 }
361