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