[PATCH] *-map, *-omap: Allow passing NULL to search

[PATCH] *-map, *-omap: Allow passing NULL to search

[Colin Watson]

It's sometimes convenient to have a map whose values may be NULL, but in
that case it's a little awkward to determine whether a key exists in the
map: gl_map_get returns NULL for both "key not found" and "value is
NULL", so one needs a local variable just for the purpose of passing its
address to gl_map_search.

Instead, allow the return pointers to be NULL, so that one can use
gl_map_search (map, NULL, NULL) to check existence.

* lib/gl_anytree_omap.h (gl_tree_search): Only set *valuep if valuep is
non-NULL.
* lib/gl_array_map.c (gl_array_search): Likewise.
* lib/gl_array_omap.c (gl_array_search): Likewise.
* lib/gl_hash_map.c (gl_hash_search): Likewise.
* lib/gl_linkedhash_map.c (gl_linkedhash_search): Likewise.
* lib/gl_map.h (gl_map_search): Describe new behaviour.
* lib/gl_omap.h (gl_omap_search): Likewise.

* lib/gl_anytree_omap.h (gl_tree_search_atleast): Only set *keyp or
*valuep if keyp or valuep respectively is non-NULL.
* lib/gl_array_omap.c (gl_array_search_atleast): Likewise.
* lib/gl_omap.h (gl_omap_search_atleast): Likewise.
---
 lib/gl_anytree_omap.h   | 9 ++++++---
 lib/gl_array_map.c      | 3 ++-
 lib/gl_array_omap.c     | 9 ++++++---
 lib/gl_hash_map.c       | 3 ++-
 lib/gl_linkedhash_map.c | 3 ++-
 lib/gl_map.h            | 4 ++--
 lib/gl_omap.h           | 9 +++++----
 7 files changed, 25 insertions(+), 15 deletions(-)

diff --git a/lib/gl_anytree_omap.h b/lib/gl_anytree_omap.h
index d2bd88eb6..a8c6f129e 100644
--- a/lib/gl_anytree_omap.h
+++ b/lib/gl_anytree_omap.h
@@ -75,7 +75,8 @@ gl_tree_search (gl_omap_t map, const void *key, const void **valuep)
       else /* cmp == 0 */
         {
           /* We have a key equal to KEY.  */
-          *valuep = node->value;
+          if (valuep)
+            *valuep = node->value;
           return true;
         }
     }
@@ -110,8 +111,10 @@ gl_tree_search_atleast (gl_omap_t map,
                   node = node->left;
                 }
             }
-          *keyp = found->key;
-          *valuep = found->value;
+          if (keyp)
+            *keyp = found->key;
+          if (valuep)
+            *valuep = found->value;
           return true;
         }
     }
diff --git a/lib/gl_array_map.c b/lib/gl_array_map.c
index 33dc719da..2c5770054 100644
--- a/lib/gl_array_map.c
+++ b/lib/gl_array_map.c
@@ -112,7 +112,8 @@ gl_array_search (gl_map_t map, const void *key, const void **valuep)
   size_t index = gl_array_indexof (map, key);
   if (index != (size_t)(-1))
     {
-      *valuep = map->pairs[index].value;
+      if (valuep)
+        *valuep = map->pairs[index].value;
       return true;
     }
   else
diff --git a/lib/gl_array_omap.c b/lib/gl_array_omap.c
index 3d3aff613..11b660e8d 100644
--- a/lib/gl_array_omap.c
+++ b/lib/gl_array_omap.c
@@ -115,7 +115,8 @@ gl_array_search (gl_omap_t map, const void *key, const void **valuep)
   size_t index = gl_array_indexof (map, key);
   if (index != (size_t)(-1))
     {
-      *valuep = map->pairs[index].value;
+      if (valuep)
+        *valuep = map->pairs[index].value;
       return true;
     }
   else
@@ -163,8 +164,10 @@ gl_array_search_atleast (gl_omap_t map,
                   else
                     high = mid2;
                 }
-              *keyp = map->pairs[low].key;
-              *valuep = map->pairs[low].value;
+              if (keyp)
+                *keyp = map->pairs[low].key;
+              if (valuep)
+                *valuep = map->pairs[low].value;
               return true;
             }
         }
diff --git a/lib/gl_hash_map.c b/lib/gl_hash_map.c
index 534b472fa..2f0b5bb8b 100644
--- a/lib/gl_hash_map.c
+++ b/lib/gl_hash_map.c
@@ -119,7 +119,8 @@ gl_hash_search (gl_map_t map, const void *key, const void **valuep)
             ? equals (key, node->key)
             : key == node->key))
       {
-        *valuep = node->value;
+        if (valuep)
+          *valuep = node->value;
         return true;
       }
   return false;
diff --git a/lib/gl_linkedhash_map.c b/lib/gl_linkedhash_map.c
index 9e16971a0..000e33f6d 100644
--- a/lib/gl_linkedhash_map.c
+++ b/lib/gl_linkedhash_map.c
@@ -144,7 +144,8 @@ gl_linkedhash_search (gl_map_t map, const void *key, const void **valuep)
             ? equals (key, node->key)
             : key == node->key))
       {
-        *valuep = node->value;
+        if (valuep)
+          *valuep = node->value;
         return true;
       }
   return false;
diff --git a/lib/gl_map.h b/lib/gl_map.h
index 02a3ac376..790e3fa2b 100644
--- a/lib/gl_map.h
+++ b/lib/gl_map.h
@@ -133,8 +133,8 @@ extern size_t gl_map_size (gl_map_t map);
 extern const void * gl_map_get (gl_map_t map, const void *key);
 
 /* Search whether a pair with the given key is already in the map.
-   Return true and set *VALUEP to the value if found.
-   Return false if not present in the map.  */
+   If found, return true, and set *VALUEP to the value if VALUEP is non-NULL.
+   Otherwise, return false.  */
 extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep);
 
 /* Add a pair to a map.
diff --git a/lib/gl_omap.h b/lib/gl_omap.h
index d11474972..53571ec52 100644
--- a/lib/gl_omap.h
+++ b/lib/gl_omap.h
@@ -132,16 +132,17 @@ extern size_t gl_omap_size (gl_omap_t map);
 extern const void * gl_omap_get (gl_omap_t map, const void *key);
 
 /* Search whether a pair with the given key is already in the ordered map.
-   Return true and set *VALUEP to the value if found.
-   Return false if not present in the map.  */
+   If found, return true, and set *VALUEP to the value if VALUEP is non-NULL.
+   Otherwise, return false.  */
 extern bool gl_omap_search (gl_omap_t map, const void *key,
                             const void **valuep);
 
 /* Search the pair with the least key in the ordered map that compares
    greater or equal to the given THRESHOLD.  The representation of the
    THRESHOLD is defined by the THRESHOLD_FN.
-   Return true and store the found pair in *KEYP and *VALUEP if found.
-   Otherwise return false.  */
+   If found, return true, set *KEYP to the found key if KEYP is non-NULL,
+   and set *VALUEP to the found value if VALUEP is non-NULL.
+   Otherwise, return false.  */
 extern bool gl_omap_search_atleast (gl_omap_t map,
                                     gl_mapkey_threshold_fn threshold_fn,
                                     const void *threshold,
-- 
2.17.1

Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Bruno Haible]

Hi Colin,

> It's sometimes convenient to have a map whose values may be NULL, but in
> that case it's a little awkward to determine whether a key exists in the
> map: gl_map_get returns NULL for both "key not found" and "value is
> NULL", so one needs a local variable just for the purpose of passing its
> address to gl_map_search.

Yes. You can consider it "a little awkward", and you can get away with it
through an inline function like this:

static bool
gl_map_entry_exists (gl_map_t map, const void *key)
{
  const void *value;
  return gl_map_search (map, key, &value);
}

> Instead, allow the return pointers to be NULL, so that one can use
> gl_map_search (map, NULL, NULL) to check existence.

What you propose is MORE awkward, for two reasons:

  1) For this code, performance is relevant.

     On modern processors, conditional jumps are significantly more
     costly than a simple instruction on values and addresses in the
     cache. (Something like between 5 and 20 cycles, when a single
     elementary arithmetic or load/store instruction is 1 cycle.)
     Why? Because modern processors are pipelined, and a conditional jump
     stalls the pipeline. Or, in processors which have speculative execution,
     when there are more conditional jumps, the speculative execution
     depth is obviously reduced.
     So, allocating a variable on the stack, filling it, and then ignoring
     its value is FASTER than a conditional jump whose effect is to save
     1 store instruction.

     You'll also notice that this is why I wrote

       GL_MAP_INLINE const void *
       gl_map_get (gl_map_t map, const void *key)
       {
         const void *value = NULL;
         gl_map_search (map, key, &value);
         return value;
       }

     and not

       GL_MAP_INLINE const void *
       gl_map_get (gl_map_t map, const void *key)
       {
         const void *value;
         if (gl_map_search (map, key, &value)
           return value;
         else
           return NULL;
       }

  2) Allowing NULL pointers as arguments in all possible places is
     *not* a good coding style in general. (It may be a good practice,
     though, when you're being paid for a consulting project and your
     code will never be maintained once you have delivered it.)
     A large portion of these NULL checks is redundant; it clutters
     up the code and triggers conditional jumps. Additionally, it
     increases the burden of unit-testing the code.

It can be discussed whether the public API gl_map.h and gl_omap.h
should include functions like gl_map_entry_exists. Some people (like
the GNOME glib authors) attempt to provide all possible variants that
might some day be useful. Whereas I chose to provide a set of functions
that is not so large, and omit functions that can be implemented by the
user in a straightforward way. (gl_map_get is a notable exception to
this rule.) gl_map_entry_exists is clearly part of those functions
that users can implement themselves.

Bruno

Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Colin Watson]

On Mon, Feb 11, 2019 at 02:32:11AM +0100, Bruno Haible wrote:
> Hi Colin,
> 
> > It's sometimes convenient to have a map whose values may be NULL, but in
> > that case it's a little awkward to determine whether a key exists in the
> > map: gl_map_get returns NULL for both "key not found" and "value is
> > NULL", so one needs a local variable just for the purpose of passing its
> > address to gl_map_search.
> 
> Yes. You can consider it "a little awkward", and you can get away with it
> through an inline function like this:
> 
> static bool
> gl_map_entry_exists (gl_map_t map, const void *key)
> {
>   const void *value;
>   return gl_map_search (map, key, &value);
> }

Indeed, perhaps I should have mentioned that I already have exactly such
a thing for now, differing only in the choice of function name (I prefer
"contains" over "entry_exists").

So far, the only extra supporting code I've felt the need to write
around Gnulib's container types consists of (a) equals/hash/etc.
implementations for relevant types; (b) convenience wrappers for
creating lists of strings and suchlike; (c) iteration macros; (d)
map/omap "contains" checks.  The last of those feels like it's filling
in a gap in the interface, while the others feel more naturally
dependent on what sort of things are common in a particular application.

> > Instead, allow the return pointers to be NULL, so that one can use
> > gl_map_search (map, NULL, NULL) to check existence.
> 
> What you propose is MORE awkward, for two reasons:
> 
>   1) For this code, performance is relevant.

Fair enough.  In my application layer, I very much prefer improving the
readability of the application code over a handful of cycles, so I
hadn't really been thinking of situations where a few cycles would
matter; but I recognise that these APIs are used more widely.

>   2) Allowing NULL pointers as arguments in all possible places is
>      *not* a good coding style in general. (It may be a good practice,
>      though, when you're being paid for a consulting project and your
>      code will never be maintained once you have delivered it.)

I respect your opinion as the maintainer and if you don't want to
include this that's of course fine, but please could you refrain from
implying incompetence?  It's not nice.

For what it's worth, I was taking things like gl_list_iterator_next's
handling of nodep as a partial model.  It's clear that it's sometimes
acceptable to have NULL checks in similar situations in this code
(perhaps gl_map_search is significantly more of a hot path than
gl_list_iterator_next, but that isn't obvious _a priori_), and their
presence is thus a matter of judgement of trade-offs and not simply a
matter of one's inability to maintain code competently.  One ought to be
able to discuss reasonable trade-offs without having it suggested that
one is just churning out code paid by the line.

> It can be discussed whether the public API gl_map.h and gl_omap.h
> should include functions like gl_map_entry_exists. Some people (like
> the GNOME glib authors) attempt to provide all possible variants that
> might some day be useful. Whereas I chose to provide a set of functions
> that is not so large, and omit functions that can be implemented by the
> user in a straightforward way. (gl_map_get is a notable exception to
> this rule.) gl_map_entry_exists is clearly part of those functions
> that users can implement themselves.

While it's true that I'm well able to implement it myself, I think it's
a clearly helpful thing to have and the only thing I've noticed in the
various containers APIs that really feels like an interface omission;
I'd be happy to put together a patch for that if I thought it might be
accepted.  I see that you may have a different view, though.  (Of course
gl_list doesn't need this because gl_list_search returns a node rather
than the element itself, while gl_set_search returns a bool; the
asymmetry is a bit surprising to someone learning the interface, but
understandable enough.)

Thanks,

-- 
Colin Watson                                       [cjwatson@debian.org]

Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Bruno Haible]

Hi Colin,

> >   2) Allowing NULL pointers as arguments in all possible places is
> >      *not* a good coding style in general. (It may be a good practice,
> >      though, when you're being paid for a consulting project and your
> >      code will never be maintained once you have delivered it.)
> 
> I respect your opinion as the maintainer and if you don't want to
> include this that's of course fine, but please could you refrain from
> implying incompetence?  It's not nice.

I'm sorry that you understood it in that way. It was really not meant that
way. I remember your name as a long-time serious contributor to various
packages.

It must be possible to talk about coding style and good/bad practices.
Of course, what I said about these practices are _opinions_, and
  - Anyone can disagree with my opinions.
  - Opinions can change over time: You are showing that when I wrote
    the gl_list_iterator_next code, I apparently had a different
    opinion.
  - I do not even know whether you have the habit of allowing NULL
    arguments in general. Therefore I was not criticizing you; I was
    criticizing a certain aspect of the proposed patch. (Which is also
    what I constantly do before committing or submitting a patch myself:
    scrutinize it under aspects that, from experience, are known as
    good or bad practices.)

The sentence about the consulting project was not about you as a person
either; it was meant as a reflection about a condition when I would find
it justified to employ that "bad" coding style myself.

Can we be friends again?

Bruno

Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Colin Watson]

On Mon, Feb 11, 2019 at 04:39:13AM +0100, Bruno Haible wrote:
> The sentence about the consulting project was not about you as a person
> either; it was meant as a reflection about a condition when I would find
> it justified to employ that "bad" coding style myself.
> 
> Can we be friends again?

Of course.  Thanks for clarifying your position!

-- 
Colin Watson                                       [cjwatson@debian.org]

Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Bruno Haible]

Hi Colin,

> So far, the only extra supporting code I've felt the need to write
> around Gnulib's container types consists of (a) equals/hash/etc.
> implementations for relevant types

Yes, these are definitely something the application package needs to
provide.

> (b) convenience wrappers for creating lists of strings and suchlike

Yes, it would really be good to have such wrappers automatically
generated (like the compiler does for C++, when you have templates).
Maybe a concept of a "parameterized gnulib module" would help? It
would create source code by substituting application-provided tokens
into gnulib-provided template code.

> (c) iteration macros;

How do your macros look like? I haven't provided such macros, because
all ways to define such macros I can imagine have major drawbacks.
Maybe yours are better?

> For what it's worth, I was taking things like gl_list_iterator_next's
> handling of nodep as a partial model.  It's clear that it's sometimes
> acceptable to have NULL checks in similar situations in this code

Apparently I didn't think as strongly at the NULL checks when I
implemented these. Or maybe I found it hard to explain why we would
have 2 functions gl_list_iterator_get_next (which produces the value)
and gl_list_iterator_next (which ignores the value).

> (d) map/omap "contains" checks.  The last of those feels like it's filling
> in a gap in the interface
> ...
> the only thing I've noticed in the
> various containers APIs that really feels like an interface omission

OK, I can add such a function, as an inline function in gl_map.h and
gl_omap.h.

> choice of function name (I prefer "contains" over "entry_exists").

'gl_map_contains'? Hmm, one would expect that it takes the key and the value
as arguments.
'gl_map_entry_exists'? Likewise.
Probably I'll name it 'gl_map_haskey'.

Bruno