New list interface for fast tail access

1 files changed, 50 insertions, 46 deletions

diff --git a/src/list.c b/src/list.c
index 77a4042..2d1d777 100644
--- a/src/list.c
+++ b/src/list.c
@@ -2,76 +2,90 @@
 #include "util.h"
 
 void
-list_free(struct link *head, void (*free_item)(void *), int offset)
+list_init(struct list *list)
+{
+	list->head.prev = NULL;
+	list->head.next = &list->tail;
+	list->tail.prev = &list->head;
+	list->tail.next = NULL;
+}
+
+void
+list_free(struct list *list, void (*free_item)(void *), int offset)
 {
 	struct link *item;
 
-	while (head->next) {
-		item = link_pop(head->next);
+	ASSERT(list != NULL);
+
+	while (!list_empty(list)) {
+		item = link_pop(list->head.next);
 		free_item(((void *) item) - offset);
 	}
 }
 
 int
-list_empty(struct link *head)
+list_empty(struct list *list)
 {
-	ASSERT(head != NULL);
-	return head->next == NULL;
+	ASSERT(list != NULL);
+
+	return list->head.next == &list->tail;
 }
 
 int
-list_len(struct link *head)
+list_len(struct list *list)
 {
 	struct link *iter;
 	int len;
 
-	ASSERT(head != NULL);
+	ASSERT(list != NULL);
 
 	len = 0;
-	for (iter = head->next; iter; iter = iter->next)
+	for (LIST_ITER(list, iter))
 		len += 1;
 
 	return len;
 }
 
-int
-list_ffind(struct link *head, struct link *link)
+struct link *
+list_at(struct list *list, int n)
 {
-	struct link *iter;
+	ASSERT(list != NULL);
 
-	ASSERT(head != NULL);
-	for (iter = head->next; iter && iter != link; iter = iter->next);
-	return (iter == link);
+	return link_iter(list->head.next, n);
 }
 
-struct link *
-list_at(struct link *head, int n)
+void
+list_push_front(struct list *list, struct link *link)
 {
-	ASSERT(head != NULL);
-	return link_iter(head->next, n);
+	link_append(&list->head, link);
 }
 
 void
-list_push_front(struct link *head, struct link *link)
+list_push_back(struct list *list, struct link *link)
 {
-	link_append(head, link);
+	link_prepend(&list->tail, link);
 }
 
-void
-list_push_back(struct link *cur, struct link *link)
+struct link *
+list_pop_front(struct list *list)
 {
-	struct link *back;
+	ASSERT(list != NULL);
+
+	if (list_empty(list))
+		return NULL;
 
-	back = link_back(cur);
-	link_append(back, link);
+	return link_pop(list->head.next);
 }
 
 struct link *
-list_pop_front(struct link *head)
+list_pop_back(struct list *list)
 {
-	ASSERT(head != NULL);
-	if (!head->next) return NULL;
-	return link_pop(head->next);
+	ASSERT(list != NULL);
+
+	if (list_empty(list))
+		return NULL;
+
+	return link_pop(list->tail.prev);
 }
 
 void
@@ -103,11 +117,14 @@ link_append(struct link *cur, struct link *link)
 }
 
 struct link *
-link_back(struct link *link)
+link_iter(struct link *link, int n)
 {
-	ASSERT(link != NULL);
+	int i;
 
-	for (; link->next; link = link->next);
+	for (i = 0; i < n; i++) {
+		if (!link) return NULL;
+		link = link->next;
+	}
 
 	return link;
 }
@@ -124,16 +141,3 @@ link_pop(struct link *link)
 
 	return link;
 }
-
-struct link *
-link_iter(struct link *link, int n)
-{
-	int i;
-
-	for (i = 0; i < n; i++) {
-		if (!link) return NULL;
-		link = link->next;
-	}
-
-	return link;
-}