c_list.h

Go to the documentation of this file.
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 
Generated on Mon Jul 5 22:58:35 2010 for doc by  doxygen 1.6.3