Author: Pekka Riikonen <priikone@silcnet.org>
- Copyright (C) 2002 - 2007 Pekka Riikonen
+ Copyright (C) 2002 - 2008 Pekka Riikonen
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
*/
-/****h* silcutil/SILC List Interface
+/****h* silcutil/List Interface
*
* DESCRIPTION
*
- * Implementation of the SilcList interface. This interface provides
- * simple linked list. This interface does not allocate any memory.
+ * Generic list interface that can turn any structure with list pointers
+ * into a SilcList. The interface can provide both singly and doubly linked
+ * lists. The interface does not allocate any memory.
*
* SILC List is not thread-safe. If the same list context must be used
* in multithreaded environment concurrency control must be employed.
*
+ * EXAMPLE
+ *
+ * struct EntryStruct {
+ * char *dummy;
+ * struct EntryStruct *next; // The list member pointer
+ * };
+ *
+ * SilcList list;
+ *
+ * // Initialize list
+ * silc_list_init(list, struct EntryStruct, next);
+ *
***/
#ifndef SILCLIST_H
#define SILCLIST_H
-/****s* silcutil/SilcList/SilcList
+/****s* silcutil/SilcList
*
* NAME
*
unsigned int count : 30; /* Number of entries in the list */
} SilcList;
-/****d* silcutil/SilcList/SILC_LIST_END
+/****d* silcutil/SILC_LIST_END
*
* NAME
*
- * #define SILC_LIST_END ...
+ * #define SILC_LIST_END NULL
*
* DESCRIPTION
*
#define SILC_LIST_END NULL
/***/
-/****f* silcutil/SilcList/silc_list_init
+/****f* silcutil/silc_list_init
*
* SYNOPSIS
*
(list).head = (list).tail = (list).current = NULL; \
} while(0)
-/****f* silcutil/SilcList/silc_list_init_prev
+/****f* silcutil/silc_list_init_prev
*
* SYNOPSIS
*
(list).head = (list).tail = (list).current = NULL; \
} while(0)
-/****f* silcutil/SilcList/silc_list_count
+/****f* silcutil/silc_list_count
*
* SYNOPSIS
*
- * #define silc_list_count(list) ...
+ * SilcUInt32 silc_list_count(SilcList list);
*
* DESCRIPTION
*
***/
#define silc_list_count(list) (list).count
-/****f* silcutil/SilcList/silc_list_start
+/****f* silcutil/silc_list_start
*
* SYNOPSIS
*
- * #define silc_list_start(list) ...
+ * void silc_list_start(SilcList list);
*
* DESCRIPTION
*
#define silc_list_start(list) \
((list).current = (list).head, (list).end_set = 0)
-/****f* silcutil/SilcList/silc_list_end
+/****f* silcutil/silc_list_end
*
* SYNOPSIS
*
- * #define silc_list_end(list) ...
+ * void silc_list_end(SilcList list);
*
* DESCRIPTION
*
#define __silc_list_prev(list, pos) \
((void **)((unsigned char *)(pos) + (list).prev_offset))
-/****f* silcutil/SilcList/silc_list_add
+/****f* silcutil/silc_list_add
*
* SYNOPSIS
*
- * #define silc_list_add(list, entry) ...
+ * void silc_list_add(SilcList list, void *entry);
*
* DESCRIPTION
*
(list).count++; \
} while(0)
-/****f* silcutil/SilcList/silc_list_insert
+/****f* silcutil/silc_list_insert
*
* SYNOPSIS
*
- * #define silc_list_insert(list, current, entry) ...
+ * void silc_list_insert(SilcList list, void *current, void *entry);
*
* DESCRIPTION
*
(list).count++; \
} while(0)
-/****f* silcutil/SilcList/silc_list_del
+/****f* silcutil/silc_list_del
*
* SYNOPSIS
*
- * #define silc_list_del(list, entry) ...
+ * void silc_list_del(SilcListlist, void *entry);
*
* DESCRIPTION
*
for (p = &(list).head; *p; p = __silc_list_next(list, *p)) { \
if (*p == (entry)) { \
*p = *__silc_list_next(list, entry); \
- if (*p && (list).prev_set) \
+ if ((list).prev_set && *p) \
*__silc_list_prev(list, *p) = *__silc_list_prev(list, entry); \
if ((list).current == (entry)) \
(list).current = *p; \
(list).tail = prev; \
} while(0)
-/****f* silcutil/SilcList/silc_list_get
+/****f* silcutil/silc_list_get
*
* SYNOPSIS
*
- * #define silc_list_get(list) ...
+ * void *silc_list_get(SilcList list);
*
* DESCRIPTION
*
return pos;
}
-#endif
+/****f* silcutil/silc_list_pop
+ *
+ * SYNOPSIS
+ *
+ * void *silc_list_pop(SilcList list);
+ *
+ * DESCRIPTION
+ *
+ * Pops the head of the list. Removes the head of the list and returns
+ * the removed head. This will always remove the head of the list even
+ * if silc_list_end was called. Calling silc_list_start is not necessary.
+ * Returns SILC_LIST_END if the list is empty.
+ *
+ ***/
+#define silc_list_pop(x) __silc_list_pop(&(x))
+static inline
+void *__silc_list_pop(SilcList *list)
+{
+ void *head, **p;
+
+ if (!list->head)
+ return NULL;
+
+ head = list->head;
+ p = &list->head;
+ *p = *__silc_list_next(*list, head);
+ if (list->prev_set && *p)
+ *__silc_list_prev(*list, *p) = *__silc_list_prev(*list, head);
+
+ if (list->current == head)
+ list->current = *p;
+ if (head == list->tail)
+ list->tail = NULL;
+
+ list->count--;
+
+ return head;
+}
+
+/****f* silcutil/silc_list_sort
+ *
+ * SYNOPSIS
+ *
+ * void silc_list_sort(SilcList list, SilcCompare compare, context);
+ *
+ * DESCRIPTION
+ *
+ * Sort the list. The `compare' function will be called with `context'
+ * to do comparison between the entries. The `compare' must return
+ * SILC_COMPARE_LESS_THAN, SILC_COMPARE_EQUAL_TO, or
+ * SILC_COMPARE_GREATER_THAN zero if the first argument is considered to
+ * be respectively less than, equal to, or greater than the second.
+ * The entries are then sorted in ascending order. The function must not
+ * return SILC_COMPARE_STOP.
+ *
+ * NOTES
+ *
+ * The list must be initialized with silc_list_init_prev for sorting
+ * to work.
+ *
+ ***/
+#define silc_list_sort(x, comp, ctx) __silc_list_sort(&(x), comp, ctx)
+static inline
+void __silc_list_sort(SilcList *list, SilcCompare compare, void *context)
+{
+ void *c_cur, *c_prev;
+
+ SILC_ASSERT(list->prev_set);
+ if (!list->prev_set)
+ return;
+
+ if (silc_list_count(*list) < 2)
+ return;
+
+ /* Gnome sort */
+ silc_list_start(*list);
+ c_prev = silc_list_get(*list);
+ while ((c_cur = silc_list_get(*list))) {
+ if (compare(c_prev, c_cur, context) == SILC_COMPARE_GREATER_THAN) {
+ list->current = *__silc_list_prev(*list, c_prev);
+ silc_list_del(*list, c_prev);
+ silc_list_insert(*list, c_cur, c_prev);
+
+ if (list->current) {
+ c_prev = list->current;
+ list->current = c_cur;
+ continue;
+ }
+ list->current = c_cur;
+ __silc_list_get(list);
+ }
+ c_prev = c_cur;
+ }
+
+ list->current = NULL;
+}
+
+/****f* silcutil/silc_list_find
+ *
+ * SYNOPSIS
+ *
+ * void *silc_list_find(SilcList list, void *entry1, SilcCompare compare,
+ * void *context);
+ *
+ * DESCRIPTION
+ *
+ * Find an entry from the `list'. The `compare' function will be called
+ * with `context' to do comparison between the entries. If `compare'
+ * returns 0 the `entry1' is considered to be equal to `entry2' and the
+ * found entry is returned. Returns NULL if the entry could not be found.
+ *
+ * The silc_list_start or silc_list_end must be called before calling this
+ * if the finding should be started from the beginning or from the end.
+ * Calling it however is not required. The founding can be started at
+ * any point of the list. The silc_list_find can be called many times
+ * to find more entries following the previously found entries.
+ *
+ * The list can be enumerated by calling silc_list_get after the found
+ * entry. The silc_list_get will return the next entry after the found
+ * entry.
+ *
+ ***/
+#define silc_list_find(x, e, comp, ctx) __silc_list_find(&(x), (e), comp, ctx)
+static inline
+void *__silc_list_find(SilcList *list, void *entry1, SilcCompare compare,
+ void *context)
+{
+ void *entry2;
+ int ret;
+ while ((entry2 = __silc_list_get(list))) {
+ ret = compare(entry1, entry2, context);
+ if (ret == SILC_COMPARE_EQUAL_TO)
+ return entry2;
+ if (ret == SILC_COMPARE_STOP)
+ break;
+ }
+ return NULL;
+}
+
+#endif /* SILCLIST_H */
projects / runtime.git / blobdiff