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.

1 files changed, 629 insertions, 0 deletions

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 <stddef.h>
+#include <memory.h>
+#include <stdlib.h>
+
+
+/*
+ **********************************************************************************
+ *
+ * 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;
+  }
+}