doc
|
00001 /* 00002 * c_list -- 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-2008 Andreas Schneider <mail@csyncapses.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 _C_LIST_H 00027 #define _C_LIST_H 00028 00029 /** 00030 * c_list -- a doubly-linked list. 00031 * 00032 * The c_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 c_list.h 00043 */ 00044 00045 00046 /** 00047 * @typedef c_list_t 00048 * Creates a type name for c_list_s 00049 */ 00050 typedef struct c_list_s c_list_t; 00051 /** 00052 * @struct c_list_s 00053 * 00054 * Used for each element in a doubly-linked list. The list can hold 00055 * any kind of data. 00056 */ 00057 struct c_list_s { 00058 /** Link to the next element in the list */ 00059 struct c_list_s *next; 00060 /** Link to the previous element in the list */ 00061 struct c_list_s *prev; 00062 00063 /** 00064 * Holds the element's data, which can be a pointer to any kind of 00065 * data. 00066 */ 00067 void *data; 00068 }; 00069 00070 /** 00071 * Specifies the type of a comparison function used to compare two values. The 00072 * value which should be returned depends on the context in which the 00073 * c_list_compare_fn is used. 00074 * 00075 * @param a First parameter to compare with. 00076 * 00077 * @param b Second parameter to compare with. 00078 * 00079 * @return The function should return a number > 0 if the first 00080 * parameter comes after the second parameter in the sort 00081 * order. 00082 */ 00083 typedef int (*c_list_compare_fn) (const void *a, const void *b); 00084 00085 /** 00086 * Adds a new element on to the end of the list. 00087 * 00088 * @param list A pointer to c_list. 00089 * 00090 * @param data The data for the new element. 00091 * 00092 * @return New start of the list, which may have changed, so make 00093 * sure you store the new value. 00094 */ 00095 c_list_t *c_list_append(c_list_t *list, void *data); 00096 00097 /** 00098 * Adds a new element on at the beginning of the list. 00099 * 00100 * @param list A pointer to c_list. 00101 * 00102 * @param data The data for the new element. 00103 * 00104 * @return New start of the list, which may have changed, so make 00105 * sure you store the new value. 00106 */ 00107 c_list_t *c_list_prepend(c_list_t *list, void *data); 00108 00109 /** 00110 * Inserts a new element into the list at the given position. If the position 00111 * is lesser than 0, the new element gets appended to the list, if the position 00112 * is 0, we prepend the element and if the given position is greater than the 00113 * length of the list, the element gets appended too. 00114 * 00115 * @param list A pointer to c_list. 00116 * 00117 * @param data The data for the new element. 00118 * 00119 * @param position The position to insert the element. 00120 * 00121 * @return New start of the list, which may have changed, so make 00122 * sure you store the new value. 00123 */ 00124 c_list_t *c_list_insert(c_list_t *list, void *data, long position); 00125 00126 /** 00127 * Inserts a new element into the list, using the given comparison function to 00128 * determine its position. 00129 * 00130 * @param list A pointer to c_list. 00131 * 00132 * @param data The data for the new element. 00133 * 00134 * @param fn The function to compare elements in the list. It 00135 * should return a number > 0 if the first parameter comes 00136 * after the second parameter in the sort order. 00137 * 00138 * @return New start of the list, which may have changed, so make 00139 * sure you store the new value. 00140 */ 00141 c_list_t *c_list_insert_sorted(c_list_t *list, void *data, 00142 c_list_compare_fn fn); 00143 00144 /** 00145 * Allocates space for one c_list_t element. 00146 * 00147 * @return A pointer to the newly-allocated element. 00148 */ 00149 c_list_t *c_list_alloc(void); 00150 00151 /** 00152 * Removes an element from a c_list. If two elements contain the same data, 00153 * only the first is removed. 00154 * 00155 * @param list A pointer to c_list. 00156 * 00157 * @param data The data of the element to remove. 00158 * 00159 * @return The first element of the list, NULL on error. 00160 */ 00161 c_list_t *c_list_remove(c_list_t *list, void *data); 00162 00163 /** 00164 * Frees all elements from a c_list. 00165 * 00166 * @param list A pointer to c_list. 00167 */ 00168 void c_list_free(c_list_t *list); 00169 00170 /** 00171 * Gets the next element in a c_list. 00172 * 00173 * @param An element in a c_list. 00174 * 00175 * @return The next element, or NULL if there are no more 00176 * elements. 00177 */ 00178 c_list_t *c_list_next(c_list_t *list); 00179 00180 /** 00181 * Gets the previous element in a c_list. 00182 * 00183 * @param An element in a c_list. 00184 * 00185 * @return The previous element, or NULL if there are no more 00186 * elements. 00187 */ 00188 c_list_t *c_list_prev(c_list_t *list); 00189 00190 /** 00191 * Gets the number of elements in a c_list 00192 * 00193 * @param list A pointer to c_list. 00194 * 00195 * @return The number of elements 00196 */ 00197 unsigned long c_list_length(c_list_t *list); 00198 00199 /** 00200 * Gets the first element in a c_list 00201 * 00202 * @param list A pointer to c_list. 00203 * 00204 * @return New start of the list, which may have changed, so make 00205 * sure you store the new value. 00206 */ 00207 c_list_t *c_list_first(c_list_t *list); 00208 00209 /** 00210 * Gets the last element in a c_list 00211 * 00212 * @param list A pointer to c_list. 00213 * 00214 * @return New start of the list, which may have changed, so make 00215 * sure you store the new value. 00216 */ 00217 c_list_t *c_list_last(c_list_t *list); 00218 00219 /** 00220 * Gets the element at the given positon in a c_list. 00221 * 00222 * @param list A pointer to c_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 c_list_t *c_list_position(c_list_t *list, long position); 00230 00231 /** 00232 * Finds the element in a c_list_t which contains the given data. 00233 * 00234 * @param list A pointer to c_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 c_list_t *c_list_find(c_list_t *list, const void *data); 00241 00242 /** 00243 * Finds an element, using a supplied function to find the desired 00244 * element. 00245 * 00246 * @param list A pointer to c_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 c_list_t *c_list_find_custom(c_list_t *list, const void *data, 00256 c_list_compare_fn fn); 00257 00258 /** 00259 * Sorts the elements of a c_list. 00260 * The algorithm used is Mergesort, because that works really well 00261 * on linked lists, without requiring the O(N) extra space it needs 00262 * when you do it on arrays. 00263 * 00264 * @param list A pointer to c_list. 00265 * 00266 * @param func The comparison function used to sort the c_list. This 00267 * function is passed 2 elements of the GList and should 00268 * return 0 if they are equal, a negative value if the 00269 * first element comes before the second, or a positive 00270 * value if the first element comes after the second. 00271 * 00272 * @return New start of the list, which may have changed, so make 00273 * sure you store the new value. 00274 */ 00275 c_list_t *c_list_sort(c_list_t *list, c_list_compare_fn func); 00276 00277 #endif /* _C_LIST_H */ 00278