Nucleus

/*
 * This file implements Object Lists.  Objects can be a part of multiple lists
 * that can be managed automatically by the Object Manager.  This prevents
 * subsystems having to implement their own object lists for sub-objects.  Each
 * list is implemented as an Object itself, which allows the common object
 * routines to be used on them.
 */

#include <stdarg.h>
#include <nucleus/kernel.h>
#include <nucleus/memory.h>
#include <nucleus/object.h>

/* Structure for a List Entry */
struct ListEntry {
	struct ListEntry *prev, *next;
	Object *obj;
};
/* Structure for an Object List */
struct ObjectList {
	struct ListEntry *start, *end;
	size_t entries;
	ObjectType *type;
	enum ListMode mode;
	compare_callback_t compare;
	Spinlock lock;
};
/* Iterator */
struct Iterator {
	ObjectList *list;
	struct ListEntry *prev, *entry, *next;
	off_t pos;
};

void init_lock(Spinlock *lock);
void acquire(Spinlock *lock);
void release(Spinlock *lock);

/* Create an Object List */
ObjectList *
create_list(ObjectType *type, enum ListMode mode, ...)
{
	ObjectList *list = kmalloc(sizeof(ObjectList));
	init_lock(&list->lock);
	list->type = type;
	list->mode = mode;

	if (mode == LIST_ORDERED) {
		va_list args;
		va_start(args, mode);
		list->compare = va_arg(args, compare_callback_t);
		va_end(args);
	}

	return list;
}

/* Destroy an Object List */
void
destroy_list(ObjectList *list)
{
	while (list->entries > 0)
		remove(list, list->start->obj);
}

/* Add an Object to a List */
void
add(ObjectList *list, void *addr)
{
	Object *obj = addr;
	ASSERT(obj->magic == OBJECT_MAGIC);
	if (list->type && obj->type != list->type)
		return;

	if (list->mode != LIST_LOCKLESS)
		acquire(&list->lock);

	struct ListEntry *entry, *next;
	entry = kmalloc(sizeof(struct ListEntry));
	entry->obj = get(obj);
	list->entries++;

	if (!list->start) {
		/* Only item in list */
		list->start = list->end = entry;
	} else if (list->compare) {
		/* Find next item */
		for (next = list->start; next; next = next->next) {
			if (list->compare(next->obj, obj) > 0)
				break;
		}
		if (!next)
			goto end;
		/* Add in */
		entry->prev = next->prev;
		entry->next = next;
		next->prev = entry;
		if (entry->prev)
			entry->prev->next = entry;
		else
			list->start = entry;
	} else {
end:
		/* Add to end of list */
		list->end->next = entry;
		entry->prev = list->end;
		list->end = entry;
	}

	if (list->mode != LIST_LOCKLESS)
		release(&list->lock);
}

/* Remove an Object from a List */
void
remove(ObjectList *list, void *addr)
{
	Object *obj = addr;
	ASSERT(obj->magic == OBJECT_MAGIC);
	if (!list->start)
		return;
	if (list->type && obj->type != list->type)
		return;
	if (list->mode != LIST_LOCKLESS)
		acquire(&list->lock);

	/* Search for object */
	struct ListEntry *entry;
	for (entry = list->start;
	     entry && entry->obj != obj;
	     entry = entry->next);
	if (!entry) {
		release(&list->lock);
		return;
	}

	/* Unlink list */
	if (list->start == entry)
		list->start = entry->next;
	if (list->end == entry)
		list->end = entry->prev;

	/* Unlink neighbours */
	if (entry->prev)
		entry->prev->next = entry->next;
	if (entry->next)
		entry->next->prev = entry->prev;

	/* Release resources */
	if (__builtin_expect(!!(obj->usage), 1))
		put(obj);
	list->entries--;
	kfree(entry);
	if (list->mode != LIST_LOCKLESS)
		release(&list->lock);
}

/* Pop the first Object in a List */
void *
pop_from_start(ObjectList *list)
{
	if (!list->start)
		return NULL;
	if (list->mode != LIST_LOCKLESS)
		acquire(&list->lock);
	Object *head = get(list->start->obj);
	remove(list, head);
	if (list->mode != LIST_LOCKLESS)
		release(&list->lock);
	return head;
}

/* Pop the last Object in a List */
void *
pop_from_end(ObjectList *list)
{
	if (!list->end)
		return NULL;
	if (list->mode != LIST_LOCKLESS)
		acquire(&list->lock);
	Object *tail = get(list->end->obj);
	remove(list, tail);
	if (list->mode != LIST_LOCKLESS)
		release(&list->lock);
	return tail;
}

/* Count the number of Objects in a List */
size_t
count(ObjectList *list)
{
	return list->entries;
}

/* Get the nth Object in a List */
void *
get_nth_item(ObjectList *list, off_t n)
{
	if (n > list->entries - 1)
		return NULL;

	struct ListEntry *entry;
	if (n < (list->entries >> 1)) {
		for (entry = list->start; entry; entry = entry->next)
			if (n-- == 0)
				break;
	} else {
		n = list->entries - 1 - n;
		for (entry = list->end; entry; entry = entry->prev)
			if (n-- == 0)
				break;
	}
	return entry->obj;
}

/* Copy list */
ObjectList *
copy_list(ObjectList *list)
{
	ObjectList *newlist = create_list(list->type, list->mode,
	                                  list->compare);
	if (list->mode != LIST_LOCKLESS)
		acquire(&list->lock);
	struct ListEntry *entry;
	for (entry = list->start; entry; entry = entry->next)
		add(newlist, entry->obj);
	if (list->mode != LIST_LOCKLESS)
		release(&list->lock);
	return newlist;
}

/* Concatenate one list onto the end of another */
void
concat_list(ObjectList *src, ObjectList *dest)
{
	if (src->mode != LIST_LOCKLESS)
		acquire(&src->lock);
	struct ListEntry *entry;
	for (entry = src->start; entry; entry = entry->next)
		add(dest, entry->obj);
	if (src->mode != LIST_LOCKLESS)
		release(&src->lock);
}

/* Iterate a List */
Iterator *
iterate(ObjectList *list)
{
	Iterator *i = kmalloc(sizeof(Iterator));
	i->list = list;
	return i;
}

/* Get first iteratable element */
void *
first(Iterator *iter)
{
	iter->entry = iter->list->start;
	if (iter->entry) {
		iter->next = iter->entry->next;
		iter->pos = 0;
		return iter->entry->obj;
	}
	return NULL;
}

/* Get last iteratable element */
void *
last(Iterator *iter)
{
	iter->entry = iter->list->end;
	if (iter->entry) {
		iter->prev = iter->entry->prev;
		iter->pos = iter->list->entries - 1;
		return iter->entry->obj;
	}
	return NULL;
}

/* Get next iteratable element */
void *
next(Iterator *iter)
{
	iter->entry = iter->next;
	if (iter->entry) {
		iter->prev = iter->entry->prev;
		iter->next = iter->entry->next;
		iter->pos++;
		return iter->entry->obj;
	}
	return NULL;
}

/* Get previous iteratable element */
void *
prev(Iterator *iter)
{
	iter->entry = iter->prev;
	if (iter->entry) {
		iter->prev = iter->entry->prev;
		iter->next = iter->entry->next;
		iter->pos--;
		return iter->entry->obj;
	}
	return NULL;
}

/* End iteration */
int
done_iterating(Iterator *iter)
{
	kfree(iter);
	return 0;
}