haiku.git

/*
 * Copyright 2003-2006, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
 * Distributed under the terms of the MIT License.
 */


#include <util/list.h>
#include <util/DoublyLinkedList.h>
#include <BytePointer.h>


#define GET_ITEM(list, item) ({ BytePointer<void> pointer((uint8*)item \
	- list->offset); &pointer; })
#define GET_LINK(list, item) ({ BytePointer<list_link> pointer((uint8*)item \
	+ list->offset); &pointer; })

STATIC_ASSERT(sizeof(DoublyLinkedListLink<void*>) == sizeof(list_link));


/** Initializes the list with a specified offset to the link
 *	structure in the items that will be part of the list.
 */

void
list_init_etc(struct list *list, int32 offset)
{
	list->link.next = list->link.prev = &list->link;
	list->offset = offset;
}


void
list_init(struct list *list)
{
	list_init_etc(list, 0);
}


/** Adds a link to the head of the list
 */

void
list_add_link_to_head(struct list *list, void *_link)
{
	list_link *link = (list_link *)_link;

	link->next = list->link.next;
	link->prev = &list->link;

	list->link.next->prev = link;
	list->link.next = link;

#if DEBUG_DOUBLY_LINKED_LIST
	ASSERT(link->next != link);
#endif
}


/** Adds a link to the tail of the list
 */

void
list_add_link_to_tail(struct list *list, void *_link)
{
	list_link *link = (list_link *)_link;

	link->next = &list->link;
	link->prev = list->link.prev;

	list->link.prev->next = link;
	list->link.prev = link;

#if DEBUG_DOUBLY_LINKED_LIST
	ASSERT(link->prev != link);
#endif
}


/** Removes a link from the list it's currently in.
 *	Note: the link has to be in a list when you call this function.
 */

void
list_remove_link(list_link *link)
{
	link->next->prev = link->prev;
	link->prev->next = link->next;

#if DEBUG_DOUBLY_LINKED_LIST
	link->prev = link->next = NULL;
#endif
}


static inline list_link *
get_next_link(struct list *list, list_link *link)
{
	if (link->next == &list->link)
		return NULL;

	return link->next;
}


static inline list_link *
get_prev_link(struct list *list, list_link *link)
{
	if (link->prev == &list->link)
		return NULL;

	return link->prev;
}


/** Gets the successor for the current item. If the passed
 *	item is NULL, it returns the first entry in the list,
 *	if there is one.
 *	Returns NULL if there aren't any more items in this list.
 */

void *
list_get_next_item(struct list *list, void *item)
{
	list_link *link;

	if (item == NULL)
		return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.next);

	link = get_next_link(list, GET_LINK(list, item));
	return link != NULL ? GET_ITEM(list, link) : NULL;
}


/** Gets the predecessor for the current item. If the passed
 *	item is NULL, it returns the last entry in the list,
 *	if there is one.
 *	Returns NULL if there aren't any previous items in this list.
 */

void *
list_get_prev_item(struct list *list, void *item)
{
	list_link *link;

	if (item == NULL)
		return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev);

	link = get_prev_link(list, GET_LINK(list, item));
	return link != NULL ? GET_ITEM(list, link) : NULL;
}


void *
list_get_last_item(struct list *list)
{
	return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev);
}


/** Adds an item to the end of the list.
 *	Similar to list_add_link_to_tail() but works on the item, not the link.
 */

void
list_add_item(struct list *list, void *item)
{
	list_add_link_to_tail(list, GET_LINK(list, item));
}


/** Removes an item from the list.
 *	Similar to list_remove_link() but works on the item, not the link.
 */

void
list_remove_item(struct list *list, void *item)
{
	list_remove_link(GET_LINK(list, item));
}


/** Inserts an item before another item in the list.
 *	If you pass NULL as \a before item, the item is added at the end of
 *	the list.
 */

void
list_insert_item_before(struct list *list, void *before, void *item)
{
	list_link *beforeLink;
	list_link *link;

	if (before == NULL) {
		list_add_item(list, item);
		return;
	}

	beforeLink = GET_LINK(list, before);
	link = GET_LINK(list, item);

	link->prev = beforeLink->prev;
	link->next = beforeLink;

	beforeLink->prev->next = link;
	beforeLink->prev = link;
}


/** Removes the first item in the list and returns it.
 *	Returns NULL if the list is empty.
 */

void *
list_remove_head_item(struct list *list)
{
	list_link *link;

	if (list_is_empty(list))
		return NULL;

	list_remove_link(link = list->link.next);
	return GET_ITEM(list, link);
}


/** Removes the last item in the list and returns it.
 *	Returns NULL if the list is empty.
 */

void *
list_remove_tail_item(struct list *list)
{
	list_link *link;

	if (list_is_empty(list))
		return NULL;

	list_remove_link(link = list->link.prev);
	return GET_ITEM(list, link);
}


/**	Moves the contents of the source list to the target list.
 *	The target list will be emptied before the items are moved;
 *	this is a very fast operation.
 */

void
list_move_to_list(struct list *sourceList, struct list *targetList)
{
	if (list_is_empty(sourceList)) {
		targetList->link.next = targetList->link.prev = &targetList->link;
		return;
	}

	*targetList = *sourceList;

	// correct link pointers to this list
	targetList->link.next->prev = &targetList->link;
	targetList->link.prev->next = &targetList->link;

	// empty source list
	sourceList->link.next = sourceList->link.prev = &sourceList->link;
}