/*
* Copyright (c) 2001-2004 Jakub Jermar
* Copyright (c) 2013 Jiri Svoboda
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/** @addtogroup libc
* @{
*/
/** @file
*/
#ifndef _LIBC_LIST_H_
#define _LIBC_LIST_H_
#include <assert.h>
#include <member.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <trace.h>
#include <_bits/decls.h>
#ifndef __cplusplus
/**
* We don't define the macros in C++ to avoid polluting headers with
* namespaceless names. We don't actually need them, so this is fine.
* We still allow including the rest of the file (in `helenos` namespace)
* so that we can expose publicly visible types that have list_t members.
*/
/** Declare and initialize statically allocated list.
*
* @param name Name of the new statically allocated list.
*
*/
#define LIST_INITIALIZE(name) \
list_t name = LIST_INITIALIZER(name)
/** Initializer for statically allocated list.
*
* @code
* struct named_list {
* const char *name;
* list_t list;
* } var = {
* .name = "default name",
* .list = LIST_INITIALIZER(name_list.list)
* };
* @endcode
*
* @param name Name of the new statically allocated list.
*
*/
#define LIST_INITIALIZER(name) \
{ \
.head = { \
.prev = &(name).head, \
.next = &(name).head \
} \
}
#define list_get_instance(link, type, member) \
member_to_inst(link, type, member)
#define list_foreach(list, member, itype, iterator) \
for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
for (link_t *_link = (list).head.next; \
iterator = list_get_instance(_link, itype, member), \
_link != &(list).head; _link = _link->next)
#define list_foreach_rev(list, member, itype, iterator) \
for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
for (link_t *_link = (list).head.prev; \
iterator = list_get_instance(_link, itype, member), \
_link != &(list).head; _link = _link->prev)
/** Unlike list_foreach(), allows removing items while traversing a list.
*
* @code
* list_t mylist;
* typedef struct item {
* int value;
* link_t item_link;
* } item_t;
*
* //..
*
* // Print each list element's value and remove the element from the list.
* list_foreach_safe(mylist, cur_link, next_link) {
* item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
* printf("%d\n", cur_item->value);
* list_remove(cur_link);
* }
* @endcode
*
* @param list List to traverse.
* @param iterator Iterator to the current element of the list.
* The item this iterator points may be safely removed
* from the list.
* @param next_iter Iterator to the next element of the list.
*/
#define list_foreach_safe(list, iterator, next_iter) \
for (link_t *iterator = (list).head.next, \
*next_iter = iterator->next; \
iterator != &(list).head; \
iterator = next_iter, next_iter = iterator->next)
#define assert_link_not_used(link) \
assert(!link_used(link))
#define list_pop(list, type, member) \
((type *) list_pop_internal(list, \
(list_link_to_void(&(((type *) NULL)->member)) - NULL)))
#endif /* !__cplusplus */
__HELENOS_DECLS_BEGIN;
/** Doubly linked list link. */
typedef struct __adt_list_link {
struct __adt_list_link *prev; /**< Pointer to the previous item in the list. */
struct __adt_list_link *next; /**< Pointer to the next item in the list. */
} link_t;
/** Doubly linked list. */
typedef struct {
link_t head; /**< List head. Does not have any data. */
} list_t;
extern bool list_member(const link_t *, const list_t *);
extern void list_splice(list_t *, link_t *);
extern size_t list_count(const list_t *);
/** Returns true if the link is definitely part of a list. False if not sure. */
static inline bool link_in_use(const link_t *link)
{
return link->prev != NULL && link->next != NULL;
}
/** Initialize doubly-linked circular list link
*
* Initialize doubly-linked list link.
*
* @param link Pointer to link_t structure to be initialized.
*
*/
_NO_TRACE static inline void link_initialize(link_t *link)
{
link->prev = NULL;
link->next = NULL;
}
/** Initialize doubly-linked circular list
*
* Initialize doubly-linked circular list.
*
* @param list Pointer to list_t structure.
*
*/
_NO_TRACE static inline __CONSTEXPR void list_initialize(list_t *list)
{
list->head.prev = &list->head;
list->head.next = &list->head;
}
/** Insert item before another item in doubly-linked circular list.
*
*/
static inline void list_insert_before(link_t *lnew, link_t *lold)
{
lnew->next = lold;
lnew->prev = lold->prev;
lold->prev->next = lnew;
lold->prev = lnew;
}
/** Insert item after another item in doubly-linked circular list.
*
*/
static inline void list_insert_after(link_t *lnew, link_t *lold)
{
lnew->prev = lold;
lnew->next = lold->next;
lold->next->prev = lnew;
lold->next = lnew;
}
/** Add item to the beginning of doubly-linked circular list
*
* Add item to the beginning of doubly-linked circular list.
*
* @param link Pointer to link_t structure to be added.
* @param list Pointer to list_t structure.
*
*/
_NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
{
list_insert_after(link, &list->head);
}
/** Add item to the end of doubly-linked circular list
*
* Add item to the end of doubly-linked circular list.
*
* @param link Pointer to link_t structure to be added.
* @param list Pointer to list_t structure.
*
*/
_NO_TRACE static inline void list_append(link_t *link, list_t *list)
{
list_insert_before(link, &list->head);
}
/** Remove item from doubly-linked circular list
*
* Remove item from doubly-linked circular list.
*
* @param link Pointer to link_t structure to be removed from the list
* it is contained in.
*
*/
_NO_TRACE static inline void list_remove(link_t *link)
{
if ((link->prev != NULL) && (link->next != NULL)) {
link->next->prev = link->prev;
link->prev->next = link->next;
}
link_initialize(link);
}
/** Query emptiness of doubly-linked circular list
*
* Query emptiness of doubly-linked circular list.
*
* @param list Pointer to lins_t structure.
*
*/
_NO_TRACE static inline bool list_empty(const list_t *list)
{
return (list->head.next == &list->head);
}
/** Get first item in list.
*
* @param list Pointer to list_t structure.
*
* @return Head item of the list.
* @return NULL if the list is empty.
*
*/
static inline link_t *list_first(const list_t *list)
{
return ((list->head.next == &list->head) ? NULL : list->head.next);
}
/** Get last item in list.
*
* @param list Pointer to list_t structure.
*
* @return Head item of the list.
* @return NULL if the list is empty.
*
*/
static inline link_t *list_last(const list_t *list)
{
return (list->head.prev == &list->head) ? NULL : list->head.prev;
}
/** Get next item in list.
*
* @param link Current item link
* @param list List containing @a link
*
* @return Next item or NULL if @a link is the last item.
*/
static inline link_t *list_next(const link_t *link, const list_t *list)
{
return (link->next == &list->head) ? NULL : link->next;
}
/** Get previous item in list.
*
* @param link Current item link
* @param list List containing @a link
*
* @return Previous item or NULL if @a link is the first item.
*/
static inline link_t *list_prev(const link_t *link, const list_t *list)
{
return (link->prev == &list->head) ? NULL : link->prev;
}
/** Split or concatenate headless doubly-linked circular list
*
* Split or concatenate headless doubly-linked circular list.
*
* Note that the algorithm works both directions:
* concatenates splitted lists and splits concatenated lists.
*
* @param part1 Pointer to link_t structure leading the first
* (half of the headless) list.
* @param part2 Pointer to link_t structure leading the second
* (half of the headless) list.
*
*/
_NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
{
if (part1 == NULL || part2 == NULL)
return;
part1->prev->next = part2;
part2->prev->next = part1;
link_t *hlp = part1->prev;
part1->prev = part2->prev;
part2->prev = hlp;
}
/** Split headless doubly-linked circular list
*
* Split headless doubly-linked circular list.
*
* @param part1 Pointer to link_t structure leading
* the first half of the headless list.
* @param part2 Pointer to link_t structure leading
* the second half of the headless list.
*
*/
_NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
{
headless_list_split_or_concat(part1, part2);
}
/** Concatenate two headless doubly-linked circular lists
*
* Concatenate two headless doubly-linked circular lists.
*
* @param part1 Pointer to link_t structure leading
* the first headless list.
* @param part2 Pointer to link_t structure leading
* the second headless list.
*
*/
_NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
{
headless_list_split_or_concat(part1, part2);
}
/** Swap the contents of two lists.
*
* @param list1
* @param list2
*/
static inline void list_swap(list_t *list1, list_t *list2)
{
link_t *first1 = list_first(list1);
link_t *first2 = list_first(list2);
/* Detach both lists from their heads. */
headless_list_split(&list1->head, first1);
headless_list_split(&list2->head, first2);
/* Attach both lists to their new heads. */
headless_list_concat(&list1->head, first2);
headless_list_concat(&list2->head, first1);
}
/** Concatenate two lists
*
* Concatenate lists @a list1 and @a list2, producing a single
* list @a list1 containing items from both (in @a list1, @a list2
* order) and empty list @a list2.
*
* @param list1 First list and concatenated output
* @param list2 Second list and empty output.
*
*/
_NO_TRACE static inline void list_concat(list_t *list1, list_t *list2)
{
list_splice(list2, list1->head.prev);
}
/** Get n-th item in a list.
*
* @param list Pointer to link_t structure representing the list.
* @param n Item number (indexed from zero).
*
* @return n-th item of the list.
* @return NULL if no n-th item found.
*
*/
static inline link_t *list_nth(const list_t *list, size_t n)
{
size_t cnt = 0;
link_t *link = list_first(list);
while (link != NULL) {
if (cnt == n)
return link;
cnt++;
link = list_next(link, list);
}
return NULL;
}
/** Verify that argument type is a pointer to link_t (at compile time).
*
* This can be used to check argument type in a macro.
*/
static inline const void *list_link_to_void(const link_t *link)
{
return link;
}
/** Determine if link is used.
*
* @param link Link
* @return @c true if link is used, @c false if not.
*/
static inline bool link_used(link_t *link)
{
if (link->prev == NULL && link->next == NULL)
return false;
assert(link->prev != NULL && link->next != NULL);
return true;
}
static inline void *list_pop_internal(list_t *list, ptrdiff_t offset)
{
link_t *tmp = list_first(list);
if (tmp == NULL)
return NULL;
list_remove(tmp);
return (void *) (((uint8_t *) tmp) - offset);
}
__HELENOS_DECLS_END;
#endif
/** @}
*/