Re: [pdf-devel] Re: List unit test failing

[jemarch]

   > If someone knows how "allow_duplicates" is supposed to work, help me :-)

   This parameter seems not used in the gnulib array list implementation 
   (gl_array_list.[c|h]).

   jemarch, is this a bug in gnulib? or are we misunderstanding something?

Hm. From the gl_list.h file:

   ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
   the list. The implementation may verify this at runtime.  */

It says `may' and not `should'. 

It seems that the `allow_duplicates' flag is used in some
implementations (such as gl_anytreehash_list1.h) where an efficiency
trick can be used to improve speedness in insertions.

So it seems Bruno didnt think that the control of duplicate values
should be done in the gl_list implementation level but in an upper
level.

I would do exactly that: to extend the definition of pdf-list to have
a boolean `allow_duplicates' and control value duplication in the
pdf-list level.

The following patch implement that support (and the current list tests
run fine). Note that the patch includes changes in the API of
pdf_list_add_first(), pdf_list_add_last(), pdf_list_add_at() and
pdf_list_set_at(). 

Aleks, Gerel, do you think this is a good solution?

Index: doc/gnupdf.texi
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/doc/gnupdf.texi,v
retrieving revision 1.50
diff -r1.50 gnupdf.texi
1742a1743,1745
> @item PDF_BADDATA
> The list do not allow duplicated values and already contain
> @var{element}.
1754c1757
< @deftypefun pdf_list_node_t pdf_list_add_first (pdf_list_t @var{list}, const 
void* @var{element})
---
> @deftypefun pdf_status_t pdf_list_add_first (pdf_list_t @var{list}, const 
> void* @var{element}, pdf_list_node_t address@hidden)
1756c1759,1760
< Add an element as the first element of the list.
---
> Add an element as the first element of the list. If @var{node} is not
> NULL then a reference to the newly created node is copied to it.
1764a1769,1770
> @item node
> If non NULL, a list node variable used to contain the added element.
1767c1773,1780
< The node containing the added elemetn.
---
> A PDF status value:
> @table @code
> @item PDF_OK
> The element was inserted successfully.
> @item PDF_EBADDATA
> The list do not allow duplicated values and already contain
> @var{element}.
> @end table
1775c1788
< @deftypefun pdf_list_node_t pdf_list_add_last (pdf_list_t @var{list}, const 
void* @var{element})
---
> @deftypefun pdf_status_t pdf_list_add_last (pdf_list_t @var{list}, const 
> void* @var{element}, pdf_list_node_t address@hidden)
1777c1790,1791
< Add an element as the last element of the list.
---
> Add an element as the last element of the list. If @var{node} is not
> NULL then a reference to the newly created node is copied to it.
1785a1800,1801
> @item node
> If non NULL, a list node variable used to contain the added element.
1788c1804,1811
< The node containing the given @var{element}.
---
> A PDF status value:
> @table @code
> @item PDF_OK
> The element was inserted successfully.
> @item PDF_EBADDATA
> The list do not allow duplicated values and already contain
> @var{element}.
> @end table
1819a1843,1845
> @item PDF_BADDATA
> The list do not allow duplicated values and already contain
> @var{element}.
Index: src/base/pdf-list.h
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/src/base/pdf-list.h,v
retrieving revision 1.7
diff -r1.7 pdf-list.h
1c1
< /* -*- mode: C -*- Time-stamp: "2008-04-13 12:09:09 gerel"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:33:56 jemarch"
47a48
>   pdf_bool_t allow_duplicates;
115,116c116,117
< pdf_list_node_t pdf_list_add_first (pdf_list_t list, const void* element);
< pdf_list_node_t pdf_list_add_last (pdf_list_t list, const void* element);
---
> pdf_status_t pdf_list_add_first (pdf_list_t list, const void* element, 
> pdf_list_node_t *node);
> pdf_status_t pdf_list_add_last (pdf_list_t list, const void* element, 
> pdf_list_node_t *node);
193a195,196
>       list->allow_duplicates = allow_duplicates;
> 
528,529c531,532
<   if ((position > 0 && position < pdf_list_size (list)) ||
<       (position == 0))
---
>   if (list.allow_duplicates ||
>       (gl_list_search ((gl_list_t)list.gl_list, element) == NULL))
531c534,535
<       if (node != NULL)
---
>       if (((position > 0 && position < pdf_list_size (list)) ||
>            (position == 0)))
533,534c537,545
<           node->gl_node = gl_list_set_at ((gl_list_t)list.gl_list, position,
<                                           element);
---
>           if (node != NULL)
>             {
>               node->gl_node = gl_list_set_at ((gl_list_t)list.gl_list, 
> position,
>                                               element);
>             }
>           else
>             {
>               gl_list_set_at ((gl_list_t)list.gl_list, position, element);
>             }
538,539c549,550
<           gl_list_set_at ((gl_list_t)list.gl_list, position, element);
<         }
---
>           st = PDF_EINVRANGE;
>         }  
542,544c553,556
<     {
<       st = PDF_EINVRANGE;
<     }  
---
>     {      
>       /* Duplicated list values are not allowed */
>       st = PDF_EBADDATA;
>     }
553,554c565,568
< EXTERN_INLINE pdf_list_node_t
< pdf_list_add_first (pdf_list_t list, const void* element)
---
> EXTERN_INLINE pdf_status_t
> pdf_list_add_first (pdf_list_t list,
>                     const void* element,
>                     pdf_list_node_t *node)
556c570,571
<   pdf_list_node_t node;
---
>   pdf_status_t st;
>   gl_list_node_t gl_node;
558c573,587
<   node.gl_node = gl_list_add_first ((gl_list_t)list.gl_list, element);
---
>   st = PDF_OK;
>   if (list.allow_duplicates ||
>       (gl_list_search ((gl_list_t)list.gl_list, element) == NULL))
>     {
>       gl_node = gl_list_add_first ((gl_list_t)list.gl_list, element);
>       if (node != NULL)
>         {
>           node->gl_node = gl_node;
>         }
>     }
>   else
>     {
>       /* Duplicated list elements are not allowed */
>       st = PDF_EBADDATA;
>     }
560c589
<   return (node);
---
>   return (st);
564,565c593,596
< EXTERN_INLINE pdf_list_node_t
< pdf_list_add_last (pdf_list_t list, const void* element)
---
> EXTERN_INLINE pdf_status_t
> pdf_list_add_last (pdf_list_t list,
>                    const void* element,
>                    pdf_list_node_t *node)
567c598,599
<   pdf_list_node_t node;
---
>   pdf_status_t st;
>   gl_list_node_t gl_node;
569c601,615
<   node.gl_node = gl_list_add_last ((gl_list_t)list.gl_list, element);
---
>   st = PDF_OK;
>   if (list.allow_duplicates ||
>       (gl_list_search ((gl_list_t)list.gl_list, element) == NULL))
>     {
>       gl_node = gl_list_add_last ((gl_list_t)list.gl_list, element);
>       if (node != NULL)
>         {
>           node->gl_node = gl_node;
>         }
>     }
>   else
>     {
>       /* Duplicated list elements are not allowed */
>       st = PDF_EBADDATA;
>     }
571c617
<   return (node);
---
>   return (st);
585,586c631,632
<   if ((position > 0 && position < pdf_list_size (list)) ||
<       (position == 0))
---
>   if (list.allow_duplicates ||
>       (gl_list_search ((gl_list_t)list.gl_list, element) == NULL))
588c634,635
<       if (node != NULL)
---
>       if ((position > 0 && position < pdf_list_size (list)) ||
>           (position == 0))
590,591c637,645
<           node->gl_node = gl_list_add_at ((gl_list_t)list.gl_list,
<                                           position, element);
---
>           if (node != NULL)
>             {
>               node->gl_node = gl_list_add_at ((gl_list_t)list.gl_list,
>                                               position, element);
>             }
>           else
>             {
>               gl_list_add_at ((gl_list_t)list.gl_list, position, element);
>             }
595c649
<           gl_list_add_at ((gl_list_t)list.gl_list, position, element);
---
>           st = PDF_EINVRANGE;
600c654,655
<       st = PDF_EINVRANGE;
---
>       /* Duplicated list values are not allowed */
>       st = PDF_EBADDATA;
Index: src/base/pdf-stm.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/src/base/pdf-stm.c,v
retrieving revision 1.7
diff -r1.7 pdf-stm.c
1c1
< /* -*- mode: C -*- Time-stamp: "2008-03-13 17:05:59 gerel"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:31:35 jemarch"
713c713,714
<                           (const void *) filter);
---
>                            (const void *) filter,
>                            NULL);
719c720,721
<                           (const void *) filter);
---
>                            (const void *) filter,
>                            NULL);
Index: src/base/pdf-text-filter.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/src/base/pdf-text-filter.c,v
retrieving revision 1.2
diff -r1.2 pdf-text-filter.c
123c123
<       pdf_list_add_last(new_wb_list, &new_word);
---
>       pdf_list_add_last(new_wb_list, &new_word, NULL);
Index: src/base/pdf-text.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/src/base/pdf-text.c,v
retrieving revision 1.7
diff -r1.7 pdf-text.c
1745c1745
<           pdf_list_add_last(word_boundaries, p_word);
---
>           pdf_list_add_last(word_boundaries, p_word, NULL);
Index: torture/unit/base/list/pdf-list-add-first.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-add-first.c,v
retrieving revision 1.2
diff -r1.2 pdf-list-add-first.c
1c1
< /* -*- mode: C -*- Time-stamp: "2008-03-17 22:56:14 gerel"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:38:01 jemarch"
52,53c52,53
<   pdf_list_add_first (list, &elem);
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
>   pdf_list_add_first (list, &elem, NULL);
56c56
<   pdf_list_add_first (list, &elem2);
---
>   pdf_list_add_first (list, &elem2, NULL);
78,79c78,79
<   pdf_list_add_first (list, &elem);
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
>   pdf_list_add_first (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-add-last.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-add-last.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-add-last.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:22:42 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:38:26 jemarch"
49c49
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
52c52
<   pdf_list_add_last (list, &elem2);
---
>   pdf_list_add_last (list, &elem2, NULL);
Index: torture/unit/base/list/pdf-list-get-at.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-get-at.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-get-at.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:25:13 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:38:52 jemarch"
48c48
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
75c75
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
102c102
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-indexof-from-to.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-indexof-from-to.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-indexof-from-to.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:22:24 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:40:22 jemarch"
51c51
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
81c81
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
114c114
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
143c143
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-indexof-from.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-indexof-from.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-indexof-from.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:25:04 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:39:49 jemarch"
49c49
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
79c79
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
109c109
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-indexof.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-indexof.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-indexof.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:24:53 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:39:14 jemarch"
50c50
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-iterator-from-to.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-iterator-from-to.c,v
retrieving revision 1.2
diff -r1.2 pdf-list-iterator-from-to.c
1c1
< /* -*- mode: C -*- Time-stamp: "2008-03-18 15:19:40 gerel"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:40:53 jemarch"
49,50c49,50
<   pdf_list_add_last (list, &elem);
<   pdf_list_add_last (list, &elem2);
---
>   pdf_list_add_last (list, &elem, NULL);
>   pdf_list_add_last (list, &elem2, NULL);
79,80c79,80
<   pdf_list_add_last (list, &elem);
<   pdf_list_add_last (list, &elem2);
---
>   pdf_list_add_last (list, &elem, NULL);
>   pdf_list_add_last (list, &elem2, NULL);
118c118
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-iterator-next.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-iterator-next.c,v
retrieving revision 1.2
diff -r1.2 pdf-list-iterator-next.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/04/06 22:53:28 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:41:07 jemarch"
49c49
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-next-node.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-next-node.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-next-node.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:25:24 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:42:28 jemarch"
50,51c50,51
<   node = pdf_list_add_last (list, &elem);
<   pdf_list_add_last (list, &elem2);
---
>   pdf_list_add_last (list, &elem, &node);
>   pdf_list_add_last (list, &elem2, NULL);
81c81
<   node = pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, &node);
110c110
<   node = pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, &node);
Index: torture/unit/base/list/pdf-list-node-value.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-node-value.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-node-value.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:23:53 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:42:46 jemarch"
48c48
<   node = pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, &node);
Index: torture/unit/base/list/pdf-list-previous-node.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-previous-node.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-previous-node.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:24:33 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:43:25 jemarch"
50,51c50,51
<   pdf_list_add_last (list, &elem);
<   node = pdf_list_add_last (list, &elem2);
---
>   pdf_list_add_last (list, &elem, NULL);
>   pdf_list_add_last (list, &elem2, &node);
81c81
<   node = pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, &node);
110c110
<   node = pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, &node);
Index: torture/unit/base/list/pdf-list-remove-at.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-remove-at.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-remove-at.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:23:12 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:43:43 jemarch"
48c48
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
74c74
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-remove-node.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-remove-node.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-remove-node.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:22:34 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:44:20 jemarch"
48c48
<   node = pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, &node);
Index: torture/unit/base/list/pdf-list-remove.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-remove.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-remove.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:34:45 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:43:59 jemarch"
51c51
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
78c78
<   pdf_list_add_first (list, &elem);
---
>   pdf_list_add_first (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-search-from-to.c
===================================================================
RCS file: 
/cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-search-from-to.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-search-from-to.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:34:57 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:45:55 jemarch"
52c52
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
79c79
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
107c107
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
133c133
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-search-from.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-search-from.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-search-from.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:35:12 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:45:29 jemarch"
53c53
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
80c80
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
108c108
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
134c134
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-search.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-search.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-search.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:35:26 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:44:59 jemarch"
52c52
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
80c80
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
109c109
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
Index: torture/unit/base/list/pdf-list-set-at.c
===================================================================
RCS file: /cvsroot/pdf/libgnupdf/torture/unit/base/list/pdf-list-set-at.c,v
retrieving revision 1.1
diff -r1.1 pdf-list-set-at.c
1c1
< /* -*- mode: C -*- Time-stamp: "08/03/17 14:24:24 jemarch"
---
> /* -*- mode: C -*- Time-stamp: "08/04/21 19:47:35 jemarch"
50c50
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);
79c79
<   pdf_list_add_last (list, &elem);
---
>   pdf_list_add_last (list, &elem, NULL);