l4/pkg/l4re-core/l4util/include/sll.h

   1 /**
   2  * \file
   3  * \brief List implemenation
   4  */
   5 /*
   6  * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
   7  *               Ronald Aigner <ra3@os.inf.tu-dresden.de>
   8  *     economic rights: Technische Universität Dresden (Germany)
   9  * This file is part of TUD:OS and distributed under the terms of the
  10  * GNU Lesser General Public License 2.1.
  11  * Please see the COPYING-LGPL-2.1 file for details.
  12  */
  13 #ifndef __L4UTIL__SLL_H__
  14 #define __L4UTIL__SLL_H__
  15
  16 #include <stdlib.h>
  17
  18 #include <l4/sys/compiler.h>
  19
  20 EXTERN_C_BEGIN
  21
  22 /*
  23  * the linked list structure
  24  */
  25
  26 typedef struct slist_t
  27 {
  28   struct slist_t *next;   /* pointer to next node */
  29   void *data;          /* void pointer for user data */
  30 } slist_t;
  31
  32 /*
  33  * function prototypes
  34  */
  35 static inline slist_t*
  36 list_new_entry(void *data);
  37
  38 static inline slist_t*
  39 list_append(slist_t *list, slist_t *new_node);
  40
  41 static inline slist_t*
  42 list_remove(slist_t *list, slist_t *node);
  43
  44 static inline void
  45 list_free_entry(slist_t **list);
  46
  47 static inline unsigned char
  48 list_is_empty(slist_t *list);
  49
  50 static inline slist_t*
  51 list_get_at(slist_t *list, int n);
  52
  53 static inline slist_t*
  54 list_add(slist_t *list, slist_t *new_node);
  55
  56 static inline void
  57 list_insert_after(slist_t *after, slist_t *new_node);
  58
  59 static inline int
  60 list_elements(slist_t *head);
  61
  62 /*
  63  *  allocateNode()
  64  *  allocate a new node.
  65  *
  66  *  Parameters:
  67  *  void    *data       a generic pointer to object data
  68  *
  69  *  Return Values:
  70  *  pointer to slist_t if succeeds
  71  *  NULL otherwise
  72  *
  73  */
  74 static inline slist_t*
  75 list_new_entry(void *data)
  76 {
  77   slist_t *sll;
  78
  79   sll = (slist_t *)malloc(sizeof(slist_t));
  80   if (!sll)
  81     return ((slist_t *) NULL);
  82
  83   sll->data=data;
  84   sll->next=NULL;
  85
  86   return (sll);
  87 }
  88
  89 /*
  90  *  appendNode()
  91  *  appends a node to the end of a list
  92  *
  93  *  Parameters:
  94  *  slist_t *head      - modify the list
  95  *  slist_t *new       - appends this node
  96  *
  97  *  Return Values:
  98  *  the new list
  99  *
 100  */
 101 static inline slist_t*
 102 list_append(slist_t *head, slist_t *new_node)
 103 {
 104   slist_t *ret = head;
 105   if (!head)
 106     return new_node;
 107
 108   while (head->next)
 109     head = head->next;
 110   head->next = new_node;
 111   return ret;
 112 }
 113
 114 /*
 115  *  insertNode()
 116  *  insert a node at the beginning of a list
 117  *
 118  *  Parameters:
 119  *  slist_t *head      - modify this list
 120  *  slist_t *new       - appends this node
 121  *
 122  *  Return Values:
 123  *  the new list
 124  *
 125  */
 126 static inline slist_t*
 127 list_add(slist_t *head, slist_t *new_node)
 128 {
 129   if (!new_node)
 130     return head;
 131   new_node->next = head;
 132   return new_node;
 133 }
 134
 135 /*
 136  *  insertNode()
 137  *  insert a node at the beginning of a list
 138  *
 139  *  Parameters:
 140  *  slist_t *head      - modify this list
 141  *  slist_t *new       - appends this node
 142  *
 143  *  Return Values:
 144  *  the new list
 145  *
 146  */
 147 static inline void
 148 list_insert_after(slist_t *after, slist_t *new_node)
 149 {
 150   if (!new_node)
 151     return;
 152   if (!after)
 153     return;
 154   new_node->next = after->next;
 155   after->next = new_node;
 156 }
 157
 158
 159 /*
 160  *  emptyList()
 161  *  check if a list variable is NULL
 162  *
 163  *  Parameters:
 164  *  slist_t *list      list
 165  *
 166  *  Return Values:
 167  *  TRUE    if empty
 168  *  FALSE   if not empty
 169  *
 170  */
 171 static inline unsigned char
 172 list_is_empty(slist_t *list)
 173 {
 174   return ((list) ? 0 : 1);
 175 }
 176
 177 /*
 178  *  delNode()
 179  *  remove a node from a list
 180  *
 181  *  Parameters:
 182  *  slist_t  *head      - list to modify
 183  *  slist_t *node       - node to remove
 184  *
 185  *  Return Values:
 186  *  none
 187  *
 188  */
 189 static inline slist_t*
 190 list_remove(slist_t *head, slist_t *node)
 191 {
 192   slist_t *ret = head;
 193   if (list_is_empty(head))
 194     return ret;
 195   if (!node)
 196     return ret;
 197
 198   if (head == node)
 199     {
 200       ret = head->next;
 201     }
 202   else
 203     {
 204       while (head && (head->next != node))
 205         head = head->next;
 206       if (!head)
 207         return ret;
 208       else
 209         head->next = node->next;
 210     }
 211   list_free_entry(&node);
 212   return ret;
 213 }
 214
 215 /*
 216  *  freeNode()
 217  *  frees a node
 218  *
 219  *  Parameters:
 220  *  slist_t  *list  node to free
 221  *
 222  *  Return Values:
 223  *  none
 224  *
 225  */
 226 static inline void
 227 list_free_entry(slist_t **list)
 228 {
 229   if (*list)
 230     {
 231       free ((void *) (*list));
 232       (*list)=NULL;
 233     }
 234 }
 235
 236
 237 /*
 238  *  getNthNode()
 239  *  get nth node in a list
 240  *
 241  *  Parameters:
 242  *  slist_t *list       - the head list
 243  *  int n           - return the node
 244  *  Return Values:
 245  *  a pointer to the list at position n
 246  *  NULL if there's no such node at posion n
 247  *
 248  */
 249 static inline slist_t*
 250 list_get_at(slist_t *list, int n)
 251 {
 252   int j=0;
 253
 254   while (list)
 255     {
 256       j++;
 257       if (j == n)
 258         return (list);
 259       list = list->next;
 260     }
 261
 262   return ((slist_t *) NULL);
 263 }
 264
 265 /*
 266  *  numNodes()
 267  *  returns number of nodes in the list
 268  *
 269  *  Parameters:
 270  *  slist_t  *head      - the head node of the list
 271  *
 272  *  Return Values:
 273  *  number of node/s
 274  *
 275  */
 276 static inline int
 277 list_elements(slist_t *head)
 278 {
 279   register int n;
 280   for (n=0; head; head=head->next) n++;
 281   return (n);
 282 }
 283
 284 EXTERN_C_END
 285
 286 #endif  /* __L4UTIL__SLL_H__ */