From c7934638eb9a6a006ccb85ad09dbcdfcac93f90f Mon Sep 17 00:00:00 2001 From: lecoanet Date: Mon, 29 Nov 1999 09:08:03 +0000 Subject: RadarListDelete ne prend plus de troisi�me param�tre contenant une valeur � rechercher. Il faut d�sormais fournir l'index de l'entr�e � d�truire. RadarListDetect est supprim�e. RadarListDo prend un param�tre de plus contenant une donn�e anonyme qui sera reservie � la fonction de test. Cette fonction re�oit donc un param�tre de plus ce qui permet d'effectuer un test plus utile. --- generic/List.c | 629 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ generic/List.h | 117 +++++++++++ 2 files changed, 746 insertions(+) create mode 100644 generic/List.c create mode 100644 generic/List.h (limited to 'generic') diff --git a/generic/List.c b/generic/List.c new file mode 100644 index 0000000..573d7b2 --- /dev/null +++ b/generic/List.c @@ -0,0 +1,629 @@ +/* + * List.c -- Implementation of list module. + * + * Authors : Patrick Lecoanet. + * Creation date : Tue Mar 15 17:18:17 1994 + * + * $Id$ + */ + +/* + * Copyright (c) 1993 - 1999 CENA, Patrick Lecoanet -- + * + * This code is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This code 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 + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this code; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + + +/* + ********************************************************************************** + * + * This modules exports the following functions: + * - RadarListNew + * - RadarListDuplicate + * - RadarListEmpty + * - RadarListFromArray + * - RadarListArray + * - RadarListFree + * - RadarListSize + * - RadarListAssertSize + * - RadarListAdd + * - RadarListAt + * - RadarListAtPut + * - RadarListDelete + * - RadarListTruncate + * - RadarListDetect + * - RadarListDo + * + * To appear soon: + * - RadarListCollect + * - RadarListReject + * + * And the following variables: + * + ********************************************************************************** + */ + +/* + ********************************************************************************** + * + * Included files + * + ********************************************************************************** + */ + +#include "Types.h" +#include "List.h" +#include "config.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 + +#define MAX(a, b) ((a) > (b) ? (a) : (b)) +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + + +/* + ********************************************************************************** + * + * New types + * + ********************************************************************************** + */ + +typedef struct { + char *list; + long elem_size; + long alloc_size; + long used_size; +} _RadarList; + + +/* + ********************************************************************************** + * + * GrowIfNeeded -- + * Enlarge a list so that it has min_size available. Take care of + * static storage. + * + ********************************************************************************** + */ + +static void +GrowIfNeeded(_RadarList *list, + 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 = (char *) RadarMalloc(list->alloc_size*list->elem_size); + } + else { + /* Case of a list made by RadarListFromArray. 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 = (char *) RadarMalloc(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 = (char *) RadarRealloc(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); +} + + +/* + ********************************************************************************** + * + * RadarListNew -- + * Return a new empty list 'initial_size' large. + * + ********************************************************************************** + */ + +RadarList +RadarListNew(int initial_size, + int element_size) +{ + _RadarList *new_list; + + if (initial_size < 0) { + initial_size = 0; + } + + if (element_size <= 0) { + element_size = 1; + } + + new_list = (_RadarList *) RadarMalloc(sizeof(_RadarList)); + + new_list->alloc_size = initial_size; + new_list->used_size = 0; + new_list->elem_size = element_size; + + if (initial_size) { + long size = new_list->alloc_size*new_list->elem_size; + + new_list->list = RadarMalloc(size); + memset(new_list->list, 0, size); + } + else { + new_list->list = NULL; + } + + return (RadarList) new_list; +} + + +/* + ********************************************************************************** + * + * RadarListDuplicate -- + * Return a copy of the list given as parameter. + * + ********************************************************************************** + */ + +RadarList +RadarListDuplicate(RadarList list) +{ + _RadarList *cur_list = (_RadarList *) list; + _RadarList *new_list; + + new_list = (_RadarList *) RadarMalloc(sizeof(_RadarList)); + + 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) { + long used_size = new_list->used_size*new_list->elem_size; + long size = new_list->alloc_size*new_list->elem_size; + + new_list->list = RadarMalloc(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 (RadarList) new_list; +} + + +/* + ********************************************************************************** + * + * RadarListEmpty -- + * Clear out a list, kkeping its allocated size. + * + ********************************************************************************** + */ + +void +RadarListEmpty(RadarList list) +{ + _RadarList *cur_list = (_RadarList *) list; + + cur_list->used_size = 0; +} + + +/* + ********************************************************************************** + * + * RadarListFromArray -- + * Return a list filled from the given array. + * + ********************************************************************************** + */ + +RadarList +RadarListFromArray(void *array, + int array_size, + int element_size) +{ + _RadarList *new_list; + + new_list = (_RadarList *) RadarListNew(0, element_size); + new_list->list = array; + new_list->used_size = array_size; + return (RadarList) new_list; +} + + +/* + ********************************************************************************** + * + * RadarListArray -- + * Return a pointer to the array containing the list. + * + ********************************************************************************** + */ + +void * +RadarListArray(RadarList list) +{ + _RadarList *cur_list = (_RadarList *) list; + + return (void *) cur_list->list; +} + + +/* + ********************************************************************************** + * + * RadarListFree -- + * Delete a list and free its memory. The entries + * still in the list are lost but no further deallocation + * is attempted. + * + ********************************************************************************** + */ + +void +RadarListFree(RadarList list) +{ + _RadarList *cur_list = (_RadarList *) list; + + if (cur_list->list != NULL && cur_list->alloc_size != 0) { + RadarFree(cur_list->list); + } + + RadarFree(cur_list); +} + + +/* + ********************************************************************************** + * + * RadarListSize -- + * Return the current number of entries kept in list. + * + ********************************************************************************** + */ + +int +RadarListSize(RadarList list) +{ + return ((_RadarList *)list)->used_size; +} + + +/* + ********************************************************************************** + * + * RadarListAssertSize -- + * Set the list length to size. + * + ********************************************************************************** + */ + +void +RadarListAssertSize(RadarList list, + int size) +{ + _RadarList *cur_list = (_RadarList *) list; + + if (cur_list->used_size < size) { + GrowIfNeeded(cur_list, size - cur_list->used_size); + } + cur_list->used_size = size; +} + + +/* + ********************************************************************************** + * + * RadarListCopy -- + * Destructively copy 'from' into 'to' starting at the first + * position. It is the same as saying RadarListEmpty and then + * RadarListAppend. + * + ********************************************************************************** + */ + +void +RadarListCopy(RadarList to, + RadarList from) +{ + _RadarList *to_list = (_RadarList *) to; + _RadarList *from_list = (_RadarList *) 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; +} + + +/* + ********************************************************************************** + * + * RadarListAppend -- + * Append 'from' at the end of 'to' which is enlarged as needed. + * + ********************************************************************************** + */ + +void +RadarListAppend(RadarList to, + RadarList from) +{ + _RadarList *to_list = (_RadarList *) to; + _RadarList *from_list = (_RadarList *) 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; +} + + +/* + ********************************************************************************** + * + * RadarListAdd -- + * Add a new entry 'value' in the list before + * 'index'. 'index' can be the position of a + * previous entry or the special values RadarListHead, + * RadarListTail. The entries have positions + * starting at 0. + * + ********************************************************************************** + */ + +void +RadarListAdd(RadarList list, + void *value, + int index) +{ + _RadarList *cur_list = (_RadarList *) list; + int i; + + GrowIfNeeded(cur_list, 1); + + if (index < 0) { + index = 0; + } + + if (index < cur_list->used_size) { + for (i = cur_list->used_size-1; i >= 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)++; +} + + +/* + ********************************************************************************** + * + * RadarListAt -- + * Return the entry at 'index'. Indices start at 0. + * Indices out of the current range are constrained + * to fit in the range. + * + ********************************************************************************** + */ + +void * +RadarListAt(RadarList list, + int index) +{ + if (!((_RadarList *) list)->used_size) { + return NULL; + } + if (index >= ((_RadarList *) list)->used_size) { + index = ((_RadarList *) list)->used_size - 1; + } + if (index < 0) { + index = 0; + } + + return (void *) ((_RadarList *) list)->list+(index*((_RadarList *) list)->elem_size); +} + + +/* + ********************************************************************************** + * + * RadarListAtPut -- + * 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 +RadarListAtPut(RadarList list, + void *value, + int index) +{ + if (!((_RadarList *) list)->used_size) { + return; + } + if (index >= ((_RadarList *) list)->used_size) { + index = ((_RadarList *) list)->used_size - 1; + } + if (index < 0) { + index = 0; + } + + memcpy(((_RadarList *) list)->list+(index*((_RadarList *) list)->elem_size), + (char *) value, + ((_RadarList *) list)->elem_size); +} + + +/* + ********************************************************************************** + * + * RadarListDelete -- + * Suppress the entry matching value, searching from position + * 'index'. If value is NULL suppress entry at index. + * + ********************************************************************************** + */ + +void +RadarListDelete(RadarList list, + int index) +{ + _RadarList *cur_list = (_RadarList *) list; + int i; + + if (!((_RadarList *) list)->used_size) { + return; + } + if (index >= ((_RadarList *) list)->used_size) { + index = ((_RadarList *) list)->used_size - 1; + } + if (index < 0) { + index = 0; + } + + 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)--; +} + +/* + ********************************************************************************** + * + * RadarListTruncate -- + * Suppress the entries from position 'index' inclusive to the end. + * + ********************************************************************************** + */ + +void +RadarListTruncate(RadarList list, + int index) +{ + _RadarList *cur_list = (_RadarList *) list; + + if (!((_RadarList *) list)->used_size) { + return; + } + if (index >= ((_RadarList *) list)->used_size) { + return; + } + if (index < 0) { + index = 0; + } + + cur_list->used_size = index; +} + + +/* + ********************************************************************************** + * + * RadarListDo -- + * Apply the function 'to_do' to each entry in the list. + * Stop either at end of list or if 'to_do' returns a + * non nul result. 'to_do' is a function with two + * parameters. The first is bound in turn to each value of + * the list, the second is the data passed to RadarListDo. + * If the scan stops at the end of the list, the function + * returns -1, else it returns the index at which it has + * stopped. + * + ********************************************************************************** + */ + +int +RadarListDo(RadarList list, + void *data, + int (*to_do)(void *value, void *data)) +{ + _RadarList *cur_list = (_RadarList *) list; + int i; + + for (i = 0; + i < cur_list->used_size && + !(*to_do)((void *) (cur_list->list + (i * cur_list->elem_size)), data); + i++); + if (i == cur_list->used_size) { + return -1; + } + else { + return i; + } +} diff --git a/generic/List.h b/generic/List.h new file mode 100644 index 0000000..46ee00e --- /dev/null +++ b/generic/List.h @@ -0,0 +1,117 @@ +/* + * List.h -- Header of list module. + * + * Authors : Patrick Lecoanet. + * Creation date : Tue Mar 15 17:24:51 1994 + * + * $Id$ + */ + +/* + * Copyright (c) 1993 - 1999 CENA, Patrick Lecoanet -- + * + * This code is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This code 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 + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this code; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + + +#ifndef _List_h +#define _List_h + + +#ifdef __CPLUSPLUS__ +extern "C" { +#endif + + +/* + ********************************************************************************** + * + * Included files + * + ********************************************************************************** + */ + + +/* + ********************************************************************************** + * + * Constants + * + ********************************************************************************** + */ + +#define RadarListHead 0 +#define RadarListTail (~(1 << ((8*sizeof(int)) - 1))) + + +/* + ********************************************************************************** + * + * New types + * + ********************************************************************************** + */ + +typedef void *RadarList; + + +/* + ********************************************************************************** + * + * Prototypes + * + ********************************************************************************** + */ + +RadarList RadarListNew(int /* initial_size */, + int /* element_size */); +RadarList RadarListDuplicate(RadarList /* list */); +void RadarListEmpty(RadarList /* list */); +RadarList RadarListFromArray(void */* array */, + int /* array_size */, + int /* element_size */); +void *RadarListArray(RadarList /* list */); +void RadarListFree(RadarList /* list */); +int RadarListSize(RadarList /* list */); +void RadarListAssertSize(RadarList /* list */, + int /* size */); +void RadarListCopy(RadarList /* to */, + RadarList /* from */); +void RadarListAppend(RadarList /* to */, + RadarList /* from */); +void RadarListAdd(RadarList /* list */, + void */* value */, + int /* index */); +void *RadarListAt(RadarList /* list */, + int /* index */); +void RadarListAtPut(RadarList /* list */, + void */* value */, + int /* index */); +void RadarListDelete(RadarList /* list */, + int /* index */); +void RadarListTruncate(RadarList /* list */, + int /* index */); +int RadarListDo(RadarList /* list */, + void *data, + int (*/* to_do */)(void */* value */, + void */*data*/)); + + +#ifdef __CPLUSPLUS__ +} +#endif + +#endif /* _List_h */ -- cgit v1.1