list.c

/* the Music Player Daemon (MPD)
 * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com)
 * This project's homepage is: http://www.musicpd.org
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "list.h"
#include "utils.h"

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

static void makeListNodesArray(List * list)
{
	ListNode *node = list->firstNode;
	long i;

	if (!list->numberOfNodes)
		return;

	list->nodesArray = xrealloc(list->nodesArray,
				   sizeof(ListNode *) * list->numberOfNodes);

	for (i = 0; i < list->numberOfNodes; i++) {
		list->nodesArray[i] = node;
		node = node->nextNode;
	}
}

static void freeListNodesArray(List * list)
{
	if (!list->nodesArray)
		return;
	free(list->nodesArray);
	list->nodesArray = NULL;
}

List *makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys)
{
	List *list = xmalloc(sizeof(List));

	assert(list != NULL);

	list->sorted = 0;
	list->firstNode = NULL;
	list->lastNode = NULL;
	list->freeDataFunc = freeDataFunc;
	list->numberOfNodes = 0;
	list->nodesArray = NULL;
	list->strdupKeys = strdupKeys;

	return list;
}

ListNode *insertInListBeforeNode(List * list, ListNode * beforeNode, int pos,
				 const char *key, void *data)
{
	ListNode *node;

	assert(list != NULL);
	assert(key != NULL);
	/*assert(data!=NULL); */

	node = xmalloc(sizeof(ListNode));
	assert(node != NULL);

	node->nextNode = beforeNode;
	if (beforeNode == list->firstNode) {
		if (list->firstNode == NULL) {
			assert(list->lastNode == NULL);
			list->lastNode = node;
		} else {
			assert(list->lastNode != NULL);
			assert(list->lastNode->nextNode == NULL);
			list->firstNode->prevNode = node;
		}
		node->prevNode = NULL;
		list->firstNode = node;
	} else {
		if (beforeNode) {
			node->prevNode = beforeNode->prevNode;
			beforeNode->prevNode = node;
		} else {
			node->prevNode = list->lastNode;
			list->lastNode = node;
		}
		node->prevNode->nextNode = node;
	}

	if (list->strdupKeys)
		node->key = xstrdup(key);
	else
		node->key = key;

	node->data = data;

	list->numberOfNodes++;

	if (list->sorted) {
		list->nodesArray = xrealloc(list->nodesArray,
					   list->numberOfNodes *
					   sizeof(ListNode *));
		if (node == list->lastNode) {
			list->nodesArray[list->numberOfNodes - 1] = node;
		} else if (pos < 0)
			makeListNodesArray(list);
		else {
			memmove(list->nodesArray + pos + 1,
				list->nodesArray + pos,
				sizeof(ListNode *) * (list->numberOfNodes -
						      pos - 1));
			list->nodesArray[pos] = node;
		}
	}

	return node;
}

ListNode *insertInList(List * list, const char *key, void *data)
{
	ListNode *node;

	assert(list != NULL);
	assert(key != NULL);
	/*assert(data!=NULL); */

	node = xmalloc(sizeof(ListNode));
	assert(node != NULL);

	if (list->nodesArray)
		freeListNodesArray(list);

	if (list->firstNode == NULL) {
		assert(list->lastNode == NULL);
		list->firstNode = node;
	} else {
		assert(list->lastNode != NULL);
		assert(list->lastNode->nextNode == NULL);
		list->lastNode->nextNode = node;
	}

	if (list->strdupKeys)
		node->key = xstrdup(key);
	else
		node->key = key;

	node->data = data;
	node->nextNode = NULL;
	node->prevNode = list->lastNode;

	list->lastNode = node;

	list->numberOfNodes++;

	return node;
}

int insertInListWithoutKey(List * list, void *data)
{
	ListNode *node;

	assert(list != NULL);
	assert(data != NULL);

	node = xmalloc(sizeof(ListNode));
	assert(node != NULL);

	if (list->nodesArray)
		freeListNodesArray(list);

	if (list->firstNode == NULL) {
		assert(list->lastNode == NULL);
		list->firstNode = node;
	} else {
		assert(list->lastNode != NULL);
		assert(list->lastNode->nextNode == NULL);
		list->lastNode->nextNode = node;
	}

	node->key = NULL;
	node->data = data;
	node->nextNode = NULL;
	node->prevNode = list->lastNode;

	list->lastNode = node;

	list->numberOfNodes++;

	return 1;
}

/* if _key_ is not found, *_node_ is assigned to the node before which
	the info would be found */
int findNodeInList(List * list, const char *key, ListNode ** node, int *pos)
{
	long high;
	long low;
	long cur;
	ListNode *tmpNode;
	int cmp;

	assert(list != NULL);

	if (list->sorted && list->nodesArray) {
		high = list->numberOfNodes - 1;
		low = 0;
		cur = high;

		while (high > low) {
			cur = (high + low) / 2;
			tmpNode = list->nodesArray[cur];
			cmp = strcmp(tmpNode->key, key);
			if (cmp == 0) {
				*node = tmpNode;
				*pos = cur;
				return 1;
			} else if (cmp > 0)
				high = cur;
			else {
				if (low == cur)
					break;
				low = cur;
			}
		}

		cur = high;
		if (cur >= 0) {
			tmpNode = list->nodesArray[cur];
			*node = tmpNode;
			*pos = high;
			cmp = tmpNode ? strcmp(tmpNode->key, key) : -1;
			if (0 == cmp)
				return 1;
			else if (cmp > 0)
				return 0;
			else {
				*pos = -1;
				*node = NULL;
				return 0;
			}
		} else {
			*pos = 0;
			*node = list->firstNode;
			return 0;
		}
	} else {
		tmpNode = list->firstNode;

		while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
			tmpNode = tmpNode->nextNode;
		}

		*node = tmpNode;
		if (tmpNode)
			return 1;
	}

	return 0;
}

int findInList(List * list, const char *key, void **data)
{
	ListNode *node;
	int pos;

	if (findNodeInList(list, key, &node, &pos)) {
		if (data)
			*data = node->data;
		return 1;
	}

	return 0;
}

int deleteFromList(List * list, const char *key)
{
	ListNode *tmpNode;

	assert(list != NULL);

	tmpNode = list->firstNode;

	while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
		tmpNode = tmpNode->nextNode;
	}

	if (tmpNode != NULL)
		deleteNodeFromList(list, tmpNode);
	else
		return 0;

	return 1;
}

void deleteNodeFromList(List * list, ListNode * node)
{
	assert(list != NULL);
	assert(node != NULL);

	if (node->prevNode == NULL) {
		list->firstNode = node->nextNode;
	} else {
		node->prevNode->nextNode = node->nextNode;
	}
	if (node->nextNode == NULL) {
		list->lastNode = node->prevNode;
	} else {
		node->nextNode->prevNode = node->prevNode;
	}
	if (list->freeDataFunc) {
		list->freeDataFunc(node->data);
	}

	if (list->strdupKeys)
		xfree(node->key);
	free(node);
	list->numberOfNodes--;

	if (list->nodesArray) {
		freeListNodesArray(list);
		if (list->sorted)
			makeListNodesArray(list);
	}

}

void freeList(void *list)
{
	ListNode *tmpNode;
	ListNode *tmpNode2;

	assert(list != NULL);

	tmpNode = ((List *) list)->firstNode;

	if (((List *) list)->nodesArray)
		free(((List *) list)->nodesArray);

	while (tmpNode != NULL) {
		tmpNode2 = tmpNode->nextNode;
		if (((List *) list)->strdupKeys)
			xfree(tmpNode->key);
		if (((List *) list)->freeDataFunc) {
			((List *) list)->freeDataFunc(tmpNode->data);
		}
		free(tmpNode);
		tmpNode = tmpNode2;
	}

	free(list);
}

static void swapNodes(ListNode * nodeA, ListNode * nodeB)
{
	const char *key;
	void *data;

	assert(nodeA != NULL);
	assert(nodeB != NULL);

	key = nodeB->key;
	data = nodeB->data;

	nodeB->key = nodeA->key;
	nodeB->data = nodeA->data;

	nodeA->key = key;
	nodeA->data = data;
}

static void bubbleSort(ListNode ** nodesArray, long start, long end)
{
	long i;
	long j;
	ListNode *node;

	if (start >= end)
		return;

	for (j = start; j < end; j++) {
		for (i = end - 1; i >= start; i--) {
			node = nodesArray[i];
			if (strcmp(node->key, node->nextNode->key) > 0) {
				swapNodes(node, node->nextNode);
			}
		}
	}
}

static void quickSort(ListNode ** nodesArray, long start, long end)
{
	if (start >= end)
		return;
	else if (end - start < 5)
		bubbleSort(nodesArray, start, end);
	else {
		long i;
		ListNode *node;
		long pivot;
		ListNode *pivotNode;
		const char *pivotKey;

		List *startList = makeList(free, 0);
		List *endList = makeList(free, 0);
		long *startPtr = xmalloc(sizeof(long));
		long *endPtr = xmalloc(sizeof(long));
		*startPtr = start;
		*endPtr = end;
		insertInListWithoutKey(startList, (void *)startPtr);
		insertInListWithoutKey(endList, (void *)endPtr);

		while (startList->numberOfNodes) {
			start = *((long *)startList->lastNode->data);
			end = *((long *)endList->lastNode->data);

			if (end - start < 5) {
				bubbleSort(nodesArray, start, end);
				deleteNodeFromList(startList,
						   startList->lastNode);
				deleteNodeFromList(endList, endList->lastNode);
			} else {
				pivot = (start + end) / 2;
				pivotNode = nodesArray[pivot];
				pivotKey = pivotNode->key;

				for (i = pivot - 1; i >= start; i--) {
					node = nodesArray[i];
					if (strcmp(node->key, pivotKey) > 0) {
						pivot--;
						if (pivot > i) {
							swapNodes(node,
								  nodesArray
								  [pivot]);
						}
						swapNodes(pivotNode,
							  nodesArray[pivot]);
						pivotNode = nodesArray[pivot];
					}
				}
				for (i = pivot + 1; i <= end; i++) {
					node = nodesArray[i];
					if (strcmp(pivotKey, node->key) > 0) {
						pivot++;
						if (pivot < i) {
							swapNodes(node,
								  nodesArray
								  [pivot]);
						}
						swapNodes(pivotNode,
							  nodesArray[pivot]);
						pivotNode = nodesArray[pivot];
					}
				}

				deleteNodeFromList(startList,
						   startList->lastNode);
				deleteNodeFromList(endList, endList->lastNode);

				if (pivot - 1 - start > 0) {
					startPtr = xmalloc(sizeof(long));
					endPtr = xmalloc(sizeof(long));
					*startPtr = start;
					*endPtr = pivot - 1;
					insertInListWithoutKey(startList,
							       (void *)
							       startPtr);
					insertInListWithoutKey(endList,
							       (void *)endPtr);
				}

				if (end - pivot - 1 > 0) {
					startPtr = xmalloc(sizeof(long));
					endPtr = xmalloc(sizeof(long));
					*startPtr = pivot + 1;
					*endPtr = end;
					insertInListWithoutKey(startList,
							       (void *)
							       startPtr);
					insertInListWithoutKey(endList,
							       (void *)endPtr);
				}
			}
		}

		freeList(startList);
		freeList(endList);
	}
}

void sortList(List * list)
{
	assert(list != NULL);

	list->sorted = 1;

	if (list->numberOfNodes < 2)
		return;

	if (list->nodesArray)
		freeListNodesArray(list);
	makeListNodesArray(list);

	quickSort(list->nodesArray, 0, list->numberOfNodes - 1);
}