/* Libvisual - The audio visualisation framework.
*
* Copyright (C) 2004, 2005, 2006 Dennis Smit <ds@nerds-incorporated.org>
*
* List implementation from RCL.
* Copyright (C) 2002, 2003, 2004
* Dennis Smit <ds@nerds-incorporated.org>,
* Sepp Wijnands <mrrazz@nerds-incorporated.org>,
* Tom Wimmenhove <nohup@nerds-incorporated.org>
*
* Authors: Dennis Smit <ds@nerds-incorporated.org>
* Sepp Wijnands <mrrazz@nerds-incorporated.org>,
* Tom Wimmenhove <nohup@nerds-incorporated.org>
*
* $Id: lv_list.c,v 1.30 2006/01/22 13:23:37 synap Exp $
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1
* 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 Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser 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 <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include <lvconfig.h>
#include "lv_list.h"
#include "lv_log.h"
#include "lv_mem.h"
#define LIST_ITERCONTEXT(obj) (VISUAL_CHECK_CAST ((obj), ListIterContext))
typedef struct _ListIterContext ListIterContext;
struct _ListIterContext {
VisObject *object;
VisListEntry *cur;
};
static int list_destroy (VisCollection *collection);
static int list_size (VisCollection *collection);
static VisCollectionIter *list_iter (VisCollection *collection);
static void list_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index);
static int list_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
static void list_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
static void *list_iter_getdata (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
static int list_destroy (VisCollection *collection)
{
VisCollectionDestroyerFunc destroyer;
VisList *list = VISUAL_LIST (collection);
VisListEntry *le = NULL;
void *elem;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_COLLECTION_NULL);
destroyer = visual_collection_get_destroyer (collection);
/* Walk through the given list, possibly calling the destroyer for it */
if (destroyer == NULL) {
while ((elem = visual_list_next (list, &le)) != NULL)
visual_list_delete (list, &le);
} else {
while ((elem = visual_list_next (list, &le)) != NULL) {
destroyer (elem);
visual_list_delete (list, &le);
}
}
return VISUAL_OK;
}
static int list_size (VisCollection *collection)
{
VisList *list = VISUAL_LIST (collection);
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_COLLECTION_NULL);
return list->count;
}
static VisCollectionIter *list_iter (VisCollection *collection)
{
VisCollectionIter *iter;
ListIterContext *context;
VisList *list = VISUAL_LIST (collection);
context = visual_mem_new0 (ListIterContext, 1);
/* Do the VisObject initialization for the ListIterContext */
visual_object_initialize (VISUAL_OBJECT (context), TRUE, NULL);
context->cur = list->head;
iter = visual_collection_iter_new (list_iter_assign, list_iter_next, list_iter_has_more,
list_iter_getdata, collection, VISUAL_OBJECT (context));
return iter;
}
static void list_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index)
{
ListIterContext *context = LIST_ITERCONTEXT (itercontext);
VisList *list = VISUAL_LIST (collection);
int i;
context->cur = list->head;
if (context->cur == NULL)
return;
for (i = 0; i < index; i++) {
context->cur = context->cur->next;
if (context->cur == NULL)
return;
}
}
static void list_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
ListIterContext *context = LIST_ITERCONTEXT (itercontext);
VisListEntry *le = context->cur;
if (le == NULL)
return;
context->cur = le->next;
}
static int list_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
ListIterContext *context = LIST_ITERCONTEXT (itercontext);
if (context->cur == NULL)
return FALSE;
return TRUE;
}
static void *list_iter_getdata (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
{
ListIterContext *context = LIST_ITERCONTEXT (itercontext);
VisListEntry *le = context->cur;
if (le == NULL)
return NULL;
return le->data;
}
/**
* @defgroup VisList VisList
* @{
*/
/**
* Creates a new VisList structure.
* The VisList system is a double linked list implementation.
*
* @return A newly allocated VisList.
*/
VisList *visual_list_new (VisCollectionDestroyerFunc destroyer)
{
VisList *list;
list = visual_mem_new0 (VisList, 1);
visual_list_init (list, destroyer);
/* do the visobject initialization */
visual_object_set_allocated (VISUAL_OBJECT (list), TRUE);
visual_object_ref (VISUAL_OBJECT (list));
return list;
}
/**
*
*/
int visual_list_init (VisList *list, VisCollectionDestroyerFunc destroyer)
{
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
/* Do the VisObject initialization */
visual_object_clear (VISUAL_OBJECT (list));
visual_object_set_dtor (VISUAL_OBJECT (list), visual_collection_dtor);
visual_object_set_allocated (VISUAL_OBJECT (list), FALSE);
/* Set the VisCollection data */
visual_collection_set_destroyer (VISUAL_COLLECTION (list), destroyer);
visual_collection_set_destroy_func (VISUAL_COLLECTION (list), list_destroy);
visual_collection_set_size_func (VISUAL_COLLECTION (list), list_size);
visual_collection_set_iter_func (VISUAL_COLLECTION (list), list_iter);
/* Set the VisList data */
list->head = NULL;
list->tail = NULL;
list->count = 0;
return VISUAL_OK;
}
/**
* Go to the next entry in the list and return it's data element.
* This function will load the next entry in le and return a pointer
* to the data element.
*
* @see visual_list_prev
*
* @param list Pointer to the VisList we're traversing.
* @param le Pointer to a VisListEntry to store the next entry within
* and also to use as a reference to determine at which entry we're
* currently. To begin traversing do: VisListEntry *le = NULL and pass
* it as &le in the argument.
*
* @return The data element of the next entry, or NULL.
*/
void *visual_list_next (VisList *list, VisListEntry **le)
{
visual_log_return_val_if_fail (list != NULL, NULL);
visual_log_return_val_if_fail (le != NULL, NULL);
if (*le == NULL)
*le = list->head;
else
*le = (*le)->next;
if (*le != NULL)
return (*le)->data;
return NULL;
}
/**
* Go to the previous entry in the list and return it's data element.
* This function will load the previous entry in le and return a pointer
* to the data element.
*
* @see visual_list_next
*
* @param list Pointer to the VisList we're traversing.
* @param le Pointer to a VisListEntry to store the previous entry within
* and also to use as a reference to determine at which entry we're
* currently. To begin traversing at the end of the list do:
* VisList *le = NULL and pass it as &le in the argument.
*
* @return The data element of the previous entry, or NULL.
*/
void *visual_list_prev (VisList *list, VisListEntry **le)
{
visual_log_return_val_if_fail (list != NULL, NULL);
visual_log_return_val_if_fail (le != NULL, NULL);
if (!*le)
*le = list->tail;
else
*le = (*le)->prev;
if (*le)
return (*le)->data;
return NULL;
}
/**
* Get an data entry by index. This will give the pointer to an data
* element based on the index in the list.
*
* @param list Pointer to the VisList of which we want an element.
* @param index Index to determine which entry we want. The index starts at
* 1.
*
* @return The data element of the requested entry, or NULL.
*/
void *visual_list_get (VisList *list, int index)
{
VisListEntry *le = NULL;
void *data = NULL;
int i, lc;
visual_log_return_val_if_fail (list != NULL, NULL);
visual_log_return_val_if_fail (index >= 0, NULL);
lc = visual_collection_size (VISUAL_COLLECTION (list));
if (lc - 1 < index)
return NULL;
for (i = 0; i <= index; i++) {
data = visual_list_next (list, &le);
if (data == NULL)
return NULL;
}
return data;
}
/**
* Adds an entry at the beginning of the list.
*
* @param list Pointer to the VisList to which an entry needs to be added
* at it's head.
* @param data A pointer to the data that needs to be added to the list.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL on failure.
*/
int visual_list_add_at_begin (VisList *list, void *data)
{
VisListEntry *le;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
/* Allocate memory for new list entry */
le = visual_mem_new0 (VisListEntry, 1);
/* Assign data element */
le->data = data;
visual_list_chain_at_begin (list, le);
return VISUAL_OK;
}
/**
* Adds an entry at the end of the list.
*
* @param list Pointer to the VisList to which an entry needs to be added
* at it's tail.
* @param data A pointer to the data that needs to be added to the list.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL on failure.
*/
int visual_list_add (VisList *list, void *data)
{
VisListEntry *le;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
le = visual_mem_new0 (VisListEntry, 1);
/* Assign data element */
le->data = data;
visual_list_chain (list, le);
return VISUAL_OK;
}
/**
* Chains an VisListEntry at the beginning of the list.
*
* @param list Pointer to the VisList to which an entry needs to be added
* at it's tail.
* @param le A pointer to the VisListEntry that needs to be chained to the list.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
*/
int visual_list_chain_at_begin (VisList *list, VisListEntry *le)
{
VisListEntry *next;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
if (list->head == NULL) {
list->head = le;
list->tail = le;
le->prev = NULL;
le->next = NULL;
} else {
next = list->head;
le->next = next;
list->head = le;
le->prev = NULL;
}
/* Done */
list->count++;
return VISUAL_OK;
}
/**
* Chains an VisListEntry at the end of the list.
*
* @param list Pointer to the VisList to which an entry needs to be added
* at it's tail.
* @param le A pointer to the VisListEntry that needs to be chained to the list.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
*/
int visual_list_chain (VisList *list, VisListEntry *le)
{
VisListEntry *prev;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
/* Add list entry to list */
/* Is this the first entry for this list ? */
if (list->head == NULL) {
list->head = le;
list->tail = le;
le->prev = NULL;
le->next = NULL;
} else {
/* Nope, add to tail of this list */
prev = list->tail;
/* Exchange pointers */
prev->next = le;
le->prev = prev;
le->next = NULL;
/* Point tail to new entry */
list->tail = le;
}
/* Done */
list->count++;
return VISUAL_OK;
}
/**
* Unchain a VisListEntry from a VisList, entry won't be deleted. This function will only remove the
* links with it's VisList.
*
* @param list Pointer to the VisList from which an entry is unchained.
* @param le Pointer to a VisListEntry that is being unchained.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL
* on failure.
*/
int visual_list_unchain (VisList *list, VisListEntry *le)
{
VisListEntry *prev;
VisListEntry *next;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
/* Point new to le's previous entry */
prev = le->prev;
next = le->next;
/* Does it have a previous entry ? */
if (prev != NULL)
prev->next = next;
else
list->head = next;
if (next != NULL) /* It does have a next entry ? */
next->prev = prev;
else
list->tail = prev;
list->count--;
return VISUAL_OK;
}
/**
* Insert an entry in the middle of a list. By adding it
* after the le entry.
*
* @param list Pointer to the VisList in which an entry needs to be inserted.
* @param le Pointer to a VisListEntry after which the entry needs to be inserted.
* @param data Pointer to the data the new entry represents.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL, -VISUAL_ERROR_LIST_ENTRY_NULL or
* -VISUAL_ERROR_NULL on failure.
*/
int visual_list_insert (VisList *list, VisListEntry **le, void *data)
{
VisListEntry *prev, *next, *current;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
visual_log_return_val_if_fail (data != NULL, -VISUAL_ERROR_NULL);
current = visual_mem_new0 (VisListEntry, 1);
/* Assign data element */
current->data = data;
/* Add entry to list */
if (list->head == NULL && *le == NULL) {
/* First entry */
list->head = current;
list->tail = current;
} else if (*le == NULL) {
/* Insert entry at first position */
next = list->head;
/* Exchange pointers */
current->next = next;
next->prev = current;
/* Point head to current pointer */
list->head = current;
} else {
/* Insert entry at *le's position */
prev = *le;
next = prev->next;
current->prev = prev;
current->next = next;
prev->next = current;
if (next != NULL)
next->prev = current;
else
list->tail = current;
}
/* Hop to new entry */
*le = current;
/* Done */
list->count++;
return VISUAL_OK;
}
/**
* Removes an entry from the list.
*
* @param list A pointer to the VisList in which an entry needs to be deleted.
* @param le A pointer to the entry that needs to be deleted.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
*/
int visual_list_delete (VisList *list, VisListEntry **le)
{
VisListEntry *next;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
/* Valid list entry ? */
if (*le == NULL) {
visual_log (VISUAL_LOG_CRITICAL, "There is no list entry to delete");
return -VISUAL_ERROR_LIST_ENTRY_INVALID; /* Nope */
}
next = (*le)->next;
visual_list_unchain (list, *le);
visual_mem_free (*le);
*le = next;
return VISUAL_OK;
}
/**
* Removes and entry from the list and uses the VisListDestroyerFunc when present to clean up the data.
*
* @param list A pointer to the VisList in which an entry needs to be destroyed.
* @param le A pointer to the entry that needs to be destroyed.
*
* @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
*/
int visual_list_destroy (VisList *list, VisListEntry **le)
{
VisCollectionDestroyerFunc destroyer;
visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
destroyer = visual_collection_get_destroyer (VISUAL_COLLECTION (list));
if (destroyer != NULL)
destroyer ((*le)->data);
return visual_list_delete (list, le);
}
/**
* @}
*/