git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 2/2] hashmap: migrate documentation from Documentation/technical into header

From
Jonathan Nieder <jrnieder@gmail.com>
Date
Jun 29, 2017, 21:18 UTC
Message-ID
<20170629211832.GB68015@aiede.mtv.corp.google.com>
In-Reply-To
<20170629011334.11173-3-sbeller@google.com>
Stefan Beller wrote:
Show 11 quoted lines
> Subject: hashmap: migrate documentation from Documentation/technical into header
>
> While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well
> as documenting the new data pointer for the compare function.
>
> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>  Documentation/technical/api-hashmap.txt | 309 --------------------------------
>  hashmap.h                               | 249 +++++++++++++++++++++++--
>  2 files changed, 231 insertions(+), 327 deletions(-)
>  delete mode 100644 Documentation/technical/api-hashmap.txt
Yay, I love this.
[...]
> --- a/Documentation/technical/api-hashmap.txt
> +++ /dev/null
> @@ -1,309 +0,0 @@

Verified that these docs have all been migrated to the header, except where noted below.

[...]
Show 9 quoted lines
> -`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::
> -
> -	User-supplied function to test two hashmap entries for equality. Shall
> -	return 0 if the entries are equal.
> -+
> -This function is always called with non-NULL `entry` / `entry_or_key`
> -parameters that have the same hash code. When looking up an entry, the `key`
> -and `keydata` parameters to hashmap_get and hashmap_remove are always passed
> -as second and third argument, respectively. Otherwise, `keydata` is NULL.
This was really heard to read in the preimage.  Thanks for cleaning it up.
[...]
> -Usage example
> --------------
> -
> -Here's a simple usage example that maps long keys to double values.

What happened to this? I think it would be useful to include in a long comment at the top of the header. A worked example like this makes it easier to get one's bearings and know which functions to look at.

[...]
> -Using variable-sized keys
> --------------------------

Same question: should this discussion go in the hashmap_get() docstring, with a pointer from hashmap_remove()? Or should it go in test-hashmap.c, with a pointer in the docstrings of both?

[...]
Show 8 quoted lines
> +++ b/hashmap.h
> @@ -3,11 +3,18 @@
>  
>  /*
>   * Generic implementation of hash-based key-value mappings.
> - * See Documentation/technical/api-hashmap.txt.
> + *
>   */
nit: why the blank line?
Show 27 quoted lines
>  
> -/* FNV-1 functions */
> -
> +/*
> + * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
> + * http://www.isthe.com/chongo/tech/comp/fnv).
> + * `strhash` and `strihash` take 0-terminated strings, while `memhash` and
> + * `memihash` operate on arbitrary-length memory.
> + * `strihash` and `memihash` are case insensitive versions.
> + * `memihash_cont` is a variant of `memihash` that allows a computation to be
> + * continued with another chunk of data.
> + */
>  extern unsigned int strhash(const char *buf);
>  extern unsigned int strihash(const char *buf);
>  extern unsigned int memhash(const void *buf, size_t len);
> @@ -16,6 +23,15 @@ extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_
>  
>  static inline unsigned int sha1hash(const unsigned char *sha1)
>  {
> +	/*
> +	 * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
> +	 * for use in hash tables. Cryptographic hashes are supposed to have
> +	 * uniform distribution, so in contrast to `memhash()`, this just copies
> +	 * the first `sizeof(int)` bytes without shuffling any bits. Note that
> +	 * the results will be different on big-endian and little-endian
> +	 * platforms, so they should not be stored or transferred over the net.
> +	 */
This comment should go in front of the function instead of in its body, like this:
	/*
	 * Converts a crypto [...]
	 */
	static inline unsigned int sha1hash(...

because it is describing the purpose and usage of the function and not its implementation.

[...]
Show 11 quoted lines
> +/*
> + * User-supplied function to test two hashmap entries for equality. Shall
> + * return 0 if the entries are equal.
> + *
> + * This function is always called with non-NULL `entry` and `entry_or_key`
> + * parameters that have the same hash code.
> + *
> + * When looking up an entry, the `key` and `keydata` parameters to hashmap_get
> + * and hashmap_remove are always passed
> + * as second `entry_or_key` and third argument `keydata`, respectively.
> + * Otherwise, `keydata` is NULL.
strange wrapping
Show 5 quoted lines
> + *
> + * There are two modes for this function to be used:
> + * (a) When looking for an exact match of a given `entry`, then `keydata`
> + *     ought to be NULL, and this function should cast `entry` and
> + *     `entry_or_key` to the user entries and check for equality.

What does it mean that `keydata` ought to be NULL? Are you saying it will be NULL, or that someone has to ensure it's NULL, or something else?

> + * (b) When it is too expensive to allocate such a user entry (either because
> + *     it is large or varialbe sized, such that it is not on the stack),
> + *     Then the relevant data to check for equality should be passed via
> + *     ` keydata`.
stray space in "` keydata`".
> + *
> + * Resulting from these modes, this function should compare `keydata` to `entry`
> + * when `keydata` is not NULL. `entry_or_key` may be a bogus hashmap_entry (see
> + * hashmap_get_from_hash).
What is meant by a bogus hashmap_entry here?  (See also below.)
[...]
Show 5 quoted lines
> +/*
> + * struct hashmap is the hash table structure. Members can be used as follows,
> + * but should not be modified directly.
> + */
>  struct hashmap {
[...]
> +	/* Prevent automatic rehashes during inserts and deletes when set. */
> +	unsigned disallow_rehash : 1;
>  };

Please add a reference to hashmap_disallow_rehash so people know how to set this.

Show 12 quoted lines
>  
>  /* hashmap functions */
>  
> +/*
> + * Initializes a hashmap structure.
> + *
> + * `map` is the hashmap to initialize.
> + *
> + * The `equals_function` can be specified to compare two entries for equality.
> + * If NULL, entries are considered equal if their hash codes are equal.
> + *
> + * When the compare function needs specific user supplied `data`, it should

nit: it's not user supplied so much as caller supplied. Maybe this can say something like

	The `data` parameter can be used to provide additional data (a callback
	cookie) that will be passed to `equals_function` each time it is called.
	This allows a single `equals_function` to implement multiple comparison
	functions.
[...]
Show 5 quoted lines
> +/*
> + * Frees a hashmap structure and allocated memory.
> + *
> + * If `free_entries` is true, each hashmap_entry in the map is freed as well.
> + */

nit: Documentation/technical said the hashmap_entrys get freed using free(). Can't hurt to carry that note over, to save the reader from hunting down whether the struct hashmap allows setting a custom free function.

[...]
Show 6 quoted lines
> +/*
> + * Returns the hashmap entry for the specified key, or NULL if not found.
> + *
> + * `map` is the hashmap structure.
> + * `key` is a user data structure that starts with hashmap_entry that has at
> + *  least been initialized with the proper hash code (via `hashmap_entry_init`).
nit: strange alignment (extra space before "least").

Should these argument lists be formatted as a list somehow (e.g. leading "- " bullets, or with a blank line between them? (I don't have a strong opinion, just noticed they can be hard to read with everything run together.)

Show 9 quoted lines
> + * `keydata` is a data structure that holds just enough information to check
> + * for equality to a given entry.
> + *
> + * One of `key` or `keydata` shall be NULL.
> + *
> + * If an entry with matching hash code is found, `key` and `keydata` are passed
> + * to `hashmap_cmp_fn` to decide whether the entry matches the key.
> + */
>  extern void *hashmap_get(const struct hashmap *map, const void *key,
[...]
Show 7 quoted lines
> + * Removes a hashmap entry matching the specified key. If the hashmap
> + * contains duplicate entries equal to the specified key, only one of
> + * them will be removed.
> + *
> + * `map` is the hashmap structure.
> + * `key` is a user data structure that starts with hashmap_entry that has at
> + *  least been initialized with the proper hash code (via `hashmap_entry_init`).
nit: strange alignment again
[...]
>  extern void *hashmap_remove(struct hashmap *map, const void *key,
[...]
Show 11 quoted lines
> +/*
> + * Returns the hashmap entry for the specified hash code and key data,
> + * or NULL if not found.
> + *
> + * `map` is the hashmap structure.
> + * `hash` is the hash code of the entry to look up.
> + *
> + * If an entry with matching hash code is found, `keydata` is passed to
> + * `hashmap_cmp_fn` to decide whether the entry matches the key. The
> + * `entry_or_key` parameter points to a bogus hashmap_entry structure that
> + * should not be used in the comparison.

What is going on with this note about bogus entry_or_key? I have no idea what it is trying to say, neither in the preimage nor the postimage.

Show 5 quoted lines
> + */
>  static inline void *hashmap_get_from_hash(const struct hashmap *map,
> -		unsigned int hash, const void *keydata)
> +					  unsigned int hash,
> +					  const void *keydata)

In Documentation/technical, hashmap_get_from_hash was immediately after hashmap_get, making it more discoverable.

Should the descriptions of these two functions mention each other to bring about a similar effect?

[...]
Show 9 quoted lines
> @@ -91,7 +273,7 @@ int hashmap_bucket(const struct hashmap *map, unsigned int hash);
>   * manner appropriate to their usage.  This simply
>   * prevents the table from being unexpectedly re-mapped.
>   *
> - * If is up to the caller to ensure that the hashmap is
> + * It is up to the caller to ensure that the hashmap is
>   * initialized to a reasonable size to prevent poor
>   * performance.
>   *
The Documentation/technical/ text says:
	A call to allow rehashing does not force a rehash; that might happen
	with the next insert or delete.
which I find easier on the eyes than
	 * When value=0, allow future rehahses.  This DOES NOT force
	 * a rehash now.

Why not make this comment use the full description from Documentation/technical/ verbatim?

> @@ -104,10 +286,28 @@ static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)
[...]
Show 11 quoted lines
> -/* hashmap_iter functions */
>  
> +/*
> + * hashmap_iter functions
> + *
> + * Used to iterate over all entries of a hashmap. Note that it is
> + * not safe to add or remove entries to the hashmap while
> + * iterating.
> + */
> +
> +struct hashmap_iter {
nit: might be simpler to associate this comment with the struct:
	/*
	 * Used to iterate over ...
	 */
	struct hashmap_iter {
		...
	}

That way, the scope of what the comment is describing is clearer. When looking up the functions, I'm likely to look up the hashmap_iter type they use, so I'd end up reading this comment anyway.

Show 12 quoted lines
> +	struct hashmap *map;
> +	struct hashmap_entry *next;
> +	unsigned int tablepos;
> +};
> +
> +/* Initializes a `hashmap_iter` structure. */
>  extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
> +
> +/* Returns the next hashmap_entry, or NULL if there are no more entries. */
>  extern void *hashmap_iter_next(struct hashmap_iter *iter);
> +
> +/* Initializes the iterator and returns the first entry, if any). */
Stray paren?
Probably worth mentioning this is a convenience wrapper for iter_init
+ iter_next, like the Documentation/technical/ text did.
>  static inline void *hashmap_iter_first(struct hashmap *map,
The rest looks good.

Thanks and hope that helps, Jonathan

Previous: Jeff HostetlerNext: Stefan Beller
Message 9 of 26 in “Introduce data field in hashmap and migrate docs to header”
  1. 0/2 Introduce data field in hashmap and migrate docs to headerStefan Beller, Jun 29, 2017
  2. 1/2 hashmap.h: compare function has access to a data fieldStefan Beller, Jun 29, 2017
  3. Junio C HamanoJun 29, 2017
  4. Junio C HamanoJun 29, 2017
  5. Stefan BellerJun 29, 2017
  6. Junio C HamanoJun 30, 2017
  7. 2/2 hashmap: migrate documentation from Documentation/technical into headerStefan Beller, Jun 29, 2017
  8. Jeff HostetlerJun 29, 2017
  9. Jonathan NiederJun 29, 2017
  10. Stefan BellerJun 29, 2017
  11. 0/2 Introduce data field in hashmap and migrate docs to headerStefan Beller, Jun 29, 2017
  12. 1/2 hashmap.h: compare function has access to a data fieldStefan Beller, Jun 29, 2017
  13. Junio C HamanoJun 30, 2017
  14. Stefan BellerJun 30, 2017
  15. Junio C HamanoJun 30, 2017
  16. Stefan BellerJun 30, 2017
  17. Junio C HamanoJun 30, 2017
  18. Stefan BellerJun 30, 2017
  19. Junio C HamanoJun 30, 2017
  20. 2/2 hashmap: migrate documentation from Documentation/technical into headerStefan Beller, Jun 29, 2017
  21. 0/3 Introduce data field in hashmap and migrate docs to headerStefan Beller, Jun 30, 2017
  22. 1/3 hashmap.h: compare function has access to a data fieldStefan Beller, Jun 30, 2017
  23. 2/3 patch-ids.c: use hashmap correctlyStefan Beller, Jun 30, 2017
  24. Junio C HamanoJun 30, 2017
  25. Jeff KingJul 5, 2017
  26. 3/3 hashmap: migrate documentation from Documentation/technical into headerStefan Beller, Jun 30, 2017

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.