code_c/Maasha/src/lib/list.c

   1 /* Martin Asser Hansen (mail@maasha.dk) Copyright (C) 2008 - All right reserved */
   2
   3 #include "common.h"
   4 #include "mem.h"
   5 #include "list.h"
   6
   7
   8 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> SINGLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
   9
  10
  11 list_sl *list_sl_new()
  12 {
  13     /* Martin A. Hansen, August 2008 */
  14
  15     /* Initialize a new singly linked list. */
  16
  17     list_sl *new_list = NULL;
  18
  19     new_list = mem_get( sizeof( list_sl ) );
  20
  21     new_list->first = NULL;
  22
  23     return new_list;
  24 }
  25
  26
  27 node_sl *node_sl_new()
  28 {
  29     /* Martin A. Hansen, September 2008 */
  30
  31     /* Initialize a new singly linked list node. */
  32
  33     node_sl *new_node = NULL;
  34
  35     new_node = mem_get( sizeof( node_sl ) );
  36
  37     new_node->next = NULL;
  38     new_node->val  = NULL;
  39
  40     return new_node;
  41 }
  42
  43
  44 void list_sl_add_beg( list_sl **list_ppt, node_sl **node_ppt )
  45 {
  46     /* Martin A. Hansen, August 2008 */
  47
  48     /* Add a new node to the beginning of a singly linked list. */
  49
  50     list_sl *list_pt = *list_ppt;
  51     node_sl *node_pt = *node_ppt;
  52
  53     node_pt->next  = list_pt->first;
  54     list_pt->first = node_pt;
  55 }
  56
  57
  58 void list_sl_add_after( node_sl **node_ppt, node_sl **new_node_ppt )
  59 {
  60     /* Martin A. Hansen, August 2008 */
  61
  62     /* Add a new node after a given node of a singly linked list. */
  63
  64     node_sl *node_pt     = *node_ppt;
  65     node_sl *new_node_pt = *new_node_ppt;
  66
  67     new_node_pt->next = node_pt->next;
  68     node_pt->next     = new_node_pt;
  69 }
  70
  71
  72 void list_sl_remove_beg( list_sl **list_ppt )
  73 {
  74     /* Martin A. Hansen, August 2008 */
  75
  76     /* Remove the first node of a singly linked list. */
  77
  78     list_sl *list_pt  = *list_ppt;
  79     node_sl *old_node = NULL;
  80
  81     old_node       = list_pt->first;
  82     list_pt->first = list_pt->first->next;
  83
  84     mem_free( &old_node );
  85 }
  86
  87
  88 void list_sl_remove_after( node_sl **node_ppt )
  89 {
  90     /* Martin A. Hansen, August 2008 */
  91
  92     /* Remove the node next to this one in a singly linked list. */
  93
  94     node_sl *node_pt  = *node_ppt;
  95     node_sl *old_node = NULL;
  96
  97     old_node      = node_pt->next;
  98     node_pt->next = node_pt->next->next;
  99
 100     mem_free( &old_node );
 101 }
 102
 103
 104 void list_sl_print( list_sl *list_pt )
 105 {
 106     /* Martin A. Hansen, August 2008 */
 107
 108     /* Debug function to print all elements from a singly linked list. */
 109
 110     node_sl *node = NULL;
 111
 112     for ( node = list_pt->first; node != NULL; node = node->next ) {
 113         node_sl_print( node );
 114     }
 115 }
 116
 117
 118 void node_sl_print( node_sl *node_pt )
 119 {
 120     /* Martin A. Hansen, September 2008 */
 121
 122     /* Debug funtion to print a singly linked list node. */
 123
 124     printf( "node_sl->val: %s\n", ( char * ) node_pt->val );
 125 }
 126
 127
 128 void list_sl_sort( list_sl **list_ppt, int ( *compare )( const void *a, const void *b ) )
 129 {
 130     /* Martin A. Hansen, September 2008 */
 131
 132     /* Sort a singly linked list according to the compare function. */
 133
 134     list_sl  *list       = *list_ppt;
 135     node_sl **node_array = NULL;        /* array of pointers to nodes */
 136     node_sl  *node       = NULL;
 137     node_sl  *old_node   = NULL;
 138     size_t    count      = 0;
 139     size_t    i          = 0;
 140
 141     count = list_count( list );
 142
 143     if ( count > 1 )
 144     {
 145         node_array = mem_get( count * sizeof( *node_array ) );
 146
 147         for ( node = list->first, i = 0; node != NULL; node = node->next, i++ ) {
 148             node_array[ i ] = node;
 149         }
 150
 151         qsort( node_array, count, sizeof( node_array[ 0 ] ), compare );
 152
 153         list->first = NULL;
 154
 155         node = node_array[ 0 ];
 156
 157         list_sl_add_beg( &list, &node );
 158
 159         old_node = node;
 160
 161         for ( i = 1; i < count; i++ )
 162         {
 163             node = node_array[ i ];
 164
 165             list_sl_add_after( &old_node, &node );
 166
 167             old_node = node;
 168         }
 169
 170         *list_ppt = list;
 171
 172         mem_free( &node_array );
 173     }
 174 }
 175
 176
 177 void list_sl_destroy( list_sl **list_ppt )
 178 {
 179     /* Martin A. Hansen, August 2008 */
 180
 181     /* Free memory for all nodes in and including the singly linked list. */
 182
 183     list_sl *list_pt = *list_ppt;
 184     node_sl *next    = list_pt->first;
 185     node_sl *node    = NULL;
 186
 187     while ( next != NULL )
 188     {
 189         node = next;
 190         next = node->next;
 191
 192         mem_free( &node );
 193     }
 194
 195     mem_free( &list_pt );
 196
 197     *list_ppt = NULL;
 198 }
 199
 200
 201 void node_sl_destroy( node_sl **node_ppt )
 202 {
 203     /* Martin A. Hansen, September 2008 */
 204
 205     /* Free memory for singly linked list node and value. */
 206
 207     node_sl *node = *node_ppt;
 208
 209     mem_free( &node->val );
 210     mem_free( &node );
 211
 212     *node_ppt = NULL;
 213 }
 214
 215
 216 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DOUBLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 217
 218
 219 list_dl *list_dl_new()
 220 {
 221     /* Martin A. Hansen, August 2008 */
 222
 223     /* Initialize a new doubly linked list. */
 224
 225     list_dl *new_list = NULL;
 226
 227     new_list = mem_get( sizeof( list_dl ) );
 228
 229     new_list->first = NULL;
 230     new_list->last  = NULL;
 231
 232     return new_list;
 233 }
 234
 235
 236 node_dl *node_dl_new()
 237 {
 238     /* Martin A. Hansen, September 2008 */
 239
 240     /* Initialize a new doubly linked list node. */
 241
 242     node_dl *new_node = NULL;
 243
 244     new_node = mem_get( sizeof( node_dl ) );
 245
 246     new_node->next = NULL;
 247     new_node->prev = NULL;
 248     new_node->val  = NULL;
 249
 250     return new_node;
 251 }
 252
 253
 254 void list_dl_add_beg( list_dl **list_ppt, node_dl **node_ppt )
 255 {
 256     /* Martin A. Hansen, August 2008 */
 257
 258     /* Add a new node to the beginning of a doubly linked list. */
 259
 260     list_dl *list_pt = *list_ppt;
 261     node_dl *node_pt = *node_ppt;
 262
 263     if ( list_pt->first == NULL )
 264     {
 265         list_pt->first = node_pt;
 266         list_pt->last  = node_pt;
 267         node_pt->next  = NULL;
 268         node_pt->prev  = NULL;
 269     }
 270     else
 271     {
 272         list_dl_add_before( &list_pt, &list_pt->first, &node_pt );
 273     }
 274 }
 275
 276
 277 void list_dl_add_end( list_dl **list_ppt, node_dl **node_ppt )
 278 {
 279     /* Martin A. Hansen, August 2008 */
 280
 281     /* Add a new node to the end of a doubly linked list. */
 282
 283     list_dl *list_pt = *list_ppt;
 284     node_dl *node_pt = *node_ppt;
 285
 286     if ( list_pt->last == NULL ) {
 287         list_dl_add_beg( &list_pt, &node_pt );
 288     } else {
 289         list_dl_add_after( &list_pt, &list_pt->last, &node_pt );
 290     }
 291 }
 292
 293
 294 void list_dl_add_before( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt )
 295 {
 296     /* Martin A. Hansen, August 2008 */
 297
 298     /* Add a new node before a given node of a doubly linked list. */
 299
 300     list_dl *list_pt     = *list_ppt;
 301     node_dl *node_pt     = *node_ppt;
 302     node_dl *new_node_pt = *new_node_ppt;
 303
 304     new_node_pt->prev = node_pt->prev;
 305     new_node_pt->next = node_pt;
 306
 307     if ( node_pt->prev == NULL ) {
 308         list_pt->first = new_node_pt;
 309     } else {
 310         node_pt->prev->next = new_node_pt;
 311     }
 312
 313     node_pt->prev = new_node_pt;
 314 }
 315
 316
 317 void list_dl_add_after( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt )
 318 {
 319     /* Martin A. Hansen, August 2008 */
 320
 321     /* Add a new node after a given node of a doubly linked list. */
 322
 323     list_dl *list_pt     = *list_ppt;
 324     node_dl *node_pt     = *node_ppt;
 325     node_dl *new_node_pt = *new_node_ppt;
 326
 327     new_node_pt->prev = node_pt;
 328     new_node_pt->next = node_pt->next;
 329
 330     if ( node_pt->next == NULL ) {
 331         list_pt->last = new_node_pt;
 332     } else {
 333         node_pt->next->prev = new_node_pt;
 334     }
 335
 336     node_pt->next = new_node_pt;
 337 }
 338
 339
 340 void list_dl_remove( list_dl **list_ppt, node_dl **node_ppt )
 341 {
 342     /* Martin A. Hansen, August 2008 */
 343
 344     /* Remove a node from a doubly linked list. */
 345
 346     list_dl *list_pt = *list_ppt;
 347     node_dl *node_pt = *node_ppt;
 348
 349     if ( node_pt->prev == NULL ) {
 350         list_pt->first = node_pt->next;
 351     } else {
 352         node_pt->prev->next = node_pt->next;
 353     }
 354
 355     if ( node_pt->next == NULL ) {
 356         list_pt->last = node_pt->prev;
 357     } else {
 358         node_pt->next->prev = node_pt->prev;
 359     }
 360
 361     mem_free( &node_pt );
 362
 363 //    *node_ppt = NULL;
 364 }
 365
 366
 367 void list_dl_print( list_dl *list_pt )
 368 {
 369     /* Martin A. Hansen, August 2008 */
 370
 371     /* Debug function to print all elements from a doubly linked list. */
 372
 373     node_dl *node = NULL;
 374
 375     for ( node = list_pt->first; node != NULL; node = node->next ) {
 376         node_dl_print( node );
 377     }
 378 }
 379
 380
 381 void node_dl_print( node_dl *node_pt )
 382 {
 383     /* Martin A. Hansen, September 2008 */
 384
 385     /* Debug funtion to print a doubly linked list node. */
 386
 387     printf( "node_dl->val: %s\n", ( char * ) node_pt->val );
 388 }
 389
 390
 391 void list_dl_destroy( list_dl **list_ppt )
 392 {
 393     /* Martin A. Hansen, August 2008 */
 394
 395     /* Free memory for all nodes in and including the doubly linked list. */
 396
 397     list_dl *list_pt = *list_ppt;
 398     node_dl *next    = list_pt->first;
 399     node_dl *node    = NULL;
 400
 401     while ( next != NULL )
 402     {
 403         node = next;
 404         next = node->next;
 405
 406         mem_free( &node );
 407     }
 408
 409     mem_free( &list_pt );
 410
 411     *list_ppt = NULL;
 412 }
 413
 414
 415 void node_dl_destroy( node_dl **node_ppt )
 416 {
 417     /* Martin A. Hansen, September 2008 */
 418
 419     /* Free memory for doubly linked list node and value. */
 420
 421     node_dl *node = *node_ppt;
 422
 423     mem_free( &node->val );
 424     mem_free( &node );
 425
 426     *node_ppt = NULL;
 427 }
 428
 429
 430 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> GENERIC LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 431
 432
 433 size_t list_count( void *list_pt )
 434 {
 435     /* Martin A. Hansen, September 2008 */
 436
 437     /* Returns the number of nodes in a linked list. */
 438
 439     list_sl *list  = ( list_sl * ) list_pt;
 440     node_sl *node  = NULL;
 441     size_t   count = 0;
 442
 443     for ( node = list->first; node != NULL; node = node->next ) {
 444         count++;
 445     }
 446
 447     return count;
 448 }
 449
 450
 451 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ASSORTED SORTING FUNCTIOS <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 452
 453
 454 int cmp_list_sl_char_asc( const void *a, const void *b )
 455 {
 456     /* Martin A. Hansen, September 2008 */
 457
 458     /* Compare function for use with list_sl_sort(). */
 459     /* Sort in ascending order according to char node values. */
 460
 461     node_sl *a_node = *( ( node_sl ** ) a );
 462     node_sl *b_node = *( ( node_sl ** ) b );
 463
 464     return strcmp( ( char * ) a_node->val, ( char * ) b_node->val );
 465 }
 466
 467
 468 int cmp_list_sl_char_desc( const void *a, const void *b )
 469 {
 470     /* Martin A. Hansen, September 2008 */
 471
 472     /* Compare function for use with list_sl_sort(). */
 473     /* Sort in descending order according to char node values. */
 474
 475     node_sl *a_node = *( ( node_sl ** ) a );
 476     node_sl *b_node = *( ( node_sl ** ) b );
 477
 478     return strcmp( ( char * ) b_node->val, ( char * ) a_node->val );
 479 }
 480
 481
 482 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/