LCOV - code coverage report
Current view: top level - tommyds - tommylist.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 65 65 100.0 %
Date: 2017-11-06 22:14:04 Functions: 11 11 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       11929 : tommy_inline void tommy_list_init(tommy_list* list)
     115             : {
     116       11929 :         *list = 0;
     117       11929 : }
     118             : 
     119             : /**
     120             :  * Gets the head of the list.
     121             :  * \return The head node. For empty lists 0 is returned.
     122             :  */
     123    25358302 : tommy_inline tommy_node* tommy_list_head(tommy_list* list)
     124             : {
     125    25358302 :         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    23435424 : tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
     148             : {
     149             :         /* one element "circular" prev list */
     150    23435424 :         node->prev = node;
     151             : 
     152             :         /* one element "0 terminated" next list */
     153    23435424 :         node->next = 0;
     154             : 
     155    23435424 :         *list = node;
     156    23435424 : }
     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    11044827 : tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
     185             : {
     186             :         /* insert in the "circular" prev list */
     187    11044827 :         node->prev = head->prev;
     188    11044827 :         head->prev = node;
     189             : 
     190             :         /* insert in the "0 terminated" next list */
     191    11044827 :         node->next = 0;
     192    11044827 :         node->prev->next = node;
     193    11044827 : }
     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    18395051 : tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
     218             : {
     219    18395051 :         tommy_node* head = tommy_list_head(list);
     220             : 
     221    18395051 :         if (head)
     222     9156460 :                 tommy_list_insert_tail_not_empty(head, node);
     223             :         else
     224     9238591 :                 tommy_list_insert_first(list, node);
     225             : 
     226    18395051 :         node->data = data;
     227    18395051 : }
     228             : 
     229             : /** \internal
     230             :  * Removes an element from the head of a not empty list.
     231             :  * \param list The list. The list cannot be empty.
     232             :  * \return The node removed.
     233             :  */
     234             : tommy_inline tommy_node* tommy_list_remove_head_not_empty(tommy_list* list)
     235             : {
     236             :         tommy_node* head = tommy_list_head(list);
     237             : 
     238             :         /* remove from the "circular" prev list */
     239             :         head->next->prev = head->prev;
     240             : 
     241             :         /* remove from the "0 terminated" next list */
     242             :         *list = head->next; /* the new head, in case 0 */
     243             : 
     244             :         return head;
     245             : }
     246             : 
     247             : /**
     248             :  * Removes an element from the list.
     249             :  * You must already have the address of the element to remove.
     250             :  * \note The node content is left unchanged, including the tommy_node::next
     251             :  * and tommy_node::prev fields that still contain pointers at the list.
     252             :  * \param node The node to remove. The node must be in the list.
     253             :  * \return The tommy_node::data field of the node removed.
     254             :  */
     255      353399 : tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
     256             : {
     257      353399 :         tommy_node* head = tommy_list_head(list);
     258             : 
     259             :         /* remove from the "circular" prev list */
     260      353399 :         if (node->next)
     261      118100 :                 node->next->prev = node->prev;
     262             :         else
     263      235299 :                 head->prev = node->prev; /* the last */
     264             : 
     265             :         /* remove from the "0 terminated" next list */
     266      353399 :         if (head == node)
     267      249521 :                 *list = node->next; /* the new head, in case 0 */
     268             :         else
     269      103878 :                 node->prev->next = node->next;
     270             : 
     271      353399 :         return node->data;
     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       79280 : 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       79280 :         second_head = tommy_list_head(second);
     289       79280 :         if (second_head == 0)
     290       70002 :                 return;
     291             : 
     292             :         /* if the first is empty, copy the second */
     293        9278 :         first_head = tommy_list_head(first);
     294        9278 :         if (first_head == 0) {
     295        8209 :                 *first = *second;
     296        8209 :                 return;
     297             :         }
     298             : 
     299             :         /* tail of the first list */
     300        1069 :         first_tail = first_head->prev;
     301             : 
     302             :         /* set the "circular" prev list */
     303        1069 :         first_head->prev = second_head->prev;
     304        1069 :         second_head->prev = first_tail;
     305             : 
     306             :         /* set the "0 terminated" next list */
     307        1069 :         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        4387 : tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
     324             : {
     325        4387 :         return tommy_list_head(list) == 0;
     326             : }
     327             : 
     328             : /**
     329             :  * Gets the number of elements.
     330             :  * \note This operation is O(n).
     331             :  */
     332         260 : tommy_inline tommy_count_t tommy_list_count(tommy_list* list)
     333             : {
     334         260 :         tommy_count_t count = 0;
     335         260 :         tommy_node* i = tommy_list_head(list);
     336             : 
     337        2075 :         while (i) {
     338        1555 :                 ++count;
     339        1555 :                 i = i->next;
     340             :         }
     341             : 
     342         260 :         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        7645 : tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
     374             : {
     375        7645 :         tommy_node* node = tommy_list_head(list);
     376             : 
     377     3679911 :         while (node) {
     378     3664621 :                 void* data = node->data;
     379     3664621 :                 node = node->next;
     380     3664621 :                 func(data);
     381             :         }
     382        7645 : }
     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             : 

Generated by: LCOV version 1.13