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