190 lines
10 KiB
C
190 lines
10 KiB
C
|
/* 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_is_singleton_named(list, prev, next) \
|
||
|
|
(((list) != NULL) && ((list)->prev == (list)->next) && ((list) == (list)->next))
|
||
|
|
|
||
|
|
#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_atleft_named(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. The
|
||
|
|
body of the loop is allowed to delete the iterator element from
|
||
|
|
memory. */
|
||
|
|
#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_is_singleton(list) list_is_singleton_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_ */
|