glist.c

   1 /*
   2  * Copyright (c) 2006 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 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <unistd.h>
  32 #include <sys/types.h>
  33
  34 #include "tlog.h"
  35 #include "tmalloc.h"
  36
  37 #include "glist.h"
  38
  39 static GList*
  40 checkGList(GList *l) {
  41         if ( l==NULL )
  42                 l = t0malloc(sizeof(GList));
  43
  44         tassert( GLIST_LENGTH(l) >= 0 );
  45         tassert(
  46                 ( GLIST_LENGTH(l) == 0 && GLIST_HEAD(l) == NULL && GLIST_TAIL(l) == NULL ) ||
  47                 ( GLIST_LENGTH(l) > 0  && GLIST_HEAD(l) != NULL && GLIST_TAIL(l) != NULL )
  48         );
  49
  50         return l;
  51 }
  52
  53 static GListCell*
  54 makeCell(void *ptr) {
  55         GListCell       *cell = tmalloc(sizeof(GListCell));
  56         cell->data = ptr;
  57         return cell;
  58 }
  59
  60 static GList*
  61 insertCell(GList *l, GListCell *prev, GListCell *cell) {
  62         l = checkGList(l);
  63
  64         if ( prev == NULL ) {
  65                 /* insert into head */
  66                 if ( GLIST_LENGTH(l) == 0 ) {
  67                                 l->head = l->tail = cell;
  68                                 cell->next = cell->prev = NULL;
  69                 } else {
  70                         cell->next = l->head;
  71                         cell->prev = NULL;
  72                         l->head->prev = cell;
  73                         l->head = cell;
  74                 }
  75         } else if ( prev == l->tail ) {
  76                 /* insert into tail */
  77
  78                 tassert( GLIST_LENGTH(l) > 0 );
  79                 cell->next = NULL;
  80                 cell->prev = l->tail;
  81                 l->tail->next = cell;
  82                 l->tail = cell;
  83         } else {
  84                 tassert( GLIST_LENGTH(l) > 0 );
  85                 cell->next = prev->next;
  86                 cell->next->prev = cell;
  87                 cell->prev = prev;
  88                 prev->next = cell;
  89         }
  90
  91         l->length++;
  92
  93         return l;
  94 }
  95
  96 GList*
  97 GListInsert(GList *l, GListCell *prev, void *ptr) {
  98         return insertCell(l, prev, makeCell(ptr));
  99 }
 100
 101 GList*
 102 GListPush(GList *l, void *ptr) {
 103         return insertCell(l, GLIST_TAIL(l), makeCell(ptr));
 104 }
 105
 106 GList*
 107 GListPushCell(GList *l, GListCell* c) {
 108         return insertCell(l, GLIST_TAIL(l), c);
 109 }
 110
 111 GList*
 112 GListUnshift(GList *l, void *ptr) {
 113         return insertCell(l, NULL, makeCell(ptr));
 114 }
 115
 116 GList*
 117 GListUnshiftCell(GList *l, GListCell* c) {
 118         return insertCell(l, NULL, c);
 119 }
 120
 121 GList*
 122 GListDelete(GList *l, GListCell *c) {
 123         if (GLIST_LENGTH(l) <= 0)
 124                 return l;
 125
 126         if ( l->head == c ) {
 127                 tassert( c->prev == NULL );
 128                 l->head = c->next;
 129                 if ( l->head )
 130                         l->head->prev = NULL;
 131                 else
 132                         l->tail = NULL;
 133         } else if ( l->tail == c ) {
 134                 tassert( c->next == NULL );
 135                 l->tail = c->prev;
 136                 if ( l->tail )
 137                         l->tail->next = NULL;
 138                 else
 139                         l->head = NULL;
 140         } else {
 141                 c->prev->next = c->next;
 142                 c->next->prev = c->prev;
 143         }
 144
 145         c->prev = c->next = NULL;
 146
 147         l->length--;
 148
 149         return l;
 150 }
 151
 152 GListCell*
 153 GListPop(GList *l) {
 154         GListCell       *c = NULL;
 155
 156         if (GLIST_LENGTH(l) > 0) {
 157                 c = l->tail;
 158                 GListDelete(l, c);
 159         }
 160
 161         return c;
 162 }
 163
 164 GListCell*
 165 GListShift(GList *l) {
 166         GListCell       *c = NULL;
 167
 168         if (GLIST_LENGTH(l) > 0) {
 169                 c = l->head;
 170                 GListDelete(l, c);
 171         }
 172
 173         return c;
 174 }
 175
 176 GListCell*
 177 GListGet(GList *l, int n) {
 178         GListCell       *c;
 179
 180         GListForeach(c, l) {
 181                 if ( n-- == 0 )
 182                         return c;
 183         }
 184
 185         return NULL;
 186 }
 187
 188 GListCell*
 189 GListFind(GList *l, void *ptr) {
 190         GListCell    *c;
 191
 192         if ( l && l->cmpFunc ) {
 193                 GListForeach(c, l) {
 194                         if ( l->cmpFunc(ptr, c->data) == 0 )
 195                                 return c;
 196                 }
 197         } else {
 198                 GListForeach(c, l) {
 199                         if ( ptr == c->data )
 200                                 return c;
 201                 }
 202         }
 203
 204         return NULL;
 205 }
 206
 207 static GListCellComparator curComparator;
 208
 209 static int
 210 compareData( const void *a, const void *b ) {
 211         if ( *(void**)a == *(void**)b )
 212                 return 0;
 213         return curComparator( *(void**)a, *(void**)b );
 214 }
 215
 216 GList*
 217 GListSort(GList *l) {
 218         GListCell       *c;
 219         void    **arrptr, **array;
 220
 221         if (GLIST_LENGTH(l) <= 1)
 222                 return l;
 223
 224         tassert(l->cmpFunc != NULL);
 225
 226         arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
 227         GListForeach(c, l)
 228                 *arrptr++ = c->data;
 229
 230         tassert( arrptr - array == GLIST_LENGTH(l) );
 231
 232         curComparator = l->cmpFunc;
 233         qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData);
 234
 235         arrptr = array;
 236         GListForeach(c, l)
 237                 c->data = *arrptr++;
 238
 239         tfree(array);
 240
 241         return l;
 242 }
 243
 244 GList*
 245 GListUniq(GList *l) {
 246         GListCell   *c;
 247
 248         GListForeach(c, l) {
 249                 for(;;) {
 250                         GListCell       *next = c->next;
 251
 252                         if ( next == NULL )
 253                                 break;
 254
 255                         if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
 256                                 GListDelete( l, next );
 257                                 GListFreeCell( l, next );
 258                         } else
 259                                 break;
 260                 }
 261
 262         }
 263
 264         return l;
 265 }
 266
 267 void
 268 GListFree(GList *l) {
 269         GListCell   *c = GLIST_HEAD(l), *tmp;
 270
 271         while( c != NULL ) {
 272                 tmp = c->next;
 273                 GListFreeCell(l, c);
 274                 c = tmp;
 275         }
 276
 277         if (l)
 278                 tfree(l);
 279 }
 280
 281 void
 282 GListFreeCell(GList *l, GListCell* c) {
 283         if (l && l->freeFunc)
 284                 l->freeFunc(c->data);
 285
 286         tfree(c);
 287 }
 288
 289 GList*
 290 GListTruncate(GList *l, int n) {
 291         while( GLIST_LENGTH(l) > n ) {
 292                 GListCell       *c = l->tail;
 293
 294                 GListDelete(l, c);
 295                 GListFreeCell(l, c);
 296         }
 297
 298         return l;
 299 }
 300
 301 GList*
 302 GListCopy(GList *l) {
 303         GList   *n = NULL;
 304         GListCell       *c;
 305
 306         GListForeach(c,l)
 307                 n = GListPush(n, c->data);
 308
 309         if ( n && l) {
 310                 n->cmpFunc = l->cmpFunc;
 311                 n->freeFunc = l->freeFunc;
 312         }
 313
 314         return n;
 315 }
 316
 317 GList*
 318 GListConcat(GList *l1, GList *l2) {
 319
 320         if ( l1 == l2 )
 321                 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
 322         if ( GLIST_LENGTH(l1) == 0 )
 323                 return l2;
 324         if ( GLIST_LENGTH(l2) == 0 ) {
 325                 GListFree(l2);
 326                 return l1;
 327         }
 328
 329         l1->tail->next = l2->head;
 330         l2->head->prev = l1->tail;
 331         l1->tail = l2->tail;
 332         l1->length += l2->length;
 333
 334         l2->head = l2->tail = NULL;
 335         l2->length=0;
 336         GListFree(l2);
 337
 338         return l1;
 339 }
 340
 341 GList*
 342 GListDifference(GList *l1, GList *l2) {
 343         GList   *l = NULL;
 344         GListCell       *c;
 345
 346         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 347                 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
 348
 349         if (GLIST_LENGTH(l2) == 0 )
 350                 return GListCopy(l1);
 351
 352         GListForeach(c,l1) {
 353                 if ( GListFind(l2, c->data) == NULL )
 354                         l = GListPush(l, c->data);
 355         }
 356
 357         return l;
 358 }
 359
 360 GList*
 361 GListUnion(GList *l1, GList *l2) {
 362         GList   *l = GListCopy(l1);
 363         GListCell       *c;
 364
 365         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 366                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
 367
 368         if (GLIST_LENGTH(l2) == 0 )
 369                 return l;
 370
 371         GListForeach(c,l2) {
 372                 if ( GListFind(l1, c->data) == NULL )
 373                         l = GListPush(l, c->data);
 374         }
 375
 376         return l;
 377 }
 378
 379 GList*
 380 GListIntersect(GList *l1, GList *l2) {
 381         GList   *l = checkGList(NULL);
 382         GListCell   *c;
 383
 384         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 385                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
 386
 387         if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
 388                 return l;
 389
 390         GListForeach(c,l1) {
 391                 if ( GListFind(l2, c->data) != NULL )
 392                         l = GListPush(l, c->data);
 393         }
 394
 395         return l;
 396 }
 397
 398
 399
 400