2 * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
39 * this defines only for faster code
41 #define insert_full(val) do { \
44 (*(sobj->free))( tmp->value ); \
45 sobj->last = sobj->last->prev; /* current last */ \
47 curitem = sobj->last; \
48 curitem->next = tmp->prev = tmp->next = NULL; \
51 if ( (*(sobj->cmpr))( curitem->value, (val) ) <= 0 ) { \
52 tmp->next = curitem->next; \
53 tmp->prev = curitem; \
55 if ( curitem->next ) /* not last */ \
56 curitem->next->prev = tmp; \
59 curitem->next = tmp; \
62 curitem = curitem->prev; \
63 } while ( curitem ); \
64 /* insert to first position */ \
66 sobj->first->prev = tmp; \
67 tmp->next = sobj->first; \
72 #define insert_notfull( val ) do { \
73 tmp = &(sobj->buf[sobj->curlen]); \
76 curitem = sobj->first; \
78 if ( (*(sobj->cmpr))( curitem->value, tmp->value ) > 0 ) { \
79 tmp->next = curitem; \
80 curitem->prev = tmp; \
81 tmp->prev = previtem; \
83 previtem->next = tmp; \
85 sobj->first->prev = tmp; \
91 curitem = curitem->next; \
93 if ( ! tmp->next ) { /*not inserted*/ \
94 sobj->last->next = tmp; \
95 tmp->prev = sobj->last; \
104 * If input options are invalid, return -1
105 * if no memory return 1
106 * If success return 0
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;
114 sobj->buf = (SORTITEM*)tmalloc( sizeof(SORTITEM)*buflen );
116 memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*buflen );
117 sobj->buflen = buflen;
122 sobj->first = sobj->last = sobj->buf;
123 sobj->curitem = NULL;
133 PS_clear( SORT* sobj ) {
136 for(i=0; i<sobj->curlen; i++ )
137 (*(sobj->free))( sobj->buf[i].value );
141 memset( (void*)sobj, 0, sizeof(SORT) );
145 * Reset sort object..
148 PS_reset( SORT* sobj ) {
152 for(i=0; i<sobj->curlen; i++ );
153 (*(sobj->free))( sobj->buf[i].value );
155 memset( (void*)sobj->buf, 0, sizeof(SORTITEM)*sobj->buflen );
157 sobj->first = sobj->last = sobj->buf;
158 sobj->curitem = NULL;
165 PS_insert( SORT* sobj, void* nobj ) {
166 SORTITEM *curitem, *previtem, *tmp;
168 /* first insertion */
169 if ( ! sobj->curlen ) {
170 sobj->first->value = nobj;
175 if ( sobj->curlen == sobj->buflen ) {
176 if ( (*(sobj->cmpr))( sobj->last->value, nobj ) > 0 ) {
177 if ( sobj->buflen == 1 ) {
179 (*(sobj->free))( sobj->last->value );
180 sobj->last->value = nobj;
186 insert_notfull( nobj );
194 static compare_sort compareobject;
195 static int highlevelcompare( const void *a, const void *b ) {
196 return (*compareobject)( *(void**)a, *(void**)b );
200 * Insert array, if defined free function,
201 * unused item will be freeed
204 #define RECOMMEND_M(N) ( ((N)<8000) ? ( 23.0+1.5*pow((N),0.6) ) : pow(( 8.05 * log((N)) - 53.53 ),2.0) )
206 PS_bulkinsert( SORT* sobj, void** nobjs, int len ) {
207 register SORTITEM *curitem, *tmp;
208 register void** ptr = nobjs;
210 if ( !sobj->curlen ) {
212 if ( len > sobj->buflen ) {
213 if ( sobj->buflen < RECOMMEND_M( len ) )
214 initlen = sobj->buflen;
216 curitem = sobj->first;
217 compareobject = sobj->cmpr;
219 qsort( nobjs, initlen, sizeof(void*), highlevelcompare );
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;
231 sobj->last = curitem-1;
233 if ( sobj->free && initlen != sobj->buflen ) {
234 while( ptr - nobjs < len ) {
235 (*(sobj->free))( *ptr );
241 while( ptr - nobjs < len && sobj->curlen != sobj->buflen ) {
242 PS_insert( sobj, *ptr ); /* buflen is very small, so we can use function call */
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;
256 (*(sobj->free))( *ptr );
260 while( ptr - nobjs < len ) {
261 if ( (*(sobj->cmpr))( sobj->last->value, *ptr ) > 0 ) {
262 if ( sobj->buflen == 1 )
263 sobj->last->value = *ptr;
273 * insert a-la qsort, require sobj->free = NULL
276 PS_bulkplain( SORT* sobj, void* nobjs, int size, int len ) {
277 register SORTITEM *curitem, *tmp;
278 register char* ptr = (char*)nobjs;
283 if ( !sobj->curlen ) {
285 if ( len > sobj->buflen ) {
286 if ( sobj->buflen < RECOMMEND_M( len ) )
287 initlen = sobj->buflen;
289 curitem = sobj->first;
291 qsort( nobjs, initlen, size, sobj->cmpr );
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;
304 sobj->last = curitem-1;
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 */
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;
319 insert_full( (void*)ptr );
328 * init_iterator, return 0 if success
331 PS_init_iterator( SORT* sobj, int start ) {
332 if ( sobj->curlen <= 0 || start<0 || start >= sobj->curlen )
334 sobj->curitem = sobj->first;
336 sobj->curitem = sobj->curitem->next;
343 * return next sorted value or NULL
346 PS_getnext( SORT* sobj ) {
349 value = sobj->curitem->value;
353 sobj->curitem = ( sobj->curitem->next == NULL || sobj->curitem->next == sobj->first ) ? NULL : sobj->curitem->next;
359 PS_number( SORT* sobj ) {