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