LCOV - code coverage report
Current view: top level - tommyds/tommyds - tommylist.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 51 51 100.0 %
Date: 2018-04-02 17:50:51 Functions: 9 9 100.0 %

          Line data    Source code
       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           1 : tommy_inline void tommy_list_init(tommy_list* list)
     115             : {
     116           1 :         *list = 0;
     117           1 : }
     118             : 
     119             : /**
     120             :  * Gets the head of the list.
     121             :  * \return The head node. For empty lists 0 is returned.
     122             :  */
     123   539080512 : tommy_inline tommy_node* tommy_list_head(tommy_list* list)
     124             : {
     125   539080512 :         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           2 : tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
     133             : {
     134           2 :         tommy_node* head = tommy_list_head(list);
     135             : 
     136           2 :         if (!head)
     137           1 :                 return 0;
     138             : 
     139           1 :         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   246620975 : tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
     148             : {
     149             :         /* one element "circular" prev list */
     150   246620975 :         node->prev = node;
     151             : 
     152             :         /* one element "0 terminated" next list */
     153   246620975 :         node->next = 0;
     154             : 
     155   246620975 :         *list = node;
     156   246620975 : }
     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    42203071 : tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
     185             : {
     186             :         /* insert in the "circular" prev list */
     187    42203071 :         node->prev = head->prev;
     188    42203071 :         head->prev = node;
     189             : 
     190             :         /* insert in the "0 terminated" next list */
     191    42203071 :         node->next = 0;
     192    42203071 :         node->prev->next = node;
     193    42203071 : }
     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(tommy_list* list, tommy_node* node, void* data)
     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             :         node->data = data;
     210             : }
     211             : 
     212             : /**
     213             :  * Inserts an element at the tail of a list.
     214             :  * \param node The node to insert.
     215             :  * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
     216             :  */
     217   235492500 : tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
     218             : {
     219   235492500 :         tommy_node* head = tommy_list_head(list);
     220             : 
     221   235492500 :         if (head)
     222    40661607 :                 tommy_list_insert_tail_not_empty(head, node);
     223             :         else
     224   194830893 :                 tommy_list_insert_first(list, node);
     225             : 
     226   235492500 :         node->data = data;
     227   235492500 : }
     228             : 
     229             : /**
     230             :  * Removes an element from the list.
     231             :  * You must already have the address of the element to remove.
     232             :  * \note The node content is left unchanged, including the tommy_node::next
     233             :  * and tommy_node::prev fields that still contain pointers at the list.
     234             :  * \param node The node to remove. The node must be in the list.
     235             :  * \return The tommy_node::data field of the node removed.
     236             :  */
     237   233485002 : tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
     238             : {
     239   233485002 :         tommy_node* head = tommy_list_head(list);
     240             : 
     241             :         /* remove from the "circular" prev list */
     242   233485002 :         if (node->next)
     243    32256900 :                 node->next->prev = node->prev;
     244             :         else
     245   201228102 :                 head->prev = node->prev; /* the last */
     246             : 
     247             :         /* remove from the "0 terminated" next list */
     248   233485002 :         if (head == node)
     249   230826845 :                 *list = node->next; /* the new head, in case 0 */
     250             :         else
     251     2658157 :                 node->prev->next = node->next;
     252             : 
     253   233485002 :         return node->data;
     254             : }
     255             : 
     256             : /**
     257             :  * Concats two lists.
     258             :  * The second list is concatenated at the first list.
     259             :  * \param first The first list.
     260             :  * \param second The second list. After this call the list content is undefined,
     261             :  * and you should not use it anymore.
     262             :  */
     263    69976298 : tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
     264             : {
     265             :         tommy_node* first_head;
     266             :         tommy_node* first_tail;
     267             :         tommy_node* second_head;
     268             : 
     269             :         /* if the second is empty, nothing to do */
     270    69976298 :         second_head = tommy_list_head(second);
     271    69976298 :         if (second_head == 0)
     272    69849602 :                 return;
     273             : 
     274             :         /* if the first is empty, copy the second */
     275      126696 :         first_head = tommy_list_head(first);
     276      126696 :         if (first_head == 0) {
     277      123254 :                 *first = *second;
     278      123254 :                 return;
     279             :         }
     280             : 
     281             :         /* tail of the first list */
     282        3442 :         first_tail = first_head->prev;
     283             : 
     284             :         /* set the "circular" prev list */
     285        3442 :         first_head->prev = second_head->prev;
     286        3442 :         second_head->prev = first_tail;
     287             : 
     288             :         /* set the "0 terminated" next list */
     289        3442 :         first_tail->next = second_head;
     290             : }
     291             : 
     292             : /**
     293             :  * Sorts a list.
     294             :  * It's a stable merge sort with O(N*log(N)) worst complexity.
     295             :  * It's faster on degenerated cases like partially ordered lists.
     296             :  * \param cmp Compare function called with two elements.
     297             :  * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather.
     298             :  */
     299             : void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
     300             : 
     301             : /**
     302             :  * Checks if empty.
     303             :  * \return If the list is empty.
     304             :  */
     305           7 : tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
     306             : {
     307           7 :         return tommy_list_head(list) == 0;
     308             : }
     309             : 
     310             : /**
     311             :  * Gets the number of elements.
     312             :  * \note This operation is O(n).
     313             :  */
     314             : tommy_inline tommy_size_t tommy_list_count(tommy_list* list)
     315             : {
     316             :         tommy_size_t count = 0;
     317             :         tommy_node* i = tommy_list_head(list);
     318             : 
     319             :         while (i) {
     320             :                 ++count;
     321             :                 i = i->next;
     322             :         }
     323             : 
     324             :         return count;
     325             : }
     326             : 
     327             : /**
     328             :  * Calls the specified function for each element in the list.
     329             :  *
     330             :  * You cannot add or remove elements from the inside of the callback,
     331             :  * but can use it to deallocate them.
     332             :  *
     333             :  * \code
     334             :  * tommy_list list;
     335             :  *
     336             :  * // initializes the list
     337             :  * tommy_list_init(&list);
     338             :  *
     339             :  * ...
     340             :  *
     341             :  * // creates an object
     342             :  * struct object* obj = malloc(sizeof(struct object));
     343             :  *
     344             :  * ...
     345             :  *
     346             :  * // insert it in the list
     347             :  * tommy_list_insert_tail(&list, &obj->node, obj);
     348             :  *
     349             :  * ...
     350             :  *
     351             :  * // deallocates all the objects iterating the list
     352             :  * tommy_list_foreach(&list, free);
     353             :  * \endcode
     354             :  */
     355             : tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
     356             : {
     357             :         tommy_node* node = tommy_list_head(list);
     358             : 
     359             :         while (node) {
     360             :                 void* data = node->data;
     361             :                 node = node->next;
     362             :                 func(data);
     363             :         }
     364             : }
     365             : 
     366             : /**
     367             :  * Calls the specified function with an argument for each element in the list.
     368             :  */
     369             : tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
     370             : {
     371             :         tommy_node* node = tommy_list_head(list);
     372             : 
     373             :         while (node) {
     374             :                 void* data = node->data;
     375             :                 node = node->next;
     376             :                 func(arg, data);
     377             :         }
     378             : }
     379             : 
     380             : #endif
     381             : 

Generated by: LCOV version 1.13