list.c

一个用于智能手机的多媒体库适合S60 WinCE的跨平台开发库

/*
 *			GPAC - Multimedia Framework C SDK
 *
 *			Copyright (c) Jean Le Feuvre 2000-2005
 *					All rights reserved
 *
 *  This file is part of GPAC / common tools sub-project
 *
 *  GPAC 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, or (at your option)
 *  any later version.
 *   
 *  GPAC 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 library; see the file COPYING.  If not, write to
 *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. 
 *
 */

#include <gpac/list.h>

/* GF_List modes, ONLY ONE CAN BE DEFINED

	linked-list
	#define GF_LIST_LINKED

	double navigation linked-list
	#define GF_LIST_DOUBLE_LINKED

	single step memory array
	#define GF_LIST_ARRAY

	default mode is array with step aloc of GF_LIST_STEP_ALLOC
*/

/*after some tuning, this seems to be the fastest mode on WINCE*/
#ifdef _WIN32_WCE
#define GF_LIST_LINKED
#else
#define GF_LIST_LINKED
//#define GF_LIST_ARRAY
#endif

//#define GF_LIST_STEP_ALLOC	10
#define GF_LIST_STEP_ALLOC	1


#if defined(GF_LIST_LINKED)

typedef struct tagIS
{
	struct tagIS *next;
	void *data;
} ItemSlot;

struct _tag_array
{
	struct tagIS *head;
	struct tagIS *tail;
	u32 entryCount;
	s32 foundEntryNumber;
	struct tagIS *foundEntry;
};


GF_EXPORT
GF_List * gf_list_new()
{
	GF_List *nlist = (GF_List *) malloc(sizeof(GF_List));
	if (! nlist) return NULL;
	nlist->head = nlist->foundEntry = NULL;
	nlist->tail = NULL;
	nlist->foundEntryNumber = -1;
	nlist->entryCount = 0;
	return nlist;
}

GF_EXPORT
void gf_list_del(GF_List *ptr)
{
	if (!ptr) return;
	while (ptr->entryCount) gf_list_rem(ptr, 0);
	free(ptr);
}

GF_EXPORT
void gf_list_reset(GF_List *ptr)
{
	while (ptr && ptr->entryCount) gf_list_rem(ptr, 0);
}

GF_EXPORT
GF_Err gf_list_add(GF_List *ptr, void* item)
{
	ItemSlot *entry;
    if (! ptr) return GF_BAD_PARAM;
	entry = (ItemSlot *) malloc(sizeof(ItemSlot));
	if (!entry) return GF_OUT_OF_MEM;
	entry->data = item;
	entry->next = NULL;
	if (! ptr->head) {
		ptr->head = entry;
		ptr->entryCount = 1;
	} else {
		ptr->entryCount += 1;
		ptr->tail->next = entry;
	}
	ptr->tail = entry;
	ptr->foundEntryNumber = ptr->entryCount - 1;
	ptr->foundEntry = entry;
	return GF_OK;
}

GF_EXPORT
u32 gf_list_count(GF_List *ptr)
{
	if (! ptr) return 0;
	return ptr->entryCount;
}

GF_EXPORT
void *gf_list_get(GF_List *ptr, u32 itemNumber)
{
	ItemSlot *entry;
	u32 i;

	if ((! ptr) || (itemNumber >= ptr->entryCount) ) return NULL;

	if ( itemNumber < (u32) ptr->foundEntryNumber ) {
		ptr->foundEntryNumber = 0;
		ptr->foundEntry = ptr->head;
	}
	entry = ptr->foundEntry;
	for (i = ptr->foundEntryNumber; i < itemNumber; i++ ) {
		entry = entry->next;
	}
	ptr->foundEntryNumber = itemNumber;
	ptr->foundEntry = entry;
	return (void *) entry->data;
}

GF_EXPORT
void *gf_list_last(GF_List *ptr)
{
	ItemSlot *entry;
	if (!ptr || !ptr->entryCount) return NULL;
	entry = ptr->head;
	while (entry->next) entry = entry->next;
	return entry->data;
}

GF_EXPORT
GF_Err gf_list_rem(GF_List *ptr, u32 itemNumber)
{
	ItemSlot *tmp, *tmp2;
	u32 i;

	/* !! if head is null (empty list)*/
	if ( (! ptr) || (! ptr->head) || (ptr->head && !ptr->entryCount) || (itemNumber >= ptr->entryCount) ) 
		return GF_BAD_PARAM;

	/*we delete the head*/
	if (! itemNumber) {
		tmp = ptr->head;
		ptr->head = ptr->head->next;
		ptr->entryCount --;
		ptr->foundEntry = ptr->head;
		ptr->foundEntryNumber = 0;
		free(tmp);
		/*that was the last entry, reset the tail*/
		if (!ptr->entryCount) {
			ptr->tail = ptr->head = ptr->foundEntry = NULL;
			ptr->foundEntryNumber = -1;
		}
		return GF_OK;
	}

	tmp = ptr->head;
	i = 0;
	while (i < itemNumber - 1) {
		tmp = tmp->next;
		i++;
	}
	tmp2 = tmp->next;
	tmp->next = tmp2->next;
	/*if we deleted the last entry, update the tail !!!*/
	if (! tmp->next || (ptr->tail == tmp2) ) {
		ptr->tail = tmp;
		tmp->next = NULL;
	}

	free(tmp2);
	ptr->entryCount --;
	ptr->foundEntry = ptr->head;
	ptr->foundEntryNumber = 0;

	return GF_OK;
}

GF_EXPORT
GF_Err gf_list_rem_last(GF_List *ptr)
{
	return gf_list_rem(ptr, ptr->entryCount-1);
}

GF_EXPORT
GF_Err gf_list_insert(GF_List *ptr, void *item, u32 position)
{
	u32 i;
	ItemSlot *tmp, *tmp2;

	if (!ptr || !item) return GF_BAD_PARAM;
	/*if last entry or first of an empty array...*/
	if (position >= ptr->entryCount) return gf_list_add(ptr, item);

	tmp2 = (ItemSlot *) malloc(sizeof(ItemSlot));
	tmp2->data = item;
	tmp2->next = NULL;
	/*special case for the head*/
	if (position == 0) {
		tmp2->next = ptr->head;
		ptr->head = tmp2;
		ptr->entryCount ++;
		ptr->foundEntry = tmp2;
		ptr->foundEntryNumber = 0;
		return GF_OK;
	}
	tmp = ptr->head;
	for (i = 1; i < position; i++) {
		tmp = tmp->next;
		if (!tmp)
			break;
	}
	tmp2->next = tmp->next;
	tmp->next = tmp2;
	ptr->entryCount ++;
	ptr->foundEntry = tmp2;
	ptr->foundEntryNumber = i;
	return GF_OK;
}

#elif defined(GF_LIST_DOUBLE_LINKED)


typedef struct tagIS
{
	struct tagIS *next;
	struct tagIS *prev;
	void *data;
} ItemSlot;

struct _tag_array
{
	struct tagIS *head;
	struct tagIS *tail;
	u32 entryCount;
	s32 foundEntryNumber;
	struct tagIS *foundEntry;
};


GF_EXPORT
GF_List * gf_list_new()
{
	GF_List *nlist = (GF_List *) malloc(sizeof(GF_List));
	if (! nlist) return NULL;
	nlist->head = nlist->foundEntry = NULL;
	nlist->tail = NULL;
	nlist->foundEntryNumber = -1;
	nlist->entryCount = 0;
	return nlist;
}

GF_EXPORT
void gf_list_del(GF_List *ptr)
{
	if (!ptr) return;
	while (ptr->entryCount) {
		gf_list_rem(ptr, 0);
	}
	free(ptr);
}

GF_EXPORT
void gf_list_reset(GF_List *ptr)
{
	while (ptr && ptr->entryCount) gf_list_rem(ptr, 0);
}

GF_EXPORT
GF_Err gf_list_add(GF_List *ptr, void* item)
{
	ItemSlot *entry;
    if (! ptr) return GF_BAD_PARAM;
	entry = (ItemSlot *) malloc(sizeof(ItemSlot));
	if (!entry) return GF_OUT_OF_MEM;
	entry->data = item;
	entry->next = entry->prev = NULL;

	if (! ptr->head) {
		ptr->head = entry;
		ptr->entryCount = 1;
	} else {
		ptr->entryCount += 1;
		entry->prev = ptr->tail;
		ptr->tail->next = entry;
	}
	ptr->tail = entry;
	ptr->foundEntryNumber = ptr->entryCount - 1;
	ptr->foundEntry = entry;
	return GF_OK;
}


GF_EXPORT
u32 gf_list_count(GF_List *ptr)
{
	if (! ptr) return 0;
	return ptr->entryCount;
}

GF_EXPORT
void *gf_list_get(GF_List *ptr, u32 itemNumber)
{
	ItemSlot *entry;
	u32 i;

	if (!ptr || !ptr->head || (itemNumber >= ptr->entryCount) ) return NULL;

	if (!itemNumber) {
		ptr->foundEntry = ptr->head;
		ptr->foundEntryNumber = 0;
		return ptr->head->data;
	}

	entry = ptr->foundEntry;
	if ( itemNumber < (u32) ptr->foundEntryNumber ) {
		for (i = ptr->foundEntryNumber; i > itemNumber; i-- ) {
			entry = entry->prev;
		}
	} else {
		for (i = ptr->foundEntryNumber; i < itemNumber; i++ ) {
			entry = entry->next;
		}
	}
	ptr->foundEntryNumber = itemNumber;
	ptr->foundEntry = entry;
	return (void *) entry->data;
}

GF_EXPORT
void *gf_list_last(GF_List *ptr)
{
	if(!ptr || !ptr->tail) return NULL;
	return ptr->tail->data;
}

GF_EXPORT
GF_Err gf_list_rem(GF_List *ptr, u32 itemNumber)
{
	ItemSlot *tmp;
	u32 i;

	/* !! if head is null (empty list)*/
	if ( (! ptr) || (! ptr->head) || (ptr->head && !ptr->entryCount) || (itemNumber >= ptr->entryCount) ) 
		return GF_BAD_PARAM;

	/*we delete the head*/
	if (! itemNumber) {
		tmp = ptr->head;
		ptr->head = ptr->head->next;

		ptr->entryCount --;
		ptr->foundEntry = ptr->head;
		ptr->foundEntryNumber = 0;
		free(tmp);

		/*that was the last entry, reset the tail*/
		if (!ptr->entryCount) {
			ptr->tail = ptr->head = ptr->foundEntry = NULL;
			ptr->foundEntryNumber = -1;
		} else {
			ptr->head->prev = NULL;
		}
		return GF_OK;
	}
	else if (itemNumber==ptr->entryCount-1) {
		tmp = ptr->tail;
		ptr->tail = tmp->prev;
		ptr->tail->next = NULL;
		ptr->entryCount--;
		if (ptr->foundEntry==tmp) {
			ptr->foundEntry = ptr->tail;
			ptr->foundEntryNumber = ptr->entryCount-1;
		}
		free(tmp);
		return GF_OK;
	}

	tmp = ptr->foundEntry;
	if ( itemNumber < (u32) ptr->foundEntryNumber ) {
		for (i = ptr->foundEntryNumber; i > itemNumber; i-- ) {
			tmp = tmp->prev;
		}
	} else {
		for (i = ptr->foundEntryNumber; i < itemNumber; i++ ) {
			tmp = tmp->next;
		}
	}
	tmp->prev->next = tmp->next;
	tmp->next->prev = tmp->prev;
	if (tmp==ptr->foundEntry) ptr->foundEntry = tmp->next;
	free(tmp);
	ptr->entryCount--;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_list_rem_last(GF_List *ptr)
{
	return gf_list_rem(ptr, ptr->entryCount-1);
}

GF_EXPORT
GF_Err gf_list_insert(GF_List *ptr, void *item, u32 position)
{
	u32 i;
	ItemSlot *tmp, *tmp2;

	if (!ptr || !item) return GF_BAD_PARAM;
	/*if last entry or first of an empty array...*/
	if (position >= ptr->entryCount) return gf_list_add(ptr, item);
	tmp2 = (ItemSlot *) malloc(sizeof(ItemSlot));
	tmp2->data = item;
	tmp2->next = tmp2->prev = NULL;
	/*special case for the head*/
	if (position == 0) {
		ptr->head->prev = tmp2;
		tmp2->next = ptr->head;
		ptr->head = tmp2;
		ptr->entryCount ++;
		ptr->foundEntry = tmp2;
		ptr->foundEntryNumber = 0;
		return GF_OK;
	}

	tmp = ptr->foundEntry;
	if ( position < (u32) ptr->foundEntryNumber ) {
		for (i = ptr->foundEntryNumber; i >= position; i-- ) {
			tmp = tmp->prev;
		}
		tmp = tmp->prev;
	} else {
		for (i = ptr->foundEntryNumber; i < position; i++ ) {
			tmp = tmp->next;
		}
	}
	tmp2->next = tmp->next;
	tmp2->next->prev = tmp2;
	tmp2->prev = tmp;
	tmp2->prev->next = tmp2;
	ptr->entryCount ++;
	ptr->foundEntry = tmp2;
	ptr->foundEntryNumber = position;
	return GF_OK;
}

#elif defined(GF_LIST_ARRAY)

struct _tag_array
{
	void **slots;
	u32 entryCount;
};


GF_EXPORT
GF_List * gf_list_new()
{
	GF_List *nlist = (GF_List *) malloc(sizeof(GF_List));
	if (! nlist) return NULL;
	nlist->slots = NULL;
	nlist->entryCount = 0;
	return nlist;
}

GF_EXPORT
void gf_list_del(GF_List *ptr)
{
	if (!ptr) return;
	free(ptr->slots);
	free(ptr);
}

GF_EXPORT
GF_Err gf_list_add(GF_List *ptr, void* item)
{
    if (! ptr) return GF_BAD_PARAM;

	ptr->entryCount ++;
	ptr->slots = (void **) realloc(ptr->slots, ptr->entryCount*sizeof(void*));
	if (!ptr->slots) {
		ptr->entryCount = 0;
		return GF_OUT_OF_MEM;
	}
	ptr->slots[ptr->entryCount-1] = item;
	return GF_OK;
}

GF_EXPORT
u32 gf_list_count(GF_List *ptr)
{
	return ptr ? ptr->entryCount : 0;
}

GF_EXPORT
void *gf_list_get(GF_List *ptr, u32 itemNumber)
{
	if(!ptr || (itemNumber >= ptr->entryCount)) return NULL;
	return ptr->slots[itemNumber];
}

GF_EXPORT
void *gf_list_last(GF_List *ptr)
{
	if(!ptr || !ptr->entryCount) return NULL;
	return ptr->slots[ptr->entryCount-1];
}


/*WARNING: itemNumber is from 0 to entryCount - 1*/
GF_EXPORT
GF_Err gf_list_rem(GF_List *ptr, u32 itemNumber)
{
	u32 i;
	if ( !ptr || !ptr->slots || !ptr->entryCount) return GF_BAD_PARAM;
	i = ptr->entryCount - itemNumber - 1;
	if (i) memmove(&ptr->slots[itemNumber], & ptr->slots[itemNumber +1], sizeof(void *)*i);
	ptr->slots[ptr->entryCount-1] = NULL;
	ptr->entryCount -= 1;
	ptr->slots = (void **) realloc(ptr->slots, sizeof(void*)*ptr->entryCount);
	return GF_OK;
}

GF_EXPORT
GF_Err gf_list_rem_last(GF_List *ptr)
{
	if ( !ptr || !ptr->slots || !ptr->entryCount) return GF_BAD_PARAM;
	ptr->entryCount -= 1;
	ptr->slots = (void **) realloc(ptr->slots, sizeof(void*)*ptr->entryCount);
	return GF_OK;
}


/*WARNING: position is from 0 to entryCount - 1*/
GF_EXPORT
GF_Err gf_list_insert(GF_List *ptr, void *item, u32 position)
{
	u32 i;
	if (!ptr || !item) return GF_BAD_PARAM;
	/*if last entry or first of an empty array...*/
	if (position >= ptr->entryCount) return gf_list_add(ptr, item);
	ptr->slots = (void **) realloc(ptr->slots, (ptr->entryCount+1)*sizeof(void*));
	i = ptr->entryCount - position;
	memmove(&ptr->slots[position + 1], &ptr->slots[position], sizeof(void *)*i);
	ptr->entryCount++;
	ptr->slots[position] = item;
	return GF_OK;
}

GF_EXPORT
void gf_list_reset(GF_List *ptr)
{
	if (ptr) {
		ptr->entryCount = 0;
		free(ptr->slots);
		ptr->slots = NULL;
	}
}

#else


struct _tag_array
{
	void **slots;
	u32 entryCount;
	u32 allocSize;
};

GF_EXPORT
GF_List * gf_list_new()
{
	GF_List *nlist;

	nlist = (GF_List *) malloc(sizeof(GF_List));
	if (! nlist) return NULL;
	
	nlist->slots = NULL;
	nlist->entryCount = 0;
	nlist->allocSize = 0;
	return nlist;
}

GF_EXPORT
void gf_list_del(GF_List *ptr)
{
	if (!ptr) return;
	free(ptr->slots);
	free(ptr);
}

static void realloc_chain(GF_List *ptr)
{
	ptr->allocSize += GF_LIST_STEP_ALLOC;
	ptr->slots = realloc(ptr->slots, ptr->allocSize*sizeof(void*));
}

GF_EXPORT
GF_Err gf_list_add(GF_List *ptr, void* item)
{
    if (! ptr) return GF_BAD_PARAM;
	if (ptr->allocSize==ptr->entryCount) realloc_chain(ptr);
	if (!ptr->slots) return GF_OUT_OF_MEM;

	ptr->slots[ptr->entryCount] = item;
	ptr->entryCount ++;
	return GF_OK;
}

GF_EXPORT
u32 gf_list_count(GF_List *ptr)
{
	if (!ptr) return 0;
	return ptr->entryCount;
}

GF_EXPORT
void *gf_list_get(GF_List *ptr, u32 itemNumber)
{
	if(!ptr || (itemNumber >= ptr->entryCount)) return NULL;
	return ptr->slots[itemNumber];
}

GF_EXPORT
void *gf_list_last(GF_List *ptr)
{
	if(!ptr || !ptr->entryCount) return NULL;
	return ptr->slots[ptr->entryCount-1];
}


/*WARNING: itemNumber is from 0 to entryCount - 1*/
GF_EXPORT
GF_Err gf_list_rem(GF_List *ptr, u32 itemNumber)
{
	u32 i;
	if ( !ptr || !ptr->slots || !ptr->entryCount) return GF_BAD_PARAM;
	i = ptr->entryCount - itemNumber - 1;
	if (i) memmove(&ptr->slots[itemNumber], & ptr->slots[itemNumber +1], sizeof(void *)*i);
	ptr->slots[ptr->entryCount-1] = NULL;
	ptr->entryCount -= 1;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_list_rem_last(GF_List *ptr)
{
	u32 i;
	if ( !ptr || !ptr->slots || !ptr->entryCount) return GF_BAD_PARAM;
	ptr->slots[ptr->entryCount-1] = NULL;
	ptr->entryCount -= 1;
	return GF_OK;
}

/*WARNING: position is from 0 to entryCount - 1*/
GF_EXPORT
GF_Err gf_list_insert(GF_List *ptr, void *item, u32 position)
{
	u32 i;
	if (!ptr || !item) return GF_BAD_PARAM;
	/*if last entry or first of an empty array...*/
	if (position >= ptr->entryCount) return gf_list_add(ptr, item);
	if (ptr->allocSize==ptr->entryCount) realloc_chain(ptr);

	i = ptr->entryCount - position;
	memmove(&ptr->slots[position + 1], &ptr->slots[position], sizeof(void *)*i);
	ptr->entryCount++;
	ptr->slots[position] = item;
	return GF_OK;
}

GF_EXPORT
void gf_list_reset(GF_List *ptr)
{
	if (ptr) ptr->entryCount = 0;
}

#endif

GF_EXPORT
s32 gf_list_find(GF_List *ptr, void *item)
{
	u32 i, count;
	count = gf_list_count(ptr);
	for (i=0; i<count; i++) {
		if (gf_list_get(ptr, i) == item) return (s32) i;
	}
	return -1;
}

GF_EXPORT
s32 gf_list_del_item(GF_List *ptr, void *item)
{
	s32 i = gf_list_find(ptr, item);
	if (i>=0) gf_list_rem(ptr, (u32) i);
	return i;
}

GF_EXPORT
void *gf_list_enum(GF_List *ptr, u32 *pos)
{
	void *res = gf_list_get(ptr, *pos);
	(*pos)++;
	return res;
}