prism/util/pm_list.h

   1 /**
   2  * @file pm_list.h
   3  *
   4  * An abstract linked list.
   5  */
   6 #ifndef PRISM_LIST_H
   7 #define PRISM_LIST_H
   8
   9 #include "prism/defines.h"
  10
  11 #include <stdbool.h>
  12 #include <stddef.h>
  13 #include <stdint.h>
  14 #include <stdlib.h>
  15
  16 /**
  17  * This struct represents an abstract linked list that provides common
  18  * functionality. It is meant to be used any time a linked list is necessary to
  19  * store data.
  20  *
  21  * The linked list itself operates off a set of pointers. Because the pointers
  22  * are not necessarily sequential, they can be of any size. We use this fact to
  23  * allow the consumer of this linked list to extend the node struct to include
  24  * any data they want. This is done by using the pm_list_node_t as the first
  25  * member of the struct.
  26  *
  27  * For example, if we want to store a list of integers, we can do the following:
  28  *
  29  * ```c
  30  * typedef struct {
  31  *     pm_list_node_t node;
  32  *     int value;
  33  * } pm_int_node_t;
  34  *
  35  * pm_list_t list = { 0 };
  36  * pm_int_node_t *node = xmalloc(sizeof(pm_int_node_t));
  37  * node->value = 5;
  38  *
  39  * pm_list_append(&list, &node->node);
  40  * ```
  41  *
  42  * The pm_list_t struct is used to represent the overall linked list. It
  43  * contains a pointer to the head and tail of the list. This allows for easy
  44  * iteration and appending of new nodes.
  45  */
  46 typedef struct pm_list_node {
  47     /** A pointer to the next node in the list. */
  48     struct pm_list_node *next;
  49 } pm_list_node_t;
  50
  51 /**
  52  * This represents the overall linked list. It keeps a pointer to the head and
  53  * tail so that iteration is easy and pushing new nodes is easy.
  54  */
  55 typedef struct {
  56     /** The size of the list. */
  57     size_t size;
  58
  59     /** A pointer to the head of the list. */
  60     pm_list_node_t *head;
  61
  62     /** A pointer to the tail of the list. */
  63     pm_list_node_t *tail;
  64 } pm_list_t;
  65
  66 /**
  67  * Returns true if the given list is empty.
  68  *
  69  * @param list The list to check.
  70  * @return True if the given list is empty, otherwise false.
  71  */
  72 PRISM_EXPORTED_FUNCTION bool pm_list_empty_p(pm_list_t *list);
  73
  74 /**
  75  * Returns the size of the list.
  76  *
  77  * @param list The list to check.
  78  * @return The size of the list.
  79  */
  80 PRISM_EXPORTED_FUNCTION size_t pm_list_size(pm_list_t *list);
  81
  82 /**
  83  * Append a node to the given list.
  84  *
  85  * @param list The list to append to.
  86  * @param node The node to append.
  87  */
  88 void pm_list_append(pm_list_t *list, pm_list_node_t *node);
  89
  90 /**
  91  * Deallocate the internal state of the given list.
  92  *
  93  * @param list The list to free.
  94  */
  95 PRISM_EXPORTED_FUNCTION void pm_list_free(pm_list_t *list);
  96
  97 #endif