summaryrefslogtreecommitdiff
path: root/sos-code-article6/sos/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'sos-code-article6/sos/list.h')
-rw-r--r--sos-code-article6/sos/list.h186
1 files changed, 186 insertions, 0 deletions
diff --git a/sos-code-article6/sos/list.h b/sos-code-article6/sos/list.h
new file mode 100644
index 0000000..67e72f3
--- /dev/null
+++ b/sos-code-article6/sos/list.h
@@ -0,0 +1,186 @@
+/* Copyright (C) 2001 David Decotigny
+
+ 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 the Free Software Foundation; either version 2
+ of the License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ USA.
+*/
+#ifndef _SOS_LIST_H_
+#define _SOS_LIST_H_
+
+/**
+ * @file list.h
+ *
+ * Circular doubly-linked lists implementation entirely based on C
+ * macros
+ */
+
+
+/* *_named are used when next and prev links are not exactly next
+ and prev. For instance when we have next_in_team, prev_in_team,
+ prev_global and next_global */
+
+#define list_init_named(list,prev,next) \
+ ((list) = NULL)
+
+#define list_singleton_named(list,item,prev,next) ({ \
+ (item)->next = (item)->prev = (item); \
+ (list) = (item); \
+})
+
+#define list_is_empty_named(list,prev,next) \
+ ((list) == NULL)
+
+#define list_get_head_named(list,prev,next) \
+ (list)
+
+#define list_get_tail_named(list,prev,next) \
+ ((list)?((list)->prev):NULL)
+
+/* Internal macro : insert before the head == insert at tail */
+#define __list_insert_atleft_named(before_this,item,prev,next) ({ \
+ (before_this)->prev->next = (item); \
+ (item)->prev = (before_this)->prev; \
+ (before_this)->prev = (item); \
+ (item)->next = (before_this); \
+})
+
+/* @note Before_this and item are expected to be valid ! */
+#define list_insert_before_named(list,before_this,item,prev,next) ({ \
+ __list_insert_atleft_named(before_this,item,prev,next); \
+ if ((list) == (before_this)) (list) = (item); \
+})
+
+/** @note After_this and item are expected to be valid ! */
+#define list_insert_after_named(list,after_this,item,prev,next) ({ \
+ (after_this)->next->prev = (item); \
+ (item)->next = (after_this)->next; \
+ (after_this)->next = (item); \
+ (item)->prev = (after_this); \
+})
+
+#define list_add_head_named(list,item,prev,next) ({ \
+ if (list) \
+ list_insert_before_named(list,list,item,prev,next); \
+ else \
+ list_singleton_named(list,item,prev,next); \
+ (list) = (item); \
+})
+
+#define list_add_tail_named(list,item,prev,next) ({ \
+ if (list) \
+ __list_insert_atleft_named(list,item,prev,next); \
+ else \
+ list_singleton_named(list,item,prev,next); \
+})
+
+/** @note NO check whether item really is in list ! */
+#define list_delete_named(list,item,prev,next) ({ \
+ if ( ((item)->next == (item)) && ((item)->prev == (item)) ) \
+ (item)->next = (item)->prev = (list) = NULL; \
+ else { \
+ (item)->prev->next = (item)->next; \
+ (item)->next->prev = (item)->prev; \
+ if ((item) == (list)) (list) = (item)->next; \
+ (item)->prev = (item)->next = NULL; \
+ } \
+})
+
+#define list_pop_head_named(list,prev,next) ({ \
+ typeof(list) __ret_elt = (list); \
+ list_delete_named(list,__ret_elt,prev,next); \
+ __ret_elt; })
+
+/** Loop statement that iterates through all of its elements, from
+ head to tail */
+#define list_foreach_forward_named(list,iterator,nb_elements,prev,next) \
+ for (nb_elements=0, (iterator) = (list) ; \
+ (iterator) && (!nb_elements || ((iterator) != (list))) ; \
+ nb_elements++, (iterator) = (iterator)->next )
+
+/** Loop statement that iterates through all of its elements, from
+ tail back to head */
+#define list_foreach_backward_named(list,iterator,nb_elements,prev,next) \
+ for (nb_elements=0, (iterator) = list_get_tail_named(list,prev,next) ; \
+ (iterator) && (!nb_elements || \
+ ((iterator) != list_get_tail_named(list,prev,next))) ; \
+ nb_elements++, (iterator) = (iterator)->prev )
+
+#define list_foreach_named list_foreach_forward_named
+
+/** True when we exitted early from the foreach loop (ie break) */
+#define list_foreach_early_break(list,iterator,nb_elements) \
+ ((list) && ( \
+ ((list) != (iterator)) || \
+ ( ((list) == (iterator)) && (nb_elements == 0)) ))
+
+/** Loop statement that also removes the item at each iteration */
+#define list_collapse_named(list,iterator,prev,next) \
+ for ( ; ({ ((iterator) = (list)) ; \
+ if (list) list_delete_named(list,iterator,prev,next) ; \
+ (iterator); }) ; )
+
+
+/*
+ * the same macros : assume that the prev and next fields are really
+ * named "prev" and "next"
+ */
+
+#define list_init(list) \
+ list_init_named(list,prev,next)
+
+#define list_singleton(list,item) \
+ list_singleton_named(list,item,prev,next)
+
+#define list_is_empty(list) \
+ list_is_empty_named(list,prev,next)
+
+#define list_get_head(list) \
+ list_get_head_named(list,prev,next) \
+
+#define list_get_tail(list) \
+ list_get_tail_named(list,prev,next) \
+
+/* @note Before_this and item are expected to be valid ! */
+#define list_insert_after(list,after_this,item) \
+ list_insert_after_named(list,after_this,item,prev,next)
+
+/* @note After_this and item are expected to be valid ! */
+#define list_insert_before(list,before_this,item) \
+ list_insert_before_named(list,before_this,item,prev,next)
+
+#define list_add_head(list,item) \
+ list_add_head_named(list,item,prev,next)
+
+#define list_add_tail(list,item) \
+ list_add_tail_named(list,item,prev,next)
+
+/* @note NO check whether item really is in list ! */
+#define list_delete(list,item) \
+ list_delete_named(list,item,prev,next)
+
+#define list_pop_head(list) \
+ list_pop_head_named(list,prev,next)
+
+#define list_foreach_forward(list,iterator,nb_elements) \
+ list_foreach_forward_named(list,iterator,nb_elements,prev,next)
+
+#define list_foreach_backward(list,iterator,nb_elements) \
+ list_foreach_backward_named(list,iterator,nb_elements,prev,next)
+
+#define list_foreach list_foreach_forward
+
+#define list_collapse(list,iterator) \
+ list_collapse_named(list,iterator,prev,next)
+
+#endif /* _SOS_LIST_H_ */