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 GListUnshift(GList *l, void *ptr) {
 108         return insertCell(l, NULL, makeCell(ptr));
 109 }
 110
 111 GList*
 112 GListDelete(GList *l, GListCell *c) {
 113         if (GLIST_LENGTH(l) <= 0)
 114                 return l;
 115
 116         if ( l->head == c ) {
 117                 tassert( c->prev == NULL );
 118                 l->head = c->next;
 119                 if ( l->head )
 120                         l->head->prev = NULL;
 121                 else
 122                         l->tail = NULL;
 123         } else if ( l->tail == c ) {
 124                 tassert( c->next == NULL );
 125                 l->tail = c->prev;
 126                 if ( l->tail )
 127                         l->tail->next = NULL;
 128                 else
 129                         l->head = NULL;
 130         } else {
 131                 c->prev->next = c->next;
 132                 c->next->prev = c->prev;
 133         }
 134
 135         c->prev = c->next = NULL;
 136
 137         l->length--;
 138
 139         return l;
 140 }
 141
 142 GListCell*
 143 GListPop(GList *l) {
 144         GListCell       *c = NULL;
 145
 146         if (GLIST_LENGTH(l) > 0) {
 147                 c = l->tail;
 148                 GListDelete(l, c);
 149         }
 150
 151         return c;
 152 }
 153
 154 GListCell*
 155 GListShift(GList *l) {
 156         GListCell       *c = NULL;
 157
 158         if (GLIST_LENGTH(l) > 0) {
 159                 c = l->head;
 160                 GListDelete(l, c);
 161         }
 162
 163         return c;
 164 }
 165
 166 GListCell*
 167 GListGet(GList *l, int n) {
 168         GListCell       *c;
 169
 170         GListForeach(c, l) {
 171                 if ( n-- == 0 )
 172                         return c;
 173         }
 174
 175         return NULL;
 176 }
 177
 178 GListCell*
 179 GListFind(GList *l, void *ptr) {
 180         GListCell    *c;
 181
 182         if ( l && l->cmpFunc ) {
 183                 GListForeach(c, l) {
 184                         if ( l->cmpFunc(ptr, c->data) == 0 )
 185                                 return c;
 186                 }
 187         } else {
 188                 GListForeach(c, l) {
 189                         if ( ptr == c->data )
 190                                 return c;
 191                 }
 192         }
 193
 194         return NULL;
 195 }
 196
 197 static GListCellComparator curComparator;
 198
 199 static int
 200 compareData( const void *a, const void *b ) {
 201         if ( *(void**)a == *(void**)b )
 202                 return 0;
 203         return curComparator( *(void**)a, *(void**)b );
 204 }
 205
 206 GList*
 207 GListSort(GList *l) {
 208         GListCell       *c;
 209         void    **arrptr, **array;
 210
 211         if (GLIST_LENGTH(l) <= 1)
 212                 return l;
 213
 214         tassert(l->cmpFunc != NULL);
 215
 216         arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
 217         GListForeach(c, l)
 218                 *arrptr++ = c->data;
 219
 220         tassert( arrptr - array == GLIST_LENGTH(l) );
 221
 222         curComparator = l->cmpFunc;
 223         qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData);
 224
 225         arrptr = array;
 226         GListForeach(c, l)
 227                 c->data = *arrptr++;
 228
 229         tfree(array);
 230
 231         return l;
 232 }
 233
 234 GList*
 235 GListUniq(GList *l) {
 236         GListCell   *c;
 237
 238         GListForeach(c, l) {
 239                 for(;;) {
 240                         GListCell       *next = c->next;
 241
 242                         if ( next == NULL )
 243                                 break;
 244
 245                         if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
 246                                 GListDelete( l, next );
 247                                 GListFreeCell( l, next );
 248                         } else
 249                                 break;
 250                 }
 251
 252         }
 253
 254         return l;
 255 }
 256
 257 void
 258 GListFree(GList *l) {
 259         GListCell   *c = GLIST_HEAD(l), *tmp;
 260
 261         while( c != NULL ) {
 262                 tmp = c->next;
 263                 GListFreeCell(l, c);
 264                 c = tmp;
 265         }
 266
 267         if (l)
 268                 tfree(l);
 269 }
 270
 271 void
 272 GListFreeCell(GList *l, GListCell* c) {
 273         if (l && l->freeFunc)
 274                 l->freeFunc(c->data);
 275
 276         tfree(c);
 277 }
 278
 279 GList*
 280 GListTruncate(GList *l, int n) {
 281         while( GLIST_LENGTH(l) > n ) {
 282                 GListCell       *c = l->tail;
 283
 284                 GListDelete(l, c);
 285                 GListFreeCell(l, c);
 286         }
 287
 288         checkGList(l);
 289         return l;
 290 }
 291
 292 GList*
 293 GListCopy(GList *l) {
 294         GList   *n = NULL;
 295         GListCell       *c;
 296
 297         GListForeach(c,l)
 298                 n = GListPush(n, c->data);
 299
 300         if ( n && l) {
 301                 n->cmpFunc = l->cmpFunc;
 302                 n->freeFunc = l->freeFunc;
 303         }
 304
 305         return n;
 306 }
 307
 308 GList*
 309 GListConcat(GList *l1, GList *l2) {
 310
 311         if ( l1 == l2 )
 312                 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
 313         if ( GLIST_LENGTH(l1) == 0 )
 314                 return l2;
 315         if ( GLIST_LENGTH(l2) == 0 ) {
 316                 GListFree(l2);
 317                 return l1;
 318         }
 319
 320         l1->tail->next = l2->head;
 321         l2->head->prev = l1->tail;
 322         l1->tail = l2->tail;
 323         l1->length += l2->length;
 324
 325         l2->head = l2->tail = NULL;
 326         l2->length=0;
 327         GListFree(l2);
 328
 329         return l1;
 330 }
 331
 332 GList*
 333 GListDifference(GList *l1, GList *l2) {
 334         GList   *l = NULL;
 335         GListCell       *c;
 336
 337         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 338                 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
 339
 340         if (GLIST_LENGTH(l2) == 0 )
 341                 return GListCopy(l1);
 342
 343         GListForeach(c,l1) {
 344                 if ( GListFind(l2, c->data) == NULL )
 345                         l = GListPush(l, c->data);
 346         }
 347
 348         return l;
 349 }
 350
 351 GList*
 352 GListUnion(GList *l1, GList *l2) {
 353         GList   *l = GListCopy(l1);
 354         GListCell       *c;
 355
 356         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 357                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
 358
 359         if (GLIST_LENGTH(l2) == 0 )
 360                 return l;
 361
 362         GListForeach(c,l2) {
 363                 if ( GListFind(l1, c->data) == NULL )
 364                         l = GListPush(l, c->data);
 365         }
 366
 367         return l;
 368 }
 369
 370 GList*
 371 GListIntersect(GList *l1, GList *l2) {
 372         GList   *l = checkGList(NULL);
 373         GListCell   *c;
 374
 375         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
 376                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
 377
 378         if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
 379                 return l;
 380
 381         GListForeach(c,l1) {
 382                 if ( GListFind(l2, c->data) != NULL )
 383                         l = GListPush(l, c->data);
 384         }
 385
 386         return l;
 387 }
 388
 389
 390
 391