tommyDS_hashlin/tommylist.h

   1 /*
   2  * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  19  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  20  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  21  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  22  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  23  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  24  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  25  * POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /** \file
  29  * Double linked list for collisions into hashtables.
  30  *
  31  * This list is a double linked list mainly targetted for handling collisions
  32  * into an hashtables, but useable also as a generic list.
  33  *
  34  * The main feature of this list is to require only one pointer to represent the
  35  * list, compared to a classic implementation requiring a head an a tail pointers.
  36  * This reduces the memory usage in hashtables.
  37  *
  38  * Another feature is to support the insertion at the end of the list. This allow to store
  39  * collisions in a stable order. Where for stable order we mean that equal elements keep
  40  * their insertion order.
  41  *
  42  * To initialize the list, you have to call tommy_list_init(), or to simply assign
  43  * to it NULL, as an empty list is represented by the NULL value.
  44  *
  45  * \code
  46  * tommy_list list;
  47  *
  48  * tommy_list_init(&list); // initializes the list
  49  * \endcode
  50  *
  51  * To insert elements in the list you have to call tommy_list_insert_tail()
  52  * or tommy_list_insert_head() for each element.
  53  * In the insertion call you have to specify the address of the node and the
  54  * address of the object.
  55  * The address of the object is used to initialize the tommy_node::data field
  56  * of the node.
  57  *
  58  * \code
  59  * struct object {
  60  *     int value;
  61  *     // other fields
  62  *     tommy_node node;
  63  * };
  64  *
  65  * struct object* obj = malloc(sizeof(struct object)); // creates the object
  66  *
  67  * obj->value = ...; // initializes the object
  68  *
  69  * tommy_list_insert_tail(&list, &obj->node, obj); // inserts the object
  70  * \endcode
  71  *
  72  * To iterate over all the elements in the list you have to call
  73  * tommy_list_head() to get the head of the list and follow the
  74  * tommy_node::next pointer until NULL.
  75  *
  76  * \code
  77  * tommy_node* i = tommy_list_head(&list);
  78  * while (i) {
  79  *     struct object* obj = i->data; // gets the object pointer
  80  *
  81  *     printf("%d\n", obj->value); // process the object
  82  *
  83  *     i = i->next; // go to the next element
  84  * }
  85  * \endcode
  86  *
  87  * To destroy the list you have to remove all the elements,
  88  * as the list is completely inplace and it doesn't allocate memory.
  89  * This can be done with the tommy_list_foreach() function.
  90  *
  91  * \code
  92  * // deallocates all the objects iterating the list
  93  * tommy_list_foreach(&list, free);
  94  * \endcode
  95  */
  96
  97 #ifndef __TOMMYLIST_H
  98 #define __TOMMYLIST_H
  99
 100 #include "tommytypes.h"
 101
 102 /******************************************************************************/
 103 /* list */
 104
 105 /**
 106  * Double linked list type.
 107  */
 108 typedef tommy_node* tommy_list;
 109
 110 /**
 111  * Initializes the list.
 112  * The list is completely inplace, so it doesn't need to be deinitialized.
 113  */
 114 tommy_inline void tommy_list_init(tommy_list* list)
 115 {
 116         *list = 0;
 117 }
 118
 119 /**
 120  * Gets the head of the list.
 121  * \return The head node. For empty lists 0 is returned.
 122  */
 123 tommy_inline tommy_node* tommy_list_head(tommy_list* list)
 124 {
 125         return *list;
 126 }
 127
 128 /**
 129  * Gets the tail of the list.
 130  * \return The tail node. For empty lists 0 is returned.
 131  */
 132 tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
 133 {
 134         tommy_node* head = tommy_list_head(list);
 135
 136         if (!head)
 137                 return 0;
 138
 139         return head->prev;
 140 }
 141
 142 /** \internal
 143  * Creates a new list with a single element.
 144  * \param list The list to initialize.
 145  * \param node The node to insert.
 146  */
 147 tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
 148 {
 149         /* one element "circular" prev list */
 150         node->prev = node;
 151
 152         /* one element "0 terminated" next list */
 153         node->next = 0;
 154
 155         *list = node;
 156 }
 157
 158 /** \internal
 159  * Inserts an element at the head of a not empty list.
 160  * The element is inserted at the head of the list. The list cannot be empty.
 161  * \param list The list. The list cannot be empty.
 162  * \param node The node to insert.
 163  */
 164 tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
 165 {
 166         tommy_node* head = tommy_list_head(list);
 167
 168         /* insert in the "circular" prev list */
 169         node->prev = head->prev;
 170         head->prev = node;
 171
 172         /* insert in the "0 terminated" next list */
 173         node->next = head;
 174
 175         *list = node;
 176 }
 177
 178 /** \internal
 179  * Inserts an element at the tail of a not empty list.
 180  * The element is inserted at the tail of the list. The list cannot be empty.
 181  * \param head The node at the list head. It cannot be 0.
 182  * \param node The node to insert.
 183  */
 184 tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
 185 {
 186         /* insert in the "circular" prev list */
 187         node->prev = head->prev;
 188         head->prev = node;
 189
 190         /* insert in the "0 terminated" next list */
 191         node->next = 0;
 192         node->prev->next = node;
 193 }
 194
 195 /**
 196  * Inserts an element at the head of a list.
 197  * \param node The node to insert.
 198  * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
 199  */
 200 tommy_inline void tommy_list_insert_head_check(tommy_list* list, tommy_node* node)
 201 {
 202         tommy_node* head = tommy_list_head(list);
 203
 204         if (head)
 205                 tommy_list_insert_head_not_empty(list, node);
 206         else
 207                 tommy_list_insert_first(list, node);
 208 }
 209
 210 /**
 211  * Inserts an element at the tail of a list.
 212  * \param node The node to insert.
 213  * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
 214  */
 215 tommy_inline void tommy_list_insert_tail_check(tommy_list* list, tommy_node* node)
 216 {
 217         tommy_node* head = tommy_list_head(list);
 218
 219         if (head)
 220                 tommy_list_insert_tail_not_empty(head, node);
 221         else
 222                 tommy_list_insert_first(list, node);
 223 }
 224
 225 /**
 226  * Inserts an element at the head of a list and sets the data.
 227  * \param node The node to insert.
 228  * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
 229  */
 230 tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
 231 {
 232         tommy_list_insert_head_check(list, node);
 233
 234         node->data = data;
 235 }
 236
 237 /**
 238  * Inserts an element at the tail of a list and sets the data.
 239  * \param node The node to insert.
 240  * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
 241  */
 242 tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
 243 {
 244         tommy_list_insert_tail_check(list, node);
 245
 246         node->data = data;
 247 }
 248
 249 /**
 250  * Removes an element from the list.
 251  * You must already have the address of the element to remove.
 252  * \note The node content is left unchanged, including the tommy_node::next
 253  * and tommy_node::prev fields that still contain pointers at the list.
 254  * \param node The node to remove. The node must be in the list.
 255  * \return The tommy_node::data field of the node removed.
 256  */
 257 tommy_inline void tommy_list_remove_existing(tommy_list* list, tommy_node* node)
 258 {
 259         tommy_node* head = tommy_list_head(list);
 260
 261         /* remove from the "circular" prev list */
 262         if (node->next)
 263                 node->next->prev = node->prev;
 264         else
 265                 head->prev = node->prev; /* the last */
 266
 267         /* remove from the "0 terminated" next list */
 268         if (head == node)
 269                 *list = node->next; /* the new head, in case 0 */
 270         else
 271                 node->prev->next = node->next;
 272 }
 273
 274 /**
 275  * Concats two lists.
 276  * The second list is concatenated at the first list.
 277  * \param first The first list.
 278  * \param second The second list. After this call the list content is undefined,
 279  * and you should not use it anymore.
 280  */
 281 tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
 282 {
 283         tommy_node* first_head;
 284         tommy_node* first_tail;
 285         tommy_node* second_head;
 286
 287         /* if the second is empty, nothing to do */
 288         second_head = tommy_list_head(second);
 289         if (second_head == 0)
 290                 return;
 291
 292         /* if the first is empty, copy the second */
 293         first_head = tommy_list_head(first);
 294         if (first_head == 0) {
 295                 *first = *second;
 296                 return;
 297         }
 298
 299         /* tail of the first list */
 300         first_tail = first_head->prev;
 301
 302         /* set the "circular" prev list */
 303         first_head->prev = second_head->prev;
 304         second_head->prev = first_tail;
 305
 306         /* set the "0 terminated" next list */
 307         first_tail->next = second_head;
 308 }
 309
 310 /**
 311  * Sorts a list.
 312  * It's a stable merge sort with O(N*log(N)) worst complexity.
 313  * It's faster on degenerated cases like partially ordered lists.
 314  * \param cmp Compare function called with two elements.
 315  * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather.
 316  */
 317 void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
 318
 319 /**
 320  * Checks if empty.
 321  * \return If the list is empty.
 322  */
 323 tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
 324 {
 325         return tommy_list_head(list) == 0;
 326 }
 327
 328 /**
 329  * Gets the number of elements.
 330  * \note This operation is O(n).
 331  */
 332 tommy_inline tommy_size_t tommy_list_count(tommy_list* list)
 333 {
 334         tommy_size_t count = 0;
 335         tommy_node* i = tommy_list_head(list);
 336
 337         while (i) {
 338                 ++count;
 339                 i = i->next;
 340         }
 341
 342         return count;
 343 }
 344
 345 /**
 346  * Calls the specified function for each element in the list.
 347  *
 348  * You cannot add or remove elements from the inside of the callback,
 349  * but can use it to deallocate them.
 350  *
 351  * \code
 352  * tommy_list list;
 353  *
 354  * // initializes the list
 355  * tommy_list_init(&list);
 356  *
 357  * ...
 358  *
 359  * // creates an object
 360  * struct object* obj = malloc(sizeof(struct object));
 361  *
 362  * ...
 363  *
 364  * // insert it in the list
 365  * tommy_list_insert_tail(&list, &obj->node, obj);
 366  *
 367  * ...
 368  *
 369  * // deallocates all the objects iterating the list
 370  * tommy_list_foreach(&list, free);
 371  * \endcode
 372  */
 373 tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
 374 {
 375         tommy_node* node = tommy_list_head(list);
 376
 377         while (node) {
 378                 void* data = node->data;
 379                 node = node->next;
 380                 func(data);
 381         }
 382 }
 383
 384 /**
 385  * Calls the specified function with an argument for each element in the list.
 386  */
 387 tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
 388 {
 389         tommy_node* node = tommy_list_head(list);
 390
 391         while (node) {
 392                 void* data = node->data;
 393                 node = node->next;
 394                 func(arg, data);
 395         }
 396 }
 397
 398 #endif
 399