src/libstrongswan/utils/linked_list.h

   1 /**
   2  * @file linked_list.h
   3  *
   4  * @brief Interface of linked_list_t.
   5  *
   6  */
   7
   8 /*
   9  * Copyright (C) 2007 Tobias Brunner
  10  * Copyright (C) 2005-2006 Martin Willi
  11  * Copyright (C) 2005 Jan Hutter
  12  * Hochschule fuer Technik Rapperswil
  13  *
  14  * This program is free software; you can redistribute it and/or modify it
  15  * under the terms of the GNU General Public License as published by the
  16  * Free Software Foundation; either version 2 of the License, or (at your
  17  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  18  *
  19  * This program is distributed in the hope that it will be useful, but
  20  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  21  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  22  * for more details.
  23  */
  24
  25 #ifndef LINKED_LIST_H_
  26 #define LINKED_LIST_H_
  27
  28 typedef struct linked_list_t linked_list_t;
  29
  30 #include <pthread.h>
  31
  32 #include <library.h>
  33 #include <utils/iterator.h>
  34 #include <utils/enumerator.h>
  35
  36
  37 /**
  38  * Method to match elements in a linked list (used in find_* functions)
  39  *
  40  * @param item                  current list item
  41  * @param ...                   user supplied data (only pointers, at most 5)
  42  * @return
  43  *                                              - TRUE, if the item matched
  44  *                                              - FALSE, otherwise
  45  * @ingroup utils
  46  */
  47 typedef bool (*linked_list_match_t)(void *item, ...);
  48
  49 /**
  50  * @brief Class implementing a double linked list.
  51  *
  52  * General purpose linked list. This list is not synchronized.
  53  *
  54  * @b Costructors:
  55  * - linked_list_create()
  56  *
  57  * @ingroup utils
  58  */
  59 struct linked_list_t {
  60
  61         /**
  62          * @brief Gets the count of items in the list.
  63          *
  64          * @param this          calling object
  65          * @return                      number of items in list
  66          */
  67         int (*get_count) (linked_list_t *this);
  68
  69         /**
  70          * @brief Creates a iterator for the given list.
  71          *
  72          * @warning Created iterator_t object has to get destroyed by the caller.
  73          *
  74          * @deprecated Iterator is obsolete and will disappear, it is too
  75          * complicated to implement. Use enumerator instead.
  76          *
  77          * @param this          calling object
  78          * @param forward       iterator direction (TRUE: front to end)
  79          * @return                      new iterator_t object
  80          */
  81         iterator_t *(*create_iterator) (linked_list_t *this, bool forward);
  82
  83         /**
  84          * @brief Creates a iterator, locking a mutex.
  85          *
  86          * The supplied mutex is acquired immediately, and released
  87          * when the iterator gets destroyed.
  88          *
  89          * @param this          calling object
  90          * @param mutex         mutex to use for exclusive access
  91          * @return                      new iterator_t object
  92          */
  93         iterator_t *(*create_iterator_locked) (linked_list_t *this,
  94                                                                                    pthread_mutex_t *mutex);
  95
  96         /**
  97          * @brief Create an enumerator over the list.
  98          *
  99          * The enumerator is a "lightweight" iterator. It only has two methods
 100          * and should therefore be much easier to implement.
 101          *
 102          * @param this          calling object
 103          * @return                      enumerator over list items
 104          */
 105         enumerator_t* (*create_enumerator)(linked_list_t *this);
 106
 107         /**
 108          * @brief Inserts a new item at the beginning of the list.
 109          *
 110          * @param this          calling object
 111          * @param[in] item      item value to insert in list
 112          */
 113         void (*insert_first) (linked_list_t *this, void *item);
 114
 115         /**
 116          * @brief Removes the first item in the list and returns its value.
 117          *
 118          * @param this          calling object
 119          * @param[out] item returned value of first item, or NULL
 120          * @return
 121          *                                      - SUCCESS
 122          *                                      - NOT_FOUND, if list is empty
 123          */
 124         status_t (*remove_first) (linked_list_t *this, void **item);
 125
 126         /**
 127          * @brief Returns the value of the first list item without removing it.
 128          *
 129          * @param this          calling object
 130          * @param[out] item     returned value of first item
 131          * @return
 132          *                                      - SUCCESS
 133          *                                      - NOT_FOUND, if list is empty
 134          */
 135         status_t (*get_first) (linked_list_t *this, void **item);
 136
 137         /**
 138          * @brief Inserts a new item at the end of the list.
 139          *
 140          * @param this          calling object
 141          * @param[in] item      value to insert into list
 142          */
 143         void (*insert_last) (linked_list_t *this, void *item);
 144
 145         /**
 146          * @brief Inserts a new item at a given position in the list.
 147          *
 148          * @param this          calling object
 149          * @param position      position starting at 0 to insert new entry
 150          * @param[in] item      value to insert into list
 151          * @return
 152          *                                      - SUCCESS
 153          *                                      - INVALID_ARG if position not existing
 154          */
 155         status_t (*insert_at_position) (linked_list_t *this,size_t position, void *item);
 156
 157         /**
 158          * @brief Removes an item from a given position in the list.
 159          *
 160          * @param this          calling object
 161          * @param position      position starting at 0 to remove entry from
 162          * @param[out] item removed item will be stored at this location
 163          * @return
 164          *                                              - SUCCESS
 165          *                                              - INVALID_ARG if position not existing
 166          */
 167         status_t (*remove_at_position) (linked_list_t *this, size_t position, void **item);
 168
 169         /**
 170          * @brief Get an item from a given position in the list.
 171          *
 172          * @param this          calling object
 173          * @param position      position starting at 0 to get entry from
 174          * @param[out] item     item will be stored at this location
 175          * @return
 176          *                                              - SUCCESS
 177          *                                              - INVALID_ARG if position not existing
 178          */
 179         status_t (*get_at_position) (linked_list_t *this, size_t position, void **item);
 180
 181         /**
 182          * @brief Removes the last item in the list and returns its value.
 183          *
 184          * @param this          calling object
 185          * @param[out] item     returned value of last item, or NULL
 186          * @return
 187          *                                              - SUCCESS
 188          *                                              - NOT_FOUND if list is empty
 189          */
 190         status_t (*remove_last) (linked_list_t *this, void **item);
 191
 192         /**
 193          * @brief Returns the value of the last list item without removing it.
 194          *
 195          * @param this          calling object
 196          * @param[out] item     returned value of last item
 197          * @return
 198          *                                      - SUCCESS
 199          *                                      - NOT_FOUND if list is empty
 200          */
 201         status_t (*get_last) (linked_list_t *this, void **item);
 202
 203         /** @brief Find the first matching element in the list.
 204          *
 205          * The first object passed to the match function is the current list item,
 206          * followed by the user supplied data.
 207          * If the supplied function returns TRUE this function returns SUCCESS, and
 208          * the current object is returned in the third parameter, otherwise,
 209          * the next item is checked.
 210          *
 211          * @warning Only use pointers as user supplied data.
 212          *
 213          * @param this                  calling object
 214          * @param match                 comparison function to call on each object
 215          * @param[out] item
 216          *                                              - the list item, if found
 217          *                                              - NULL, otherwise
 218          * @param ...                   user data to supply to match function (limited to 5 arguments)
 219          * @return
 220          *                                              - SUCCESS, if found
 221          *                                              - NOT_FOUND, otherwise
 222          */
 223         status_t (*find_first) (linked_list_t *this, linked_list_match_t match, void **item, ...);
 224
 225         /** @brief Find the last matching element in the list.
 226          *
 227          * The first object passed to the match function is the current list item,
 228          * followed by the user supplied data.
 229          * If the supplied function returns TRUE this function returns SUCCESS, and
 230          * the current object is returned in the third parameter, otherwise,
 231          * the next item is checked.
 232          *
 233          * @warning Only use pointers as user supplied data.
 234          *
 235          * @param this                  calling object
 236          * @param match                 comparison function to call on each object
 237          * @param[out] item
 238          *                                              - the list item, if found
 239          *                                              - NULL, otherwise
 240          * @param ...                   user data to supply to match function (limited to 5 arguments)
 241          * @return
 242          *                                              - SUCCESS, if found
 243          *                                              - NOT_FOUND, otherwise
 244          */
 245         status_t (*find_last) (linked_list_t *this, linked_list_match_t match, void **item, ...);
 246
 247         /**
 248          * @brief Invoke a method on all of the contained objects.
 249          *
 250          * If a linked list contains objects with function pointers,
 251          * invoke() can call a method on each of the objects. The
 252          * method is specified by an offset of the function pointer,
 253          * which can be evalutated at compile time using the offsetof
 254          * macro, e.g.: list->invoke(list, offsetof(object_t, method));
 255          *
 256          * @param this          calling object
 257          * @param offset        offset of the method to invoke on objects
 258          */
 259         void (*invoke_offset) (linked_list_t *this, size_t offset);
 260
 261         /**
 262          * @brief Invoke a function on all of the contained objects.
 263          *
 264          * @param this          calling object
 265          * @param offset        offset of the method to invoke on objects
 266          */
 267         void (*invoke_function) (linked_list_t *this, void (*)(void*));
 268
 269         /**
 270          * @brief Clones a list and its objects using the objects' clone method.
 271          *
 272          * @param this          calling object
 273          * @param offset        offset ot the objects clone function
 274          * @return                      cloned list
 275          */
 276         linked_list_t *(*clone_offset) (linked_list_t *this, size_t offset);
 277
 278         /**
 279          * @brief Clones a list and its objects using a given function.
 280          *
 281          * @param this          calling object
 282          * @param function      function that clones an object
 283          * @return                      cloned list
 284          */
 285         linked_list_t *(*clone_function) (linked_list_t *this, void*(*)(void*));
 286
 287         /**
 288          * @brief Destroys a linked_list object.
 289          *
 290          * @param this          calling object
 291          */
 292         void (*destroy) (linked_list_t *this);
 293
 294         /**
 295          * @brief Destroys a list and its objects using the destructor.
 296          *
 297          * If a linked list and the contained objects should be destroyed, use
 298          * destroy_offset. The supplied offset specifies the destructor to
 299          * call on each object. The offset may be calculated using the offsetof
 300          * macro, e.g.: list->destroy_offset(list, offsetof(object_t, destroy));
 301          *
 302          * @param this          calling object
 303          * @param offset        offset of the objects destructor
 304          */
 305         void (*destroy_offset) (linked_list_t *this, size_t offset);
 306
 307         /**
 308          * @brief Destroys a list and its contents using a a cleanup function.
 309          *
 310          * If a linked list and its contents should get destroyed using a specific
 311          * cleanup function, use destroy_function. This is useful when the
 312          * list contains malloc()-ed blocks which should get freed,
 313          * e.g.: list->destroy_function(list, free);
 314          *
 315          * @param this          calling object
 316          * @param function      function to call on each object
 317          */
 318         void (*destroy_function) (linked_list_t *this, void (*)(void*));
 319 };
 320
 321 /**
 322  * @brief Creates an empty linked list object.
 323  *
 324  * @return              linked_list_t object.
 325  *
 326  * @ingroup utils
 327  */
 328 linked_list_t *linked_list_create(void);
 329
 330
 331 #endif /*LINKED_LIST_H_*/