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 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DOUBLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 202
 203
 204 list_dl *list_dl_new()
 205 {
 206     /* Martin A. Hansen, August 2008 */
 207
 208     /* Initialize a new doubly linked list. */
 209
 210     list_dl *new_list = NULL;
 211
 212     new_list = mem_get( sizeof( list_dl ) );
 213
 214     new_list->first = NULL;
 215     new_list->last  = NULL;
 216
 217     return new_list;
 218 }
 219
 220
 221 node_dl *node_dl_new()
 222 {
 223     /* Martin A. Hansen, September 2008 */
 224
 225     /* Initialize a new doubly linked list node. */
 226
 227     node_dl *new_node = NULL;
 228
 229     new_node = mem_get( sizeof( node_dl ) );
 230
 231     new_node->next = NULL;
 232     new_node->prev = NULL;
 233     new_node->val  = NULL;
 234
 235     return new_node;
 236 }
 237
 238
 239 void list_dl_add_beg( list_dl **list_ppt, node_dl **node_ppt )
 240 {
 241     /* Martin A. Hansen, August 2008 */
 242
 243     /* Add a new node to the beginning of a doubly linked list. */
 244
 245     list_dl *list_pt = *list_ppt;
 246     node_dl *node_pt = *node_ppt;
 247
 248     if ( list_pt->first == NULL )
 249     {
 250         list_pt->first = node_pt;
 251         list_pt->last  = node_pt;
 252         node_pt->next  = NULL;
 253         node_pt->prev  = NULL;
 254     }
 255     else
 256     {
 257         list_dl_add_before( &list_pt, &list_pt->first, &node_pt );
 258     }
 259 }
 260
 261
 262 void list_dl_add_end( list_dl **list_ppt, node_dl **node_ppt )
 263 {
 264     /* Martin A. Hansen, August 2008 */
 265
 266     /* Add a new node to the end of a doubly linked list. */
 267
 268     list_dl *list_pt = *list_ppt;
 269     node_dl *node_pt = *node_ppt;
 270
 271     if ( list_pt->last == NULL ) {
 272         list_dl_add_beg( &list_pt, &node_pt );
 273     } else {
 274         list_dl_add_after( &list_pt, &list_pt->last, &node_pt );
 275     }
 276 }
 277
 278
 279 void list_dl_add_before( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt )
 280 {
 281     /* Martin A. Hansen, August 2008 */
 282
 283     /* Add a new node before a given node of a doubly linked list. */
 284
 285     list_dl *list_pt     = *list_ppt;
 286     node_dl *node_pt     = *node_ppt;
 287     node_dl *new_node_pt = *new_node_ppt;
 288
 289     new_node_pt->prev = node_pt->prev;
 290     new_node_pt->next = node_pt;
 291
 292     if ( node_pt->prev == NULL ) {
 293         list_pt->first = new_node_pt;
 294     } else {
 295         node_pt->prev->next = new_node_pt;
 296     }
 297
 298     node_pt->prev = new_node_pt;
 299 }
 300
 301
 302 void list_dl_add_after( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt )
 303 {
 304     /* Martin A. Hansen, August 2008 */
 305
 306     /* Add a new node after a given node of a doubly linked list. */
 307
 308     list_dl *list_pt     = *list_ppt;
 309     node_dl *node_pt     = *node_ppt;
 310     node_dl *new_node_pt = *new_node_ppt;
 311
 312     new_node_pt->prev = node_pt;
 313     new_node_pt->next = node_pt->next;
 314
 315     if ( node_pt->next == NULL ) {
 316         list_pt->last = new_node_pt;
 317     } else {
 318         node_pt->next->prev = new_node_pt;
 319     }
 320
 321     node_pt->next = new_node_pt;
 322 }
 323
 324
 325 void list_dl_remove( list_dl **list_ppt, node_dl **node_ppt )
 326 {
 327     /* Martin A. Hansen, August 2008 */
 328
 329     /* Remove a node from a doubly linked list. */
 330
 331     list_dl *list_pt = *list_ppt;
 332     node_dl *node_pt = *node_ppt;
 333
 334     if ( node_pt->prev == NULL ) {
 335         list_pt->first = node_pt->next;
 336     } else {
 337         node_pt->prev->next = node_pt->next;
 338     }
 339
 340     if ( node_pt->next == NULL ) {
 341         list_pt->last = node_pt->prev;
 342     } else {
 343         node_pt->next->prev = node_pt->prev;
 344     }
 345
 346     mem_free( &node_pt );
 347
 348 //    *node_ppt = NULL;
 349 }
 350
 351
 352 void list_dl_print( list_dl *list_pt )
 353 {
 354     /* Martin A. Hansen, August 2008 */
 355
 356     /* Debug function to print all elements from a doubly linked list. */
 357
 358     node_dl *node = NULL;
 359
 360     for ( node = list_pt->first; node != NULL; node = node->next ) {
 361         node_dl_print( node );
 362     }
 363 }
 364
 365
 366 void node_dl_print( node_dl *node_pt )
 367 {
 368     /* Martin A. Hansen, September 2008 */
 369
 370     /* Debug funtion to print a doubly linked list node. */
 371
 372     printf( "node_dl->val: %s\n", ( char * ) node_pt->val );
 373 }
 374
 375
 376 void list_dl_destroy( list_dl **list_ppt )
 377 {
 378     /* Martin A. Hansen, August 2008 */
 379
 380     /* Free memory for all nodes in and including the doubly linked list. */
 381
 382     list_dl *list_pt = *list_ppt;
 383     node_dl *next    = list_pt->first;
 384     node_dl *node    = NULL;
 385
 386     while ( next != NULL )
 387     {
 388         node = next;
 389         next = node->next;
 390
 391         mem_free( &node );
 392     }
 393
 394     mem_free( &list_pt );
 395
 396     *list_ppt = NULL;
 397 }
 398
 399
 400 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> GENERIC LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 401
 402
 403 size_t list_count( void *list_pt )
 404 {
 405     /* Martin A. Hansen, September 2008 */
 406
 407     /* Returns the number of nodes in a linked list. */
 408
 409     list_sl *list  = ( list_sl * ) list_pt;
 410     node_sl *node  = NULL;
 411     size_t   count = 0;
 412
 413     for ( node = list->first; node != NULL; node = node->next ) {
 414         count++;
 415     }
 416
 417     return count;
 418 }
 419
 420
 421 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ASSORTED SORTING FUNCTIOS <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
 422
 423
 424 int cmp_list_sl_char_asc( const void *a, const void *b )
 425 {
 426     /* Martin A. Hansen, September 2008 */
 427
 428     /* Compare function for use with list_sl_sort(). */
 429     /* Sort in ascending order according to char node values. */
 430
 431     node_sl *a_node = *( ( node_sl ** ) a );
 432     node_sl *b_node = *( ( node_sl ** ) b );
 433
 434     return strcmp( ( char * ) a_node->val, ( char * ) b_node->val );
 435 }
 436
 437
 438 int cmp_list_sl_char_desc( const void *a, const void *b )
 439 {
 440     /* Martin A. Hansen, September 2008 */
 441
 442     /* Compare function for use with list_sl_sort(). */
 443     /* Sort in descending order according to char node values. */
 444
 445     node_sl *a_node = *( ( node_sl ** ) a );
 446     node_sl *b_node = *( ( node_sl ** ) b );
 447
 448     return strcmp( ( char * ) b_node->val, ( char * ) a_node->val );
 449 }
 450
 451
 452 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/