diff options
Diffstat (limited to 'lib/list.c')
-rw-r--r-- | lib/list.c | 158 |
1 files changed, 158 insertions, 0 deletions
diff --git a/lib/list.c b/lib/list.c new file mode 100644 index 000000000..087a5f445 --- /dev/null +++ b/lib/list.c @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2008, 2009 Nicira Networks. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +#include <config.h> +#include "list.h" +#include <assert.h> + +/* Initializes 'list' as an empty list. */ +void +list_init(struct list *list) +{ + list->next = list->prev = list; +} + +/* Inserts 'elem' just before 'before'. */ +void +list_insert(struct list *before, struct list *elem) +{ + elem->prev = before->prev; + elem->next = before; + before->prev->next = elem; + before->prev = elem; +} + +/* Removes elements 'first' though 'last' (exclusive) from their current list, + then inserts them just before 'before'. */ +void +list_splice(struct list *before, struct list *first, struct list *last) +{ + if (first == last) + return; + last = last->prev; + + /* Cleanly remove 'first'...'last' from its current list. */ + first->prev->next = last->next; + last->next->prev = first->prev; + + /* Splice 'first'...'last' into new list. */ + first->prev = before->prev; + last->next = before; + before->prev->next = first; + before->prev = last; +} + +/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in + 'list'. */ +void +list_push_front(struct list *list, struct list *elem) +{ + list_insert(list->next, elem); +} + +/* Inserts 'elem' at the end of 'list', so that it becomes the back in + * 'list'. */ +void +list_push_back(struct list *list, struct list *elem) +{ + list_insert(list, elem); +} + +/* Puts 'elem' in the position currently occupied by 'position'. + * Afterward, 'position' is not part of a list. */ +void +list_replace(struct list *element, const struct list *position) +{ + element->next = position->next; + element->next->prev = element; + element->prev = position->prev; + element->prev->next = element; +} + +/* Adjusts pointers around 'list' to compensate for 'list' having been moved + * around in memory (e.g. as a consequence of realloc()). */ +void +list_moved(struct list *list) +{ + list->prev->next = list->next->prev = list; +} + +/* Removes 'elem' from its list and returns the element that followed it. + Undefined behavior if 'elem' is not in a list. */ +struct list * +list_remove(struct list *elem) +{ + elem->prev->next = elem->next; + elem->next->prev = elem->prev; + return elem->next; +} + +/* Removes the front element from 'list' and returns it. Undefined behavior if + 'list' is empty before removal. */ +struct list * +list_pop_front(struct list *list) +{ + struct list *front = list->next; + list_remove(front); + return front; +} + +/* Removes the back element from 'list' and returns it. + Undefined behavior if 'list' is empty before removal. */ +struct list * +list_pop_back(struct list *list) +{ + struct list *back = list->prev; + list_remove(back); + return back; +} + +/* Returns the front element in 'list'. + Undefined behavior if 'list' is empty. */ +struct list * +list_front(struct list *list) +{ + assert(!list_is_empty(list)); + return list->next; +} + +/* Returns the back element in 'list'. + Undefined behavior if 'list' is empty. */ +struct list * +list_back(struct list *list) +{ + assert(!list_is_empty(list)); + return list->prev; +} + +/* Returns the number of elements in 'list'. + Runs in O(n) in the number of elements. */ +size_t +list_size(const struct list *list) +{ + const struct list *e; + size_t cnt = 0; + + for (e = list->next; e != list; e = e->next) + cnt++; + return cnt; +} + +/* Returns true if 'list' is empty, false otherwise. */ +bool +list_is_empty(const struct list *list) +{ + return list->next == list; +} |