[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Idea for linked-list
From: |
Bruno Haible |
Subject: |
Re: Idea for linked-list |
Date: |
Wed, 14 Mar 2007 03:07:27 +0100 |
User-agent: |
KMail/1.5.4 |
Simon Josefsson wrote:
> One important feature of our current implementation is that I can register
> my custom "free" function, which can do more things than just memory
> deallocation:
>
> ...
>
> This function is invoked for each list item that for any reason is
> being removed from the list. Is it possible to do this with the
> linked-list module?
Good idea. It applies not only the the linked-list module, but to all *-list
and *-oset modules.
> By reading gl_anylinked_list2.h it appear as
> de-allocating a list item is pretty hard coded, and several function
> do 'free' on it.
The list node is free()d, not the value in it. The value in it is an
opaque pointer of type 'const void *', which means that the container
implementation doesn't perform any operations on it (except == in some
cases).
> I imagine some function to register a "free"-handler, and it would be
> used by all other functions that want to de-allocate a particular
> node.
It doesn't need a separate function, since noone wants to change the "free"
handler once the list has been created. It's therefore merely a constructor
argument.
I'll apply this patch first:
2007-03-13 Bruno Haible <address@hidden>
* lib/gl_oset.h (gl_setelement_dispose_fn): New type.
(gl_oset_create_empty): Add dispose_fn argument.
(struct gl_oset_implementation): Add dispose_fn argument to
'create_empty' method.
(struct gl_oset_impl_base): Add dispose_fn field.
* lib/gl_oset.c (gl_oset_create_empty): Add dispose_fn argument.
* lib/gl_array_oset.c (gl_array_create_empty): Add dispose_fn argument.
(gl_array_remove_at, gl_array_free): Call dispose_fn on the dropped
values.
* lib/gl_anytree_oset.h (gl_tree_create_empty): Add dispose_fn argument.
(gl_tree_oset_free): Call dispose_fn on the dropped values.
* lib/gl_avltree_oset.c (gl_tree_remove_node): Call dispose_fn on the
dropped value.
* lib/gl_rbtree_oset.c (gl_tree_remove_node): Call dispose_fn on the
dropped value.
* tests/test-array_oset.c (main): Update.
* tests/test-avltree_oset.c (main): Update.
* tests/test-rbtree_oset.c (main): Update.
* lib/gl_anytreehash_list1.h (add_to_bucket): Update.
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_anytree_oset.h
gnulib-work/lib/gl_anytree_oset.h
*** gnulib-cvs/lib/gl_anytree_oset.h 2006-11-13 15:30:13.000000000 +0100
--- gnulib-work/lib/gl_anytree_oset.h 2007-03-13 00:30:27.000000000 +0100
***************
*** 1,5 ****
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 30,41 ****
static gl_oset_t
gl_tree_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn)
{
struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
set->base.vtable = implementation;
set->base.compar_fn = compar_fn;
set->root = NULL;
set->count = 0;
--- 30,43 ----
static gl_oset_t
gl_tree_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn)
{
struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
set->base.vtable = implementation;
set->base.compar_fn = compar_fn;
+ set->base.dispose_fn = dispose_fn;
set->root = NULL;
set->count = 0;
***************
*** 216,221 ****
--- 218,225 ----
if (!stack_ptr->rightp)
break;
/* Free the current node. */
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (node->value);
free (node);
}
/* Descend on right branch. */
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_anytreehash_list1.h
gnulib-work/lib/gl_anytreehash_list1.h
*** gnulib-cvs/lib/gl_anytreehash_list1.h 2006-11-07 15:24:05.000000000
+0100
--- gnulib-work/lib/gl_anytreehash_list1.h 2007-03-13 00:16:31.000000000
+0100
***************
*** 1,5 ****
/* Sequential list data type implemented by a hash table with a binary tree.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Sequential list data type implemented by a hash table with a binary tree.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 152,158 ****
nodes =
gl_oset_create_empty (OSET_TREE_FLAVOR,
! compare_by_position);
gl_oset_add (nodes, node);
gl_oset_add (nodes, new_node);
--- 152,158 ----
nodes =
gl_oset_create_empty (OSET_TREE_FLAVOR,
! compare_by_position, NULL);
gl_oset_add (nodes, node);
gl_oset_add (nodes, new_node);
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_array_oset.c
gnulib-work/lib/gl_array_oset.c
*** gnulib-cvs/lib/gl_array_oset.c 2007-03-12 22:51:20.000000000 +0100
--- gnulib-work/lib/gl_array_oset.c 2007-03-13 00:29:48.000000000 +0100
***************
*** 43,54 ****
static gl_oset_t
gl_array_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn)
{
struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
set->base.vtable = implementation;
set->base.compar_fn = compar_fn;
set->elements = NULL;
set->count = 0;
set->allocated = 0;
--- 43,56 ----
static gl_oset_t
gl_array_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn)
{
struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
set->base.vtable = implementation;
set->base.compar_fn = compar_fn;
+ set->base.dispose_fn = dispose_fn;
set->elements = NULL;
set->count = 0;
set->allocated = 0;
***************
*** 204,209 ****
--- 206,213 ----
size_t i;
elements = set->elements;
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (elements[position]);
for (i = position + 1; i < count; i++)
elements[i - 1] = elements[i];
set->count = count - 1;
***************
*** 262,268 ****
gl_array_free (gl_oset_t set)
{
if (set->elements != NULL)
! free (set->elements);
free (set);
}
--- 266,288 ----
gl_array_free (gl_oset_t set)
{
if (set->elements != NULL)
! {
! if (set->base.dispose_fn != NULL)
! {
! size_t count = set->count;
!
! if (count > 0)
! {
! gl_setelement_dispose_fn dispose = set->base.dispose_fn;
! const void **elements = set->elements;
!
! do
! dispose (*elements++);
! while (--count > 0);
! }
! }
! free (set->elements);
! }
free (set);
}
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_avltree_oset.c
gnulib-work/lib/gl_avltree_oset.c
*** gnulib-cvs/lib/gl_avltree_oset.c 2006-11-06 14:03:10.000000000 +0100
--- gnulib-work/lib/gl_avltree_oset.c 2007-03-13 00:35:21.000000000 +0100
***************
*** 1,5 ****
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 519,524 ****
--- 519,526 ----
}
set->count--;
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (node->value);
free (node);
return true;
}
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_oset.c gnulib-work/lib/gl_oset.c
*** gnulib-cvs/lib/gl_oset.c 2006-10-04 19:28:15.000000000 +0200
--- gnulib-work/lib/gl_oset.c 2007-03-13 00:15:22.000000000 +0100
***************
*** 1,5 ****
/* Abstract ordered set data type.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Abstract ordered set data type.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 29,37 ****
gl_oset_t
gl_oset_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn)
{
! return implementation->create_empty (implementation, compar_fn);
}
size_t
--- 29,38 ----
gl_oset_t
gl_oset_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn)
{
! return implementation->create_empty (implementation, compar_fn, dispose_fn);
}
size_t
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_oset.h gnulib-work/lib/gl_oset.h
*** gnulib-cvs/lib/gl_oset.h 2006-11-07 14:53:52.000000000 +0100
--- gnulib-work/lib/gl_oset.h 2007-03-13 00:14:43.000000000 +0100
***************
*** 1,5 ****
/* Abstract ordered set data type.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Abstract ordered set data type.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 70,75 ****
--- 70,79 ----
NULL denotes pointer comparison. */
typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
+ /* Type of function used to dispose an element once it's removed from a set.
+ NULL denotes a no-op. */
+ typedef void (*gl_setelement_dispose_fn) (const void *elt);
+
/* Type of function used to compare an element with a threshold.
Return true if the element is greater or equal than the threshold. */
typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void
*threshold);
***************
*** 84,92 ****
/* Create an empty set.
IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
! COMPAR_FN is an element comparison function or NULL. */
extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t
implementation,
! gl_setelement_compar_fn compar_fn);
/* Return the current number of elements in an ordered set. */
extern size_t gl_oset_size (gl_oset_t set);
--- 88,98 ----
/* Create an empty set.
IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
! COMPAR_FN is an element comparison function or NULL.
! DISPOSE_FN is an element disposal function or NULL. */
extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t
implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn);
/* Return the current number of elements in an ordered set. */
extern size_t gl_oset_size (gl_oset_t set);
***************
*** 155,161 ****
{
/* gl_oset_t functions. */
gl_oset_t (*create_empty) (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn);
size_t (*size) (gl_oset_t set);
bool (*search) (gl_oset_t set, const void *elt);
bool (*search_atleast) (gl_oset_t set,
--- 161,168 ----
{
/* gl_oset_t functions. */
gl_oset_t (*create_empty) (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn);
size_t (*size) (gl_oset_t set);
bool (*search) (gl_oset_t set, const void *elt);
bool (*search_atleast) (gl_oset_t set,
***************
*** 174,179 ****
--- 181,187 ----
{
const struct gl_oset_implementation *vtable;
gl_setelement_compar_fn compar_fn;
+ gl_setelement_dispose_fn dispose_fn;
};
#if HAVE_INLINE
***************
*** 185,193 ****
# define gl_oset_create_empty gl_oset_create_empty_inline
static inline gl_oset_t
gl_oset_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn)
{
! return implementation->create_empty (implementation, compar_fn);
}
# define gl_oset_size gl_oset_size_inline
--- 193,202 ----
# define gl_oset_create_empty gl_oset_create_empty_inline
static inline gl_oset_t
gl_oset_create_empty (gl_oset_implementation_t implementation,
! gl_setelement_compar_fn compar_fn,
! gl_setelement_dispose_fn dispose_fn)
{
! return implementation->create_empty (implementation, compar_fn, dispose_fn);
}
# define gl_oset_size gl_oset_size_inline
diff -r -c3 --exclude=CVS gnulib-cvs/lib/gl_rbtree_oset.c
gnulib-work/lib/gl_rbtree_oset.c
*** gnulib-cvs/lib/gl_rbtree_oset.c 2006-11-06 14:03:10.000000000 +0100
--- gnulib-work/lib/gl_rbtree_oset.c 2007-03-13 00:35:21.000000000 +0100
***************
*** 1,5 ****
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
--- 1,5 ----
/* Ordered set data type implemented by a binary tree.
! Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <address@hidden>, 2006.
This program is free software; you can redistribute it and/or modify
***************
*** 749,754 ****
--- 749,756 ----
}
set->count--;
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (node->value);
free (node);
return true;
}
diff -r -c3 --exclude=CVS gnulib-cvs/tests/test-array_oset.c
gnulib-work/tests/test-array_oset.c
*** gnulib-cvs/tests/test-array_oset.c 2007-03-03 20:34:21.000000000 +0100
--- gnulib-work/tests/test-array_oset.c 2007-03-13 00:39:05.000000000 +0100
***************
*** 88,94 ****
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp);
/* Create set2. */
set2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, false);
--- 88,94 ----
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp, NULL);
/* Create set2. */
set2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, false);
diff -r -c3 --exclude=CVS gnulib-cvs/tests/test-avltree_oset.c
gnulib-work/tests/test-avltree_oset.c
*** gnulib-cvs/tests/test-avltree_oset.c 2007-03-03 20:34:21.000000000
+0100
--- gnulib-work/tests/test-avltree_oset.c 2007-03-13 00:39:19.000000000
+0100
***************
*** 86,95 ****
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp);
/* Create set2. */
! set2 = gl_oset_create_empty (GL_AVLTREE_OSET, (gl_setelement_compar_fn)
strcmp);
check_all (set1, set2);
--- 86,95 ----
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp, NULL);
/* Create set2. */
! set2 = gl_oset_create_empty (GL_AVLTREE_OSET, (gl_setelement_compar_fn)
strcmp, NULL);
check_all (set1, set2);
diff -r -c3 --exclude=CVS gnulib-cvs/tests/test-rbtree_oset.c
gnulib-work/tests/test-rbtree_oset.c
*** gnulib-cvs/tests/test-rbtree_oset.c 2007-03-03 20:34:21.000000000 +0100
--- gnulib-work/tests/test-rbtree_oset.c 2007-03-13 00:39:33.000000000
+0100
***************
*** 88,97 ****
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp);
/* Create set2. */
! set2 = gl_oset_create_empty (GL_RBTREE_OSET, (gl_setelement_compar_fn)
strcmp);
check_all (set1, set2);
--- 88,97 ----
unsigned int repeat;
/* Create set1. */
! set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn)
strcmp, NULL);
/* Create set2. */
! set2 = gl_oset_create_empty (GL_RBTREE_OSET, (gl_setelement_compar_fn)
strcmp, NULL);
check_all (set1, set2);