src/libstrongswan/utils/linked_list.h

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