/* * List.c -- Implementation of list module. * * Authors : Patrick Lecoanet. * Creation date : Tue Mar 15 17:18:17 1994 * * $Id$ */ /* * Copyright (c) 1993 - 2005 CENA, Patrick Lecoanet -- * * See the file "Copyright" for information on usage and redistribution * of this file, and for a DISCLAIMER OF ALL WARRANTIES. * */ /* ********************************************************************************** * * This modules exports the following functions: * - ZnListNew * - ZnListDuplicate * - ZnListEmpty * - ZnListFromArray * - ZnListArray * - ZnListFree * - ZnListSize * - ZnListAssertSize * - ZnListAdd * - ZnListAt * - ZnListAtPut * - ZnListDelete * - ZnListTruncate * - ZnListDetect * - ZnListDo * * To appear soon: * - ZnListCollect * - ZnListReject * * And the following variables: * ********************************************************************************** */ /* ********************************************************************************** * * Included files * ********************************************************************************** */ #include "Types.h" #include "List.h" #include #include #include /* ********************************************************************************** * * Constants * ********************************************************************************** */ static const char rcs_id[]="$Id$"; static const char compile_id[]="$Compile: " __FILE__ " " __DATE__ " " __TIME__ " $"; #define MAX_CHUNCK_SIZE 1024 #ifndef MAX # define MAX(a, b) ((a) > (b) ? (a) : (b)) #endif #ifndef MIN # define MIN(a, b) ((a) < (b) ? (a) : (b)) #endif /* ********************************************************************************** * * New types * ********************************************************************************** */ typedef struct { char *list; unsigned long elem_size; unsigned long alloc_size; unsigned long used_size; } _ZnList; /* ********************************************************************************** * * GrowIfNeeded -- * Enlarge a list so that it has min_size available. Take care of * static storage. * ********************************************************************************** */ static void GrowIfNeeded(_ZnList *list, unsigned int min_size) { if (list->used_size+min_size <= list->alloc_size) { return; } if (list->alloc_size == 0) { if (list->list == NULL) { /* Normal case if we have created a zero sized list */ list->alloc_size = min_size; list->list = ZnMalloc(list->alloc_size*list->elem_size); } else { /* Case of a list made by ZnListFromArray. If we try to make it grow we need to reallocate and copy. */ char *new_list; list->alloc_size = list->used_size+min_size; new_list = ZnMalloc(list->alloc_size*list->elem_size); memcpy(new_list, list->list, list->used_size*list->elem_size); list->list = new_list; } } else { list->alloc_size = MAX(MIN(list->alloc_size*2, MAX_CHUNCK_SIZE), list->alloc_size+min_size); list->list = ZnRealloc(list->list, list->alloc_size*list->elem_size); } memset(list->list+(list->used_size*list->elem_size), 0, (list->alloc_size-list->used_size)*list->elem_size); } /* ********************************************************************************** * * ZnListNew -- * Return a new empty list 'initial_size' large. * ********************************************************************************** */ ZnList ZnListNew(unsigned int initial_size, unsigned int element_size) { _ZnList *new_list; if (element_size == 0) { element_size = 1; } new_list = ZnMalloc(sizeof(_ZnList)); new_list->alloc_size = initial_size; new_list->used_size = 0; new_list->elem_size = element_size; if (initial_size) { unsigned long size = new_list->alloc_size*new_list->elem_size; new_list->list = ZnMalloc(size); memset(new_list->list, 0, size); } else { new_list->list = NULL; } return (ZnList) new_list; } /* ********************************************************************************** * * ZnListDuplicate -- * Return a copy of the list given as parameter. * ********************************************************************************** */ ZnList ZnListDuplicate(ZnList list) { _ZnList *cur_list = (_ZnList *) list; _ZnList *new_list; new_list = ZnMalloc(sizeof(_ZnList)); new_list->alloc_size = cur_list->alloc_size == 0 ? cur_list->used_size : cur_list->alloc_size; new_list->used_size = cur_list->used_size; new_list->elem_size = cur_list->elem_size; if (new_list->alloc_size) { unsigned long used_size = new_list->used_size*new_list->elem_size; unsigned long size = new_list->alloc_size*new_list->elem_size; new_list->list = ZnMalloc(size); if (used_size) { memcpy(new_list->list, cur_list->list, used_size); } memset(new_list->list + used_size, 0, size - used_size); } else { new_list->list = NULL; } return (ZnList) new_list; } /* ********************************************************************************** * * ZnListEmpty -- * Clear out a list, kkeping its allocated size. * ********************************************************************************** */ void ZnListEmpty(ZnList list) { _ZnList *cur_list = (_ZnList *) list; cur_list->used_size = 0; } /* ********************************************************************************** * * ZnListFromArray -- * Return a list filled from the given array. * ********************************************************************************** */ ZnList ZnListFromArray(void *array, unsigned int array_size, unsigned int element_size) { _ZnList *new_list; new_list = (_ZnList *) ZnListNew(0, element_size); new_list->list = array; new_list->used_size = array_size; return (ZnList) new_list; } /* ********************************************************************************** * * ZnListArray -- * Return a pointer to the array containing the list. * ********************************************************************************** */ void * ZnListArray(ZnList list) { _ZnList *cur_list = (_ZnList *) list; return (void *) cur_list->list; } /* ********************************************************************************** * * ZnListFree -- * Delete a list and free its memory. The entries * still in the list are lost but no further deallocation * is attempted. * ********************************************************************************** */ void ZnListFree(ZnList list) { _ZnList *cur_list = (_ZnList *) list; if (cur_list->list != NULL && cur_list->alloc_size != 0) { ZnFree(cur_list->list); } ZnFree(cur_list); } /* ********************************************************************************** * * ZnListSize -- * Return the current number of entries kept in list. * ********************************************************************************** */ unsigned int ZnListSize(ZnList list) { return ((_ZnList *)list)->used_size; } /* ********************************************************************************** * * ZnListAssertSize -- * Set the list length to size. * ********************************************************************************** */ void ZnListAssertSize(ZnList list, unsigned int size) { _ZnList *cur_list = (_ZnList *) list; if (cur_list->used_size < size) { GrowIfNeeded(cur_list, size - cur_list->used_size); } cur_list->used_size = size; } /* ********************************************************************************** * * ZnListCopy -- * Destructively copy 'from' into 'to' starting at the first * position. It is the same as saying ZnListEmpty and then * ZnListAppend. * ********************************************************************************** */ void ZnListCopy(ZnList to, ZnList from) { _ZnList *to_list = (_ZnList *) to; _ZnList *from_list = (_ZnList *) from; if (from_list->elem_size != to_list->elem_size) { return; } to_list->used_size = 0; GrowIfNeeded(to_list, from_list->used_size); memcpy(to_list->list, from_list->list, from_list->used_size*from_list->elem_size); to_list->used_size = from_list->used_size; } /* ********************************************************************************** * * ZnListAppend -- * Append 'from' at the end of 'to' which is enlarged as needed. * ********************************************************************************** */ void ZnListAppend(ZnList to, ZnList from) { _ZnList *to_list = (_ZnList *) to; _ZnList *from_list = (_ZnList *) from; if (from_list->elem_size != to_list->elem_size) { return; } GrowIfNeeded(to_list, from_list->used_size); memcpy(to_list->list+(to_list->used_size*to_list->elem_size), from_list->list, from_list->used_size*from_list->elem_size); to_list->used_size += from_list->used_size; } /* ********************************************************************************** * * ZnListAdd -- * Add a new entry 'value' in the list before * 'index'. 'index' can be the position of a * previous entry or the special values ZnListHead, * ZnListTail. The entries have positions * starting at 0. * ********************************************************************************** */ void ZnListAdd(ZnList list, void *value, unsigned int index) { _ZnList *cur_list = (_ZnList *) list; int i; GrowIfNeeded(cur_list, 1); if (index < cur_list->used_size) { for (i = cur_list->used_size-1; i >= (int) index; i--) { memcpy(cur_list->list+((i+1)*cur_list->elem_size), cur_list->list+(i*cur_list->elem_size), cur_list->elem_size); } } else if (index > cur_list->used_size) { index = cur_list->used_size; } memcpy(cur_list->list+(index*cur_list->elem_size), (char *) value, cur_list->elem_size); (cur_list->used_size)++; } /* ********************************************************************************** * * ZnListAt -- * Return the entry at 'index'. Indices start at 0. * Indices out of the current range are constrained * to fit in the range. * ********************************************************************************** */ void * ZnListAt(ZnList list, unsigned int index) { if (!((_ZnList *) list)->used_size) { return NULL; } if (index >= ((_ZnList *) list)->used_size) { index = ((_ZnList *) list)->used_size - 1; } return (void *) (((_ZnList *) list)->list+(index*((_ZnList *) list)->elem_size)); } /* ********************************************************************************** * * ZnListAtPut -- * Set the entry at 'index' to 'value'. * Indices start at 0. Indices out of the current * range are constrained to fit in the range. * ********************************************************************************** */ void ZnListAtPut(ZnList list, void *value, unsigned int index) { if (!((_ZnList *) list)->used_size) { return; } if (index >= ((_ZnList *) list)->used_size) { index = ((_ZnList *) list)->used_size - 1; } memcpy(((_ZnList *) list)->list+(index*((_ZnList *) list)->elem_size), (char *) value, ((_ZnList *) list)->elem_size); } /* ********************************************************************************** * * ZnListDelete -- * Suppress the entry matching value, searching from position * 'index'. If value is NULL suppress entry at index. * ********************************************************************************** */ void ZnListDelete(ZnList list, unsigned int index) { _ZnList *cur_list = (_ZnList *) list; unsigned int i; if (!((_ZnList *) list)->used_size) { return; } if (index >= ((_ZnList *) list)->used_size) { index = ((_ZnList *) list)->used_size - 1; } for (i = index; i < cur_list->used_size-1; i++) { memcpy(cur_list->list+(i*cur_list->elem_size), cur_list->list+((i+1)*cur_list->elem_size), cur_list->elem_size); } (cur_list->used_size)--; } /* ********************************************************************************** * * ZnListTruncate -- * Suppress the entries from position 'index' inclusive to the end. * ********************************************************************************** */ void ZnListTruncate(ZnList list, unsigned int index) { _ZnList *cur_list = (_ZnList *) list; if (index >= ((_ZnList *) list)->used_size) { return; } cur_list->used_size = index; }