src/list.cpp

   1 /*
   2  * list.cpp: a non-sucky linked list implementation
   3  *
   4  * Contact:
   5  *   Moonlight List (moonlight-list@lists.ximian.com)
   6  *
   7  * Copyright 2007 Novell, Inc. (http://www.novell.com)
   8  *
   9  * See the LICENSE file included with the distribution for details.
  10  */
  11
  12
  13 #include <config.h>
  14
  15 #include <glib.h>
  16 #include "list.h"
  17
  18
  19 List::Node::Node ()
  20 {
  21         next = NULL;
  22         prev = NULL;
  23 }
  24
  25
  26 List::List ()
  27 {
  28         length = 0;
  29         head = NULL;
  30         tail = NULL;
  31 }
  32
  33
  34 List::~List ()
  35 {
  36         Clear (true);
  37 }
  38
  39
  40 List::Node *
  41 List::First ()
  42 {
  43         return head;
  44 }
  45
  46
  47 List::Node *
  48 List::Last ()
  49 {
  50         return tail;
  51 }
  52
  53
  54 bool
  55 List::IsEmpty ()
  56 {
  57         return !head;
  58 }
  59
  60
  61 int
  62 List::Length ()
  63 {
  64         return length;
  65 }
  66
  67
  68 void
  69 List::Clear (bool freeNodes)
  70 {
  71         if (freeNodes) {
  72                 List::Node *n, *nn;
  73
  74                 n = head;
  75                 while (n) {
  76                         nn = n->next;
  77                         delete n;
  78                         n = nn;
  79                 }
  80         }
  81
  82         length = 0;
  83         head = NULL;
  84         tail = NULL;
  85 }
  86
  87
  88 List::Node *
  89 List::Append (List::Node *node)
  90 {
  91         node->prev = tail;
  92         node->next = NULL;
  93
  94         if (tail)
  95                 tail->next = node;
  96         else
  97                 head = node;
  98
  99         tail = node;
 100
 101         length++;
 102
 103         return node;
 104 }
 105
 106
 107 List::Node *
 108 List::Prepend (List::Node *node)
 109 {
 110         node->next = head;
 111         node->prev = NULL;
 112
 113         if (head)
 114                 head->prev = node;
 115         else
 116                 tail = node;
 117
 118         head = node;
 119
 120         length++;
 121
 122         return node;
 123 }
 124
 125
 126 List::Node *
 127 List::Insert (List::Node *node, int index)
 128 {
 129         List::Node *n = head;
 130         int i = 0;
 131
 132         if (head) {
 133                 while (n->next && i < index) {
 134                         n = n->next;
 135                         i++;
 136                 }
 137
 138                 if (i == index) {
 139                         // Inserting @node before @n
 140                         node->prev = n->prev;
 141                         node->next = n;
 142
 143                         if (n->prev)
 144                                 n->prev->next = node;
 145                         else
 146                                 head = node;
 147
 148                         n->prev = node;
 149                 } else {
 150                         // Inserting @node after @n (means @n was the tail)
 151                         tail = n->next = node;
 152                         node->prev = n;
 153                         node->next = NULL;
 154                 }
 155         } else {
 156                 // @node will be the only node in the list
 157                 head = tail = node;
 158                 node->next = NULL;
 159                 node->prev = NULL;
 160         }
 161
 162         length++;
 163
 164         return node;
 165 }
 166
 167 List::Node *
 168 List::InsertAfter (List::Node *node, List::Node *after)
 169 {
 170         if (after == NULL)
 171                 return Prepend (node);
 172
 173         node->next = after->next;
 174         node->prev = after;
 175         after->next = node;
 176
 177         if (node->next != NULL)
 178                 node->next->prev = node;
 179         else
 180                 tail = node;
 181
 182         length++;
 183
 184         return node;
 185 }
 186
 187 List::Node *
 188 List::InsertBefore (List::Node *node, List::Node *before)
 189 {
 190         if (before == NULL)
 191                 return Append (node);
 192
 193         node->next = before;
 194         node->prev = before->prev;
 195
 196         if (before->prev != NULL)
 197                 before->prev->next = node;
 198         else
 199                 head = node;
 200
 201         before->prev = node;
 202
 203         length++;
 204
 205         return node;
 206 }
 207
 208
 209 List::Node *
 210 List::Replace (List::Node *node, int index)
 211 {
 212         List::Node *n;
 213
 214         if (!(n = Index (index)))
 215                 return NULL;
 216
 217         node->next = n->next;
 218         node->prev = n->prev;
 219
 220         if (n->prev)
 221                 n->prev->next = node;
 222         else
 223                 head = node;
 224
 225         if (n->next)
 226                 n->next->prev = node;
 227         else
 228                 tail = node;
 229
 230         n->next = NULL;
 231         n->prev = NULL;
 232
 233         return n;
 234 }
 235
 236 List::Node *
 237 List::Find (NodeAction find, void *data)
 238 {
 239         List::Node *n = head;
 240
 241         if (!find)
 242                 return NULL;
 243
 244         while (n) {
 245                 if (find (n, data))
 246                         return n;
 247
 248                 n = n->next;
 249         }
 250
 251         return NULL;
 252 }
 253
 254
 255 void
 256 List::Remove (NodeAction find, void *data)
 257 {
 258         List::Node *n;
 259
 260         if ((n = Find (find, data))) {
 261                 Unlink (n);
 262                 delete n;
 263         }
 264 }
 265
 266 void
 267 List::Remove (List::Node *node)
 268 {
 269         Unlink (node);
 270         delete node;
 271 }
 272
 273 void
 274 List::RemoveAt (int index)
 275 {
 276         List::Node *node;
 277         if (!(node = Index (index)))
 278                 return;
 279
 280         Unlink (node);
 281         delete node;
 282 }
 283
 284 void
 285 List::Unlink (List::Node *node)
 286 {
 287         if (node->prev)
 288                 node->prev->next = node->next;
 289         else
 290                 head = node->next;
 291
 292         if (node->next)
 293                 node->next->prev = node->prev;
 294         else
 295                 tail = node->prev;
 296
 297         node->prev = NULL;
 298         node->next = NULL;
 299
 300         length--;
 301 }
 302
 303
 304 List::Node *
 305 List::Index (int index)
 306 {
 307         List::Node *n = head;
 308         int i = 0;
 309
 310         if (index < 0)
 311                 return NULL;
 312
 313         while (n && i < index) {
 314                 n = n->next;
 315                 i++;
 316         }
 317
 318         if (i == index)
 319                 return n;
 320
 321         return NULL;
 322 }
 323
 324 int
 325 List::IndexOf (List::Node *node)
 326 {
 327         List::Node *n = head;
 328         int i = 0;
 329
 330         while (n && n != node) {
 331                 n = n->next;
 332                 i++;
 333         }
 334
 335         return n == node ? i : -1;
 336 }
 337
 338
 339 int
 340 List::IndexOf (NodeAction find, void *data)
 341 {
 342         List::Node *n = head;
 343         int i = 0;
 344
 345         if (!find)
 346                 return -1;
 347
 348         while (n) {
 349                 if (find (n, data))
 350                         return i;
 351
 352                 n = n->next;
 353                 i++;
 354         }
 355
 356         return -1;
 357 }
 358
 359 void
 360 List::ForEach (NodeAction action, void *data)
 361 {
 362         List::Node *node = head;
 363         bool move = true;
 364
 365         if (!action)
 366                 return;
 367
 368         while (node && move) {
 369                 if (!action (node, data))
 370                         move = false;
 371                 else
 372                         node = node->next;
 373         }
 374 }
 375
 376
 377 Queue::Queue ()
 378 {
 379         pthread_mutex_init (&lock, NULL);
 380         list = new List ();
 381 }
 382
 383 Queue::~Queue ()
 384 {
 385         pthread_mutex_destroy (&lock);
 386         delete list;
 387 }
 388
 389 bool
 390 Queue::IsEmpty ()
 391 {
 392         bool empty;
 393
 394         Lock ();
 395         empty = list->IsEmpty ();
 396         Unlock ();
 397
 398         return empty;
 399 }
 400
 401 int
 402 Queue::Length ()
 403 {
 404         int length;
 405
 406         Lock ();
 407         length = list->Length ();
 408         Unlock ();
 409
 410         return length;
 411 }
 412
 413 void
 414 Queue::Clear (bool freeNodes)
 415 {
 416         Lock ();
 417         list->Clear (freeNodes);
 418         Unlock ();
 419 }
 420
 421 void
 422 Queue::Push (List::Node *node)
 423 {
 424         Lock ();
 425         list->Append (node);
 426         Unlock ();
 427 }
 428
 429 List::Node *
 430 Queue::Pop ()
 431 {
 432         List::Node *node;
 433
 434         Lock ();
 435         if ((node = list->First ()))
 436                 list->Unlink (node);
 437         Unlock ();
 438
 439         return node;
 440 }
 441
 442 void
 443 Queue::Lock ()
 444 {
 445         pthread_mutex_lock (&lock);
 446 }
 447
 448 void
 449 Queue::Unlock ()
 450 {
 451         pthread_mutex_unlock (&lock);
 452 }
 453
 454 List *
 455 Queue::LinkedList ()
 456 {
 457         return list;
 458 }
 459
 460
 461 /*
 462  * ArrayList
 463  */
 464
 465 ArrayList::ArrayList ()
 466 {
 467         array = NULL;
 468         size = 0;
 469         count = 0;
 470 }
 471
 472 ArrayList::~ArrayList ()
 473 {
 474         g_free (array);
 475 }
 476
 477 int
 478 ArrayList::GetCount ()
 479 {
 480         return count;
 481 }
 482
 483 void
 484 ArrayList::SetCount (int value)
 485 {
 486         EnsureCapacity (value);
 487         count = value;
 488 }
 489
 490 int
 491 ArrayList::GetCapacity ()
 492 {
 493         return size;
 494 }
 495
 496 void
 497 ArrayList::SetCapacity (int capacity)
 498 {
 499         if (capacity == size)
 500                 return;
 501
 502         array = (void **) g_realloc (array, sizeof (void *) * capacity);
 503
 504         for (int i = size; i < capacity; i++)
 505                 array [i] = NULL;
 506         size = capacity;
 507 }
 508
 509 void
 510 ArrayList::EnsureCapacity (int capacity)
 511 {
 512         if (size < capacity)
 513                 SetCapacity (capacity);
 514 }
 515
 516 int
 517 ArrayList::Add (void *item)
 518 {
 519         EnsureCapacity (count + 1);
 520         array [count] = item;
 521         return count++;
 522 }
 523
 524 void *&
 525 ArrayList::operator [] (int index)
 526 {
 527         return array [index];
 528 }
 529
 530
 531 //#define TEST_PROGRAM
 532 #ifdef TEST_PROGRAM
 533
 534 #include <stdio.h>
 535
 536 class IntNode : public List::Node {
 537 public:
 538         int id;
 539
 540         IntNode (int i) { id = i; }
 541 };
 542
 543
 544 static int
 545 IntNodeCompare (List::Node *n0, List::Node *n1)
 546 {
 547         IntNode *in0 = (IntNode *) n0;
 548         IntNode *in1 = (IntNode *) n1;
 549
 550         return in0->id - in1->id;
 551 }
 552
 553 static bool
 554 IntNodeFinder (List::Node *node, void *data)
 555 {
 556         int val = *((int *) data);
 557
 558         return ((IntNode *) node)->id == val;
 559 }
 560
 561
 562 int main (int argc, char **argv)
 563 {
 564         List::Node *node;
 565         List *list;
 566
 567         list = new List ();
 568
 569         node = list->Append (new IntNode (2));
 570         printf ("appended node with id = %d\n", ((IntNode *) node)->id);
 571         node = list->Append (new IntNode (4));
 572         printf ("appended node with id = %d\n", ((IntNode *) node)->id);
 573         node = list->Append (new IntNode (5));
 574         printf ("appended node with id = %d\n", ((IntNode *) node)->id);
 575         node = list->Insert (new IntNode (3), 1);
 576         printf ("inserted node with id = %d at index = %d\n",
 577                 ((IntNode *) node)->id, list->IndexOf (node));
 578         node = list->Prepend (new IntNode (1));
 579         printf ("prepended node with id = %d\n", ((IntNode *) node)->id);
 580         node = list->Prepend (new IntNode (0));
 581         printf ("prepended node with id = %d\n", ((IntNode *) node)->id);
 582         node = list->Insert (new IntNode (6), 6);
 583         printf ("inserted node with id = %d at index = %d\n",
 584                 ((IntNode *) node)->id, list->IndexOf (node));
 585
 586         printf ("\nlist contains (in order):\n");
 587         for (node = list->First (); node != NULL; node = node->next)
 588                 printf ("node id = %d\n", ((IntNode *) node)->id);
 589
 590         printf ("\nlist contains (in reverse order):\n");
 591         for (node = list->Last (); node != NULL; node = node->prev)
 592                 printf ("node id = %d\n", ((IntNode *) node)->id);
 593
 594         printf ("\nunlinking the last item in the list\n");
 595         list->Unlink (list->Last ());
 596
 597         printf ("\nlist contains (in order):\n");
 598         for (node = list->First (); node != NULL; node = node->next)
 599                 printf ("node id = %d\n", ((IntNode *) node)->id);
 600
 601         printf ("\nlist contains (in reverse order):\n");
 602         for (node = list->Last (); node != NULL; node = node->prev)
 603                 printf ("node id = %d\n", ((IntNode *) node)->id);
 604
 605         printf ("\nunlinking the first item in the list\n");
 606         list->Unlink (list->First ());
 607
 608         printf ("\nlist contains (in order):\n");
 609         for (node = list->First (); node != NULL; node = node->next)
 610                 printf ("node id = %d\n", ((IntNode *) node)->id);
 611
 612         printf ("\nlist contains (in reverse order):\n");
 613         for (node = list->Last (); node != NULL; node = node->prev)
 614                 printf ("node id = %d\n", ((IntNode *) node)->id);
 615
 616         printf ("\nreplacing 4 with 8\n");
 617         int id = 4;
 618         int index = list->IndexOf (IntNodeFinder, &id);
 619         if ((node = list->Replace (new IntNode (8), index)))
 620                 delete node;
 621         else
 622                 printf ("unsuccessful\n");
 623
 624         printf ("\nlist contains (in order):\n");
 625         for (node = list->First (); node != NULL; node = node->next)
 626                 printf ("node id = %d\n", ((IntNode *) node)->id);
 627
 628         printf ("\nlist contains (in reverse order):\n");
 629         for (node = list->Last (); node != NULL; node = node->prev)
 630                 printf ("node id = %d\n", ((IntNode *) node)->id);
 631
 632         printf ("\nremoving 5\n");
 633         id = 5;
 634         list->Remove (IntNodeFinder, &id);
 635
 636         printf ("\nlist contains (in order):\n");
 637         for (node = list->First (); node != NULL; node = node->next)
 638                 printf ("node id = %d\n", ((IntNode *) node)->id);
 639
 640         printf ("\nlist contains (in reverse order):\n");
 641         for (node = list->Last (); node != NULL; node = node->prev)
 642                 printf ("node id = %d\n", ((IntNode *) node)->id);
 643
 644         printf ("\nremoving 1\n");
 645         id = 1;
 646         list->Remove (IntNodeFinder, &id);
 647
 648         printf ("\nlist contains (in order):\n");
 649         for (node = list->First (); node != NULL; node = node->next)
 650                 printf ("node id = %d\n", ((IntNode *) node)->id);
 651
 652         printf ("\nlist contains (in reverse order):\n");
 653         for (node = list->Last (); node != NULL; node = node->prev)
 654                 printf ("node id = %d\n", ((IntNode *) node)->id);
 655
 656         list->Clear (true);
 657         delete list;
 658
 659         return 0;
 660 }
 661
 662 #endif /* TEST_PROGRAM */