• Skip to content
  • Skip to link menu
csync API Reference
  • csync
  • Sitemap
  • Contact Us
 
lomoco

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 

lomoco

Skip menu "lomoco"

API Documentation

Skip menu "@topname@"
Generated with Doxygen