lomoco_list.h
Go to the documentation of this file.00001 /* 00002 * lomoco -- a doubly-linked list 00003 * 00004 * This code is based on glist.{h,c} from glib 00005 * ftp://ftp.gtk.org/pub/gtk/ 00006 * Copyright (c) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 00007 * Copyright (c) 2006 by Andreas Schneider <mail@lomocoapses.org> 00008 * 00009 * This program is free software; you can redistribute it and/or 00010 * modify it under the terms of the GNU General Public License 00011 * as published by the Free Software Foundation; either version 2 00012 * of the License, or (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 * GNU General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU General Public License 00020 * along with this program; if not, write to the Free Software Foundation, 00021 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00022 * 00023 * vim: ts=2 sw=2 et cindent 00024 */ 00025 00026 #ifndef LOMOCO_LIST_H 00027 #define LOMOCO_LIST_H 00028 00029 /** 00030 * lomoco_list_t -- a doubly-linked list. 00031 * 00032 * The lomoco_list_t structure and its associated functions provide a standard 00033 * doubly-linked list data structure. Each node has two links: one points to 00034 * the previous node, or points to a null value or empty list if it is the 00035 * first node; and one points to the next, or points to a null value or empty 00036 * list if it is the final node. 00037 * 00038 * The data contained in each element can be simply pointers to any type of 00039 * data. You are the owner of the data, this means you have to free the memory 00040 * you have allocated for the data. 00041 * 00042 * @file lomoco_list.h 00043 */ 00044 00045 /** 00046 * An untyped pointer. 00047 */ 00048 typedef void *lomoco_pointer; 00049 00050 /** 00051 * An untyped pointer to constant data. The data pointed to should not be 00052 * changed. 00053 * 00054 * This is typically used in function prototypes to indicate that the data 00055 * pointed to will not be altered by the function. 00056 */ 00057 typedef const void *lomoco_const_pointer; 00058 00059 /** 00060 * Specifies the type of a comparison function used to compare two values. The 00061 * value which should be returned depends on the context in which the 00062 * lomoco_compare_func is used. 00063 * 00064 * @param a First parameter to compare with. 00065 * 00066 * @param b Second parameter to compare with. 00067 * 00068 * @return The function should return a number > 0 if the first 00069 * parameter comes after the second parameter in the sort 00070 * order. 00071 */ 00072 typedef int (*lomoco_compare_func) (lomoco_const_pointer a, lomoco_const_pointer b); 00073 00074 /** 00075 * Used for each element in a doubly-linked list. The data field holds the 00076 * element's data, which can be a pointer to any kind of data. 00077 * The next and prev pointers are the links to the next and previous elements 00078 * in the list. 00079 */ 00080 typedef struct lomoco_list_s { 00081 struct lomoco_list_s *next; 00082 struct lomoco_list_s *prev; 00083 00084 lomoco_pointer data; 00085 } lomoco_list_t; 00086 00087 00088 /** 00089 * Adds a new element on to the end of the list. 00090 * 00091 * @param list A pointer to lomoco_list. 00092 * 00093 * @param data The data for the new element. 00094 * 00095 * @return New start of the list, which may have changed, so make 00096 * sure you store the new value. 00097 */ 00098 lomoco_list_t *lomoco_list_append(lomoco_list_t *list, lomoco_pointer data); 00099 00100 /** 00101 * Adds a new element on at the beginning of the list. 00102 * 00103 * @param list A pointer to lomoco_list. 00104 * 00105 * @param data The data for the new element. 00106 * 00107 * @return New start of the list, which may have changed, so make 00108 * sure you store the new value. 00109 */ 00110 lomoco_list_t *lomoco_list_prepend(lomoco_list_t *list, lomoco_pointer data); 00111 00112 /** 00113 * Inserts a new element into the list at the given position. If the position 00114 * is lesser than 0, the new element gets appended to the list, if the position 00115 * is 0, we prepend the element and if the given position is greater than the 00116 * length of the list, the element gets appended too. 00117 * 00118 * @param list A pointer to lomoco_list. 00119 * 00120 * @param data The data for the new element. 00121 * 00122 * @param position The position to insert the element. 00123 * 00124 * @return New start of the list, which may have changed, so make 00125 * sure you store the new value. 00126 */ 00127 lomoco_list_t *lomoco_list_insert(lomoco_list_t *list, lomoco_pointer data, long position); 00128 00129 /** 00130 * Inserts a new element into the list, using the given comparison function to 00131 * determine its position. 00132 * 00133 * @param list A pointer to lomoco_list. 00134 * 00135 * @param data The data for the new element. 00136 * 00137 * @param func The function to compare elements in the list. It 00138 * should return a number > 0 if the first parameter comes 00139 * after the second parameter in the sort order. 00140 * 00141 * @return New start of the list, which may have changed, so make 00142 * sure you store the new value. 00143 */ 00144 lomoco_list_t *lomoco_list_insert_sorted(lomoco_list_t *list, lomoco_pointer data, lomoco_compare_func func); 00145 00146 /** 00147 * Allocates space for one lomoco_list_t element. 00148 * 00149 * @return A pointer to the newly-allocated element. 00150 */ 00151 lomoco_list_t *lomoco_list_alloc(void); 00152 00153 /** 00154 * Removes an element from a lomoco_list. If two elements contain the same data, 00155 * only the first is removed. 00156 * 00157 * @param list A pointer to lomoco_list. 00158 * 00159 * @param data The data of the element to remove. 00160 */ 00161 lomoco_list_t *lomoco_list_remove(lomoco_list_t *list, lomoco_pointer data); 00162 00163 /** 00164 * Frees all elements from a lomoco_list. 00165 * 00166 * @param list A pointer to lomoco_list. 00167 */ 00168 void lomoco_list_free(lomoco_list_t *list); 00169 00170 /** 00171 * Gets the previous element in a lomoco_list. 00172 * 00173 * @param An element in a lomoco_list. 00174 * 00175 * @return The previous element, or NULL if there are no more 00176 * elements. 00177 */ 00178 lomoco_list_t *lomoco_list_previous(lomoco_list_t *list); 00179 00180 /** 00181 * Gets the next element in a lomoco_list. 00182 * 00183 * @param An element in a lomoco_list. 00184 * 00185 * @return The next element, or NULL if there are no more 00186 * elements. 00187 */ 00188 lomoco_list_t *lomoco_list_next(lomoco_list_t *list); 00189 00190 /** 00191 * Gets the number of elements in a lomoco_list 00192 * 00193 * @param list A pointer to lomoco_list. 00194 * 00195 * @return The number of elements 00196 */ 00197 unsigned long lomoco_list_length(lomoco_list_t *list); 00198 00199 /** 00200 * Gets the first element in a lomoco_list 00201 * 00202 * @param list A pointer to lomoco_list. 00203 * 00204 * @return New start of the list, which may have changed, so make 00205 * sure you store the new value. 00206 */ 00207 lomoco_list_t *lomoco_list_first(lomoco_list_t *list); 00208 00209 /** 00210 * Gets the last element in a lomoco_list 00211 * 00212 * @param list A pointer to lomoco_list. 00213 * 00214 * @return New start of the list, which may have changed, so make 00215 * sure you store the new value. 00216 */ 00217 lomoco_list_t *lomoco_list_last(lomoco_list_t *list); 00218 00219 /** 00220 * Gets the element at the given positon in a lomoco_list. 00221 * 00222 * @param list A pointer to lomoco_list. 00223 * 00224 * @param position The position of the element, counting from 0. 00225 * 00226 * @return New start of the list, which may have changed, so make 00227 * sure you store the new value. 00228 */ 00229 lomoco_list_t *lomoco_list_position(lomoco_list_t *list, long position); 00230 00231 /** 00232 * Finds the element in a lomoco_list_t which contains the given data. 00233 * 00234 * @param list A pointer to lomoco_list. 00235 * 00236 * @param data The data of the element to remove. 00237 * 00238 * @return The found element or NULL if it is not found. 00239 */ 00240 lomoco_list_t *lomoco_list_find(lomoco_list_t *list, lomoco_pointer data); 00241 00242 /** 00243 * Finds an element, using a supplied function to find the desired 00244 * element. 00245 * 00246 * @param list A pointer to lomoco_list. 00247 * 00248 * @param data The data of the element to remove. 00249 * 00250 * @param func The function to call for each element. It should 00251 * return 0 when the desired element is found. 00252 * 00253 * @return The found element or NULL if it is not found. 00254 */ 00255 lomoco_list_t *lomoco_list_find_custom(lomoco_list_t *list, lomoco_pointer data, lomoco_compare_func func); 00256 00257 /** 00258 * Sorts the elements of a lomoco_list. 00259 * The algorithm used is Mergesort, because that works really well 00260 * on linked lists, without requiring the O(N) extra space it needs 00261 * when you do it on arrays. 00262 * 00263 * @param list A pointer to lomoco_list. 00264 * 00265 * @param func The comparison function used to sort the lomoco_list. This 00266 * function is passed 2 elements of the GList and should 00267 * return 0 if they are equal, a negative value if the first 00268 * element comes before the second, or a positive value if the 00269 * first element comes after the second. 00270 * 00271 * @return New start of the list, which may have changed, so make 00272 * sure you store the new value. 00273 */ 00274 lomoco_list_t *lomoco_list_sort(lomoco_list_t *list, lomoco_compare_func func); 00275 00276 /** 00277 * Internal used function to merge 2 lists using a compare function 00278 * 00279 * @param list1 A pointer to lomoco_list. 00280 * 00281 * @param list2 A pointer to lomoco_list. 00282 * 00283 * @return New start of the list, which may have changed, so make 00284 * sure you store the new value. 00285 */ 00286 lomoco_list_t *lomoco_list_merge(lomoco_list_t *list1, lomoco_list_t *list2, lomoco_compare_func func); 00287 00288 /** 00289 * Internally used function to split 2 lists. 00290 * 00291 * @param list A pointer to lomoco_list. 00292 * 00293 * @return New start of the list, which may have changed, so make 00294 * sure you store the new value. 00295 */ 00296 lomoco_list_t *lomoco_list_split(lomoco_list_t *list); 00297 00298 #endif /* LOMOCO_LIST_H */ 00299