/*
 * ptrlist.c
 *
 * (C) Copyright Linus Torvalds 2003-2005
 */

///
// Pointer list manipulation
// -------------------------
//
// The data structure handled here is designed to hold pointers
// but two special cases need to be avoided or need special care:
// * NULL is used by {PREPARE,NEXT}_PTR_LIST() to indicate the end-of-list.
//   Thus, NULL can't be stored in lists using this API but is fine to
//   use with FOR_EACH_PTR() and its variants.
// * VOID is used to replace a removed pseudo 'usage'. Since phi-nodes
//   (OP_PHI) use a list to store their operands, a VOID in a phi-node
//   list must be ignored since it represents a removed operand. As
//   consequence, VOIDs must never be used as phi-node operand.
//   This is fine since phi-nodes make no sense with void values
//   but VOID is also used for invalid types and in case of errors.

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "ptrlist.h"
#include "allocate.h"
#include "compat.h"

__DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
__ALLOCATOR(struct ptr_list, "ptr list", ptrlist);

///
// get the size of a ptrlist
// @head: the head of the list
// @return: the size of the list given by @head.
int ptr_list_size(struct ptr_list *head)
{
	int nr = 0;

	if (head) {
		struct ptr_list *list = head;
		do {
			nr += list->nr - list->rm;
		} while ((list = list->next) != head);
	}
	return nr;
}

///
// test if a list is empty
// @head: the head of the list
// @return: ``true`` if the list is empty, ``false`` otherwise.
bool ptr_list_empty(const struct ptr_list *head)
{
	const struct ptr_list *list = head;

	if (!head)
		return true;

	do {
		if (list->nr - list->rm)
			return false;
	} while ((list = list->next) != head);

	return true;
}

///
// test is a list contains more than one element
// @head: the head of the list
// @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
bool ptr_list_multiple(const struct ptr_list *head)
{
	const struct ptr_list *list = head;
	int nr = 0;

	if (!head)
		return false;

	do {
		nr += list->nr - list->rm;
		if (nr > 1)
			return true;
	} while ((list = list->next) != head);

	return false;
}

///
// get the first element of a ptrlist
// @head: the head of the list
// @return: the first element of the list or ``NULL`` if the list is empty
void *first_ptr_list(struct ptr_list *head)
{
	struct ptr_list *list = head;

	if (!head)
		return NULL;

	while (list->nr == 0) {
		list = list->next;
		if (list == head)
			return NULL;
	}
	return PTR_ENTRY_NOTAG(list, 0);
}

///
// get the last element of a ptrlist
// @head: the head of the list
// @return: the last element of the list or ``NULL`` if the list is empty
void *last_ptr_list(struct ptr_list *head)
{
	struct ptr_list *list;

	if (!head)
		return NULL;
	list = head->prev;
	while (list->nr == 0) {
		if (list == head)
			return NULL;
		list = list->prev;
	}
	return PTR_ENTRY_NOTAG(list, list->nr-1);
}

///
// get the nth element of a ptrlist
// @head: the head of the list
// @return: the nth element of the list or ``NULL`` if the list is too short.
void *ptr_list_nth_entry(struct ptr_list *list, unsigned int idx)
{
	struct ptr_list *head = list;

	if (!head)
		return NULL;

	do {
		unsigned int nr = list->nr;

		if (idx < nr)
			return list->list[idx];
		else
			idx -= nr;
	} while ((list = list->next) != head);
	return NULL;
}

///
// linearize the entries of a list
//
// @head: the list to be linearized
// @arr: a ``void*`` array to fill with @head's entries
// @max: the maximum number of entries to store into @arr
// @return: the number of entries in the list.
//
// Linearize the entries of a list up to a total of @max,
// and return the number of entries in the list.
//
// The array to linearize into (@arr) should really
// be ``void *x[]``, but we want to let people fill in any kind
// of pointer array, so let's just call it ``void **``.
int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
{
	int nr = 0;
	if (head && max > 0) {
		struct ptr_list *list = head;

		do {
			int i = list->nr;
			nr += i;
			if (max == 0)
				continue;
			if (i > max) 
				i = max;
			memcpy(arr, list->list, i*sizeof(void *));
			arr += i;
			max -= i;
		} while ((list = list->next) != head);
	}
	return nr;
}

///
// pack a ptrlist
//
// @listp: a pointer to the list to be packed.
//
// When we've walked the list and deleted entries,
// we may need to re-pack it so that we don't have
// any empty blocks left (empty blocks upset the
// walking code).
void pack_ptr_list(struct ptr_list **listp)
{
	struct ptr_list *head = *listp;

	if (head) {
		struct ptr_list *entry = head;
		do {
			struct ptr_list *next;
restart:
			next = entry->next;
			if (!entry->nr) {
				struct ptr_list *prev;
				if (next == entry) {
					__free_ptrlist(entry);
					*listp = NULL;
					return;
				}
				prev = entry->prev;
				prev->next = next;
				next->prev = prev;
				__free_ptrlist(entry);
				if (entry == head) {
					*listp = next;
					head = next;
					entry = next;
					goto restart;
				}
			}
			entry = next;
		} while (entry != head);
	}
}		

///
// split a ptrlist block
// @head: the ptrlist block to be split
//
// A new block is inserted just after @head and the entries
// at the half end of @head are moved to this new block.
// The goal being to create space inside @head for a new entry.
void split_ptr_list_head(struct ptr_list *head)
{
	int old = head->nr, nr = old / 2;
	struct ptr_list *newlist = __alloc_ptrlist(0);
	struct ptr_list *next = head->next;

	old -= nr;
	head->nr = old;
	newlist->next = next;
	next->prev = newlist;
	newlist->prev = head;
	head->next = newlist;
	newlist->nr = nr;
	memcpy(newlist->list, head->list + old, nr * sizeof(void *));
	memset(head->list + old, 0xf0, nr * sizeof(void *));
}

///
// add an entry to a ptrlist
// @listp: a pointer to the list
// @ptr: the entry to add to the list
// @return: the address where the new entry is stored.
//
// :note: code must not use this function and should use
//	:func:`add_ptr_list` instead.
void **__add_ptr_list(struct ptr_list **listp, void *ptr)
{
	struct ptr_list *list = *listp;
	struct ptr_list *last = NULL; /* gcc complains needlessly */
	void **ret;
	int nr;

	if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
		struct ptr_list *newlist = __alloc_ptrlist(0);
		if (!list) {
			newlist->next = newlist;
			newlist->prev = newlist;
			*listp = newlist;
		} else {
			newlist->prev = last;
			newlist->next = list;
			list->prev = newlist;
			last->next = newlist;
		}
		last = newlist;
		nr = 0;
	}
	ret = last->list + nr;
	*ret = ptr;
	nr++;
	last->nr = nr;
	return ret;
}

///
// add a tagged entry to a ptrlist
// @listp: a pointer to the list
// @ptr: the entry to add to the list
// @tag: the tag to add to @ptr
// @return: the address where the new entry is stored.
//
// :note: code must not use this function and should use
//	:func:`add_ptr_list_tag` instead.
void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
{
	/* The low two bits are reserved for tags */
	assert((3 & (unsigned long)ptr) == 0);
	assert((~3 & tag) == 0);

	ptr = (void *)(tag | (unsigned long)ptr);

	return __add_ptr_list(listp, ptr);
}

///
// test if some entry is already present in a ptrlist
// @list: the head of the list
// @entry: the entry to test
// @return: ``true`` if the entry is already present, ``false`` otherwise.
bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry)
{
	const struct ptr_list *list = head;

	if (!head)
		return false;
	do {
		int nr = list->nr;
		int i;
		for (i = 0; i < nr; i++)
			if (list->list[i] == entry)
				return true;
	} while ((list = list->next) != head);
	return false;
}

///
// delete an entry from a ptrlist
// @list: a pointer to the list
// @entry: the item to be deleted
// @count: the minimum number of times @entry should be deleted or 0.
int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
{
	void *ptr;

	FOR_EACH_PTR(*list, ptr) {
		if (ptr == entry) {
			DELETE_CURRENT_PTR(ptr);
			if (!--count)
				goto out;
		}
	} END_FOR_EACH_PTR(ptr);
	assert(count <= 0);
out:
	pack_ptr_list(list);
	return count;
}

///
// replace an entry in a ptrlist
// @list: a pointer to the list
// @old_ptr: the entry to be replaced
// @new_ptr: the new entry
// @count: the minimum number of times @entry should be deleted or 0.
int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr,
	void *new_ptr, int count)
{
	void *ptr;

	FOR_EACH_PTR(*list, ptr) {
		if (ptr==old_ptr) {
			REPLACE_CURRENT_PTR(ptr, new_ptr);
			if (!--count)
				goto out;
		}
	}END_FOR_EACH_PTR(ptr);
	assert(count <= 0);
out:
	return count;
}

///
// remove the last entry of a ptrlist
// @head: a pointer to the list
// @return: the last element of the list or NULL if the list is empty.
//
// :note: this doesn't repack the list
void * undo_ptr_list_last(struct ptr_list **head)
{
	struct ptr_list *last, *first = *head;

	if (!first)
		return NULL;
	last = first;
	do {
		last = last->prev;
		if (last->nr) {
			void *ptr;
			int nr = --last->nr;
			ptr = last->list[nr];
			last->list[nr] = (void *)0xf1f1f1f1;
			return ptr;
		}
	} while (last != first);
	return NULL;
}

///
// remove the last entry and repack the list
// @head: a pointer to the list
// @return: the last element of the list or NULL if the list is empty.
void * delete_ptr_list_last(struct ptr_list **head)
{
	void *ptr = NULL;
	struct ptr_list *last, *first = *head;

	if (!first)
		return NULL;
	last = first->prev;
	if (last->nr)
		ptr = last->list[--last->nr];
	if (last->nr <=0) {
		first->prev = last->prev;
		last->prev->next = first;
		if (last == first)
			*head = NULL;
		__free_ptrlist(last);
	}
	return ptr;
}

///
// concat two ptrlists
// @a: the source list
// @b: a pointer to the destination list.
// The element of @a are added at the end of @b.
void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
{
	void *entry;
	FOR_EACH_PTR(a, entry) {
		add_ptr_list(b, entry);
	} END_FOR_EACH_PTR(entry);
}

///
// copy the elements of a list at the end of another list.
// @listp: a pointer to the destination list.
// @src: the head of the source list.
void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src)
{
	struct ptr_list *head, *tail;
	struct ptr_list *cur = src;
	int idx;

	if (!src)
		return;
	head = *listp;
	if (!head) {
		*listp = src;
		return;
	}

	tail = head->prev;
	idx = tail->nr;
	do {
		struct ptr_list *next;
		int nr = cur->nr;
		int i;
		for (i = 0; i < nr;) {
			void *ptr = cur->list[i++];
			if (!ptr)
				continue;
			if (idx >= LIST_NODE_NR) {
				struct ptr_list *prev = tail;
				tail = __alloc_ptrlist(0);
				prev->next = tail;
				tail->prev = prev;
				prev->nr = idx;
				idx = 0;
			}
			tail->list[idx++] = ptr;
		}

		next = cur->next;
		__free_ptrlist(cur);
		cur = next;
	} while (cur != src);

	tail->nr = idx;
	head->prev = tail;
	tail->next = head;
}

///
// free a ptrlist
// @listp: a pointer to the list
// Each blocks of the list are freed (but the entries
// themselves are not freed).
//
// :note: code must not use this function and should use
//	the macro :func:`free_ptr_list` instead.
void __free_ptr_list(struct ptr_list **listp)
{
	struct ptr_list *tmp, *list = *listp;

	if (!list)
		return;

	list->prev->next = NULL;
	while (list) {
		tmp = list;
		list = list->next;
		__free_ptrlist(tmp);
	}

	*listp = NULL;
}