bug-gnulib
[Top][All Lists]
Advanced

[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);
  






reply via email to

[Prev in Thread] Current Thread [Next in Thread]