workspace/ksysguard/CContLib/ccont.c

   1 /*
   2     Lightweight C Container Library
   3
   4         Copyright (c) 2002 Tobias Koenig <tokoe@kde.org>
   5
   6         Original code was written by Chris Schlaeger <cs@kde.org>
   7
   8     This library is free software; you can redistribute it and/or
   9     modify it under the terms of the GNU Library General Public
  10     License as published by the Free Software Foundation; either
  11     version 2 of the License, or (at your option) any later version.
  12
  13     This library is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16     Library General Public License for more details.
  17
  18     You should have received a copy of the GNU Library General Public License
  19     along with this library; see the file COPYING.LIB.  If not, write to
  20     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21     Boston, MA 02110-1301, USA.
  22
  23 */
  24
  25 #include "ccont.h"
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <assert.h>
  30
  31 struct container_info {
  32         INDEX count;
  33         CONTAINER currentNode;
  34 };
  35
  36 typedef struct container_info T_CONTAINER_INFO;
  37 typedef struct container_info* CONTAINER_INFO;
  38
  39 #define rpterr(x) fprintf(stderr, "%s\n", x)
  40
  41 CONTAINER new_ctnr(void)
  42 {
  43         CONTAINER_INFO info;
  44         CONTAINER rootNode;
  45
  46         rootNode = (CONTAINER)malloc(sizeof(T_CONTAINER));
  47
  48         info = (CONTAINER_INFO)malloc(sizeof(T_CONTAINER_INFO));
  49         info->count = 0;
  50         info->currentNode = rootNode;
  51
  52         rootNode->next = rootNode;
  53         rootNode->prev = rootNode;
  54         rootNode->data = info;
  55
  56         return rootNode;
  57 }
  58
  59 /* O(n) */
  60 void zero_destr_ctnr(CONTAINER rootNode, DESTR_FUNC destr_func)
  61 {
  62         INDEX counter;
  63
  64         if (rootNode == NIL || destr_func == NIL) {
  65                 rpterr("destr_ctnr: NIL argument");
  66                 return;
  67         }
  68
  69         for (counter = level_ctnr(rootNode); counter > -1; --counter)
  70                 destr_func(pop_ctnr(rootNode));
  71
  72         assert(rootNode->data);
  73         free(rootNode->data);
  74
  75         free(rootNode);
  76         rootNode = 0;
  77
  78         return;
  79 }
  80
  81 /* O(n) */
  82 void empty_ctnr(CONTAINER rootNode)
  83 {
  84         INDEX i;
  85
  86         if (rootNode == NIL) {
  87                 rpterr("empty_ctnr: NIL argument");
  88                 return;
  89         }
  90
  91         for ( i = level_ctnr( rootNode ); i >= 0; --i )
  92                 free( pop_ctnr( rootNode ) );
  93
  94         return;
  95 }
  96
  97 /* O(1) */
  98 INDEX level_ctnr(CONTAINER rootNode)
  99 {
 100         if (rootNode == NIL) {
 101                 rpterr("level_ctnr: NIL argument");
 102                 return -1;
 103         }
 104
 105         return ((CONTAINER_INFO)rootNode->data)->count;
 106 }
 107
 108 /* This function is never used */
 109 /* O(n) */
 110 void insert_ctnr(CONTAINER rootNode, void* object, INDEX pos)
 111 {
 112         CONTAINER it;
 113         INDEX counter = 0;
 114
 115         if (rootNode == NIL || object == NIL) {
 116                 rpterr("insert_ctnr: NIL argument");
 117                 return;
 118         }
 119
 120         for (it = rootNode->next; it != rootNode; it = it->next) {
 121                 if (counter == pos) {
 122                         CONTAINER newNode = (CONTAINER)malloc(sizeof(T_CONTAINER));
 123
 124                         newNode->prev = it;
 125                         newNode->next = it->next;
 126                         it->next->prev = newNode;
 127                         it->next = newNode;
 128
 129                         newNode->data = object;
 130                         ((CONTAINER_INFO)rootNode->data)->count++;
 131                         return;
 132                 }
 133
 134                 counter++;
 135         }
 136 }
 137
 138 /* O(1) */
 139 void push_ctnr(CONTAINER rootNode, void* object)
 140 {
 141         CONTAINER newNode;
 142
 143         if (rootNode == NIL || object == NIL) {
 144                 rpterr("push_ctnr: NIL argument");
 145                 return;
 146         }
 147
 148         newNode = (CONTAINER)malloc(sizeof(T_CONTAINER));
 149         newNode->next = rootNode;
 150         newNode->prev = rootNode->prev;
 151         rootNode->prev->next = newNode;
 152         rootNode->prev = newNode;
 153
 154         newNode->data = object;
 155         ((CONTAINER_INFO)rootNode->data)->count++;
 156 }
 157
 158 /* This function is never used */
 159 /* O(n) */
 160 void* remove_at_ctnr(CONTAINER rootNode, INDEX pos)
 161 {
 162         CONTAINER it;
 163         INDEX counter = 0;
 164         void* retval;
 165
 166         if (rootNode == NIL) {
 167                 rpterr("remove_ctnr: NIL argument");
 168                 return NIL;
 169         }
 170
 171         for (it = rootNode->next; it != rootNode; it = it->next) {
 172                 if (counter == pos) {
 173                         retval = it->data;
 174
 175                         it->prev->next = it->next;
 176                         it->next->prev = it->prev;
 177
 178                         free(it);
 179
 180                         ((CONTAINER_INFO)rootNode->data)->count--;
 181                         return retval;
 182                 }
 183
 184                 counter++;
 185         }
 186
 187         return NIL;
 188 }
 189
 190 /* This function is only used within ccont.c */
 191 /* O(1) */
 192 void* pop_ctnr(CONTAINER rootNode)
 193 {
 194         CONTAINER ptr;
 195         void* retval;
 196
 197         if (rootNode == NIL) {
 198                 rpterr("pop_ctnr: NIL argument");
 199                 return NIL;
 200         }
 201
 202         if (rootNode->next == rootNode)
 203                 return NIL;
 204
 205         ptr = rootNode->next;
 206         retval = ptr->data;
 207
 208         rootNode->next = ptr->next;
 209         ptr->next->prev = rootNode;
 210
 211         ((CONTAINER_INFO)rootNode->data)->count--;
 212
 213         free(ptr);
 214
 215         return retval;
 216 }
 217
 218 /* O(n) */
 219 void* get_ctnr(CONTAINER rootNode, INDEX pos)
 220 {
 221         CONTAINER it;
 222         INDEX counter = 0;
 223
 224         if (rootNode == NIL) {
 225                 rpterr("get_ctnr: NIL argument");
 226                 return NIL;
 227         }
 228
 229         for (it = rootNode->next; it != rootNode; it = it->next) {
 230                 if (counter == pos)
 231                         return it->data;
 232
 233                 counter++;
 234         }
 235
 236         return NIL;
 237 }
 238
 239 /* This should return a reference to the node found instead of its index.
 240    The index is never used, except as an argument to a O(n) function to
 241    get a reference to the node. */
 242 /* O(n) */
 243 INDEX search_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func, void* pattern)
 244 {
 245         CONTAINER it;
 246         INDEX counter = 0;
 247
 248         if (rootNode == NIL || compare_func == NIL || pattern == NIL) {
 249                 rpterr("search_ctnr: NIL argument");
 250                 return -1;
 251         }
 252
 253         for (it = rootNode->next; it != rootNode; it = it->next) {
 254                 if (compare_func(pattern, it->data) == 0)
 255                         return counter;
 256
 257                 counter++;
 258         }
 259
 260         return -1;
 261 }
 262
 263 /* This function is never used */
 264 /* O(n) */
 265 void swap_ctnr(CONTAINER rootNode, INDEX pos1, INDEX pos2)
 266 {
 267         CONTAINER it, node1 = 0, node2 = 0;
 268         INDEX counter = 0;
 269         int found = 0;
 270         void* tmpData;
 271
 272         if (rootNode == NIL) {
 273                 rpterr("swap_ctnr: NIL argument");
 274                 return;
 275         }
 276
 277         if (pos1 == pos2)
 278                 return;
 279
 280         for (it = rootNode->next; it != rootNode; it = it->next) {
 281                 if (counter == pos1) {
 282                         node1 = it;
 283                         found++;
 284                         if (found == 2)
 285                                 break;
 286                 }
 287                 if (counter == pos2) {
 288                         node2 = it;
 289                         found++;
 290                         if (found == 2)
 291                                 break;
 292                 }
 293
 294                 counter++;
 295         }
 296
 297         if (found == 2) {
 298                 tmpData = node1->data;
 299                 node1->data = node2->data;
 300                 node2->data = tmpData;
 301         }
 302 }
 303
 304 /* O(n log n) */
 305 void bsort_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func)
 306 {
 307         /* Use mergesort adapted from http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c */
 308
 309         CONTAINER p, q, e, tail, oldhead;
 310         INDEX insize, nmerges, psize, qsize, i;
 311
 312         if (rootNode == NIL || compare_func == NIL) {
 313                 rpterr("bsort_ctnr: NIL argument");
 314                 return;
 315         }
 316
 317         if (level_ctnr(rootNode) == 0) {
 318                 /* Nothing to sort */
 319                 return;
 320         }
 321
 322         insize = 1;
 323
 324         while (1) {
 325                 p = rootNode->next;
 326                 oldhead = rootNode;       /* only used for circular linkage */
 327                 rootNode->next = NULL;
 328                 tail = NULL;
 329
 330                 nmerges = 0;  /* count number of merges we do in this pass */
 331
 332                 while (p) {
 333                         nmerges++;  /* there exists a merge to be done */
 334                         /* step `insize' places along from p */
 335                         q = p;
 336                         psize = 0;
 337                         for (i = 0; i < insize; i++) {
 338                                 psize++;
 339                                 q = (q->next == oldhead ? NULL : q->next);
 340                                 if (!q) break;
 341                         }
 342
 343                         /* if q hasn't fallen off end, we have two lists to merge */
 344                         qsize = insize;
 345
 346                         /* now we have two lists; merge them */
 347                         while (psize > 0 || (qsize > 0 && q)) {
 348                                 /* decide whether next element of merge comes from p or q */
 349                                 if (psize == 0) {
 350                                         assert(q);
 351                                         /* p is empty; e must come from q. */
 352                                         e = q; q = q->next; qsize--;
 353                                         if (q == oldhead) q = NULL;
 354                                 } else if (qsize == 0 || !q) {
 355                                         assert(p);
 356                                         /* q is empty; e must come from p. */
 357                                         e = p; p = p->next; psize--;
 358                                         if (p == oldhead) p = NULL;
 359                                 } else if (compare_func(p,q) <= 0) {
 360                                         /* First element of p is lower (or same);
 361                                          * e must come from p. */
 362                                         e = p; p = p->next; psize--;
 363                                         if (p == oldhead) p = NULL;
 364                                 } else {
 365                                         /* First element of q is lower; e must come from q. */
 366                                         e = q; q = q->next; qsize--;
 367                                         if (q == oldhead) q = NULL;
 368                                 }
 369
 370                                 /* add the next element to the merged list */
 371                                 if (tail) {
 372                                         tail->next = e;
 373                                         e->prev = tail;
 374                                 } else {
 375                                         rootNode->next = e;
 376                                         e->prev = rootNode;
 377                                 }
 378
 379                                 tail = e;
 380                         }
 381
 382                         /* now p has stepped `insize' places along, and q has too */
 383                         p = q;
 384                 }
 385
 386                 if (tail)
 387                         tail->next = rootNode;
 388                 rootNode->prev = tail;
 389
 390                 /* If we have done only one merge, we're finished. */
 391                 if (nmerges <= 1) {  /* allow for nmerges==0, the empty list case */
 392                         break;
 393                 }
 394
 395                 /* Otherwise repeat, merging lists twice the size */
 396                 insize *= 2;
 397         }
 398 }
 399
 400 /* O(1) */
 401 void* first_ctnr(CONTAINER rootNode)
 402 {
 403         if (rootNode == NIL) {
 404                 rpterr("first_ctnr: NIL argument");
 405                 return NIL;
 406         }
 407
 408         if (rootNode->next == rootNode)
 409                 return NIL;
 410
 411         ((CONTAINER_INFO)rootNode->data)->currentNode = rootNode->next;
 412
 413         return rootNode->next->data;
 414 }
 415
 416 /* O(1) */
 417 void* next_ctnr(CONTAINER rootNode)
 418 {
 419         CONTAINER_INFO info;
 420
 421         if (rootNode == NIL) {
 422                 rpterr("next_ctnr: NIL argument");
 423                 return NIL;
 424         }
 425
 426         info = (CONTAINER_INFO)rootNode->data;
 427
 428         if (info->currentNode->next == rootNode)
 429                 return NIL;
 430
 431         info->currentNode = info->currentNode->next;
 432
 433         return info->currentNode->data;
 434 }
 435
 436 /* O(1) */
 437 void* remove_ctnr(CONTAINER rootNode)
 438 {
 439         CONTAINER currentNode, tmp;
 440         CONTAINER_INFO info;
 441         void* retval;
 442
 443         if (rootNode == NIL) {
 444                 rpterr("remove_curr_ctnr: NIL argument");
 445                 return NIL;
 446         }
 447
 448         info = (CONTAINER_INFO)rootNode->data;
 449         currentNode = info->currentNode;
 450
 451         if (currentNode == rootNode) { /* should never happen */
 452                 rpterr("remove_curr_ctnr: delete root node");
 453                 return NIL;
 454         }
 455
 456         retval = currentNode->data;
 457         tmp = currentNode->prev;
 458
 459         currentNode->prev->next = currentNode->next;
 460         currentNode->next->prev = currentNode->prev;
 461
 462         free(currentNode);
 463
 464         info->count--;
 465         info->currentNode = tmp;
 466
 467         return retval;
 468 }