[systemd-devel] [PATCH 21/26] hashmap: rewrite the implementation

[Lennart Poettering]

On Thu, 16.10.14 09:50, Michal Schmidt (mschmidt at redhat.com) wrote:

> +/* Distance from Initial Bucket */
> +typedef uint8_t dib_raw_t;
> +#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
> +#define DIB_RAW_REHASH   ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
> +#define DIB_RAW_FREE     ((dib_raw_t)0xffU) /* a free bucket */
> +#define DIB_RAW_INIT   ((char)DIB_RAW_FREE) /* a byte to memset a
> DIB store with when initializing */

Not sure I am a fan of typedeffing things like this if we only use it
internally, but doesn't matter really...

> +enum {
> +        HASHMAP_TYPE_PLAIN,
> +        HASHMAP_TYPE_LINKED,
> +        HASHMAP_TYPE_SET,
> +        __HASHMAP_TYPE_COUNT
> +};

Why is this enum anonymous? Wouldn't it be nicer to give it a name? We
only use it internally only anyway...

So far we called the final counting entry of such enums _FOOBAR_MAX,
not __FOOBAR_COUNT, please stick to this naming scheme... (also iirc
the C standard reserves the double "_" prefix for the language
itself. The kernel ignores that C standard issue so far, but we should
probably honour it.

> +/* Fields that all hashmap/set types must have */
> +struct HashmapBase {
> +        const struct hash_ops *hash_ops;  /* hash and compare ops to use */
> +
> +        union _packed_ {
> +                struct indirect_storage indirect; /* if  has_indirect */
> +                struct direct_storage direct;     /* if !has_indirect */
> +        };
> +
> +        uint8_t type:2;             /* HASHMAP_TYPE_* */

Should probably be a named enum (see above)

> +        uint8_t has_indirect:1;     /* whether indirect storage is
> used */

Should really be a "bool", no?

>  
> -int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops) {
> -        Hashmap *q;
> +static void __remove_entry(HashmapBase *h, unsigned idx) {
> +        unsigned left, right, prev, dib;
> +        dib_raw_t raw_dib, *dibs;

Don't like the double __ prefix for fucntions here either...

> +static struct HashmapBase *__hashmap_new(const struct hash_ops *hash_ops, uint8_t type  HASHMAP_DEBUG_PARAMS) {
> +        HashmapBase *h;
> +
> +        h = malloc0(all_hashmap_sizes[type]);
> +        if (!h)
> +                return NULL;
> +

Hmm, a malloc() for each hashmap we allocate? Isn#t that prohibitively
expensive given how slow malloc() is? We have soo many hashmaps!

> +        h->type = type;
> +        h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops;
> +
> +        if (type == HASHMAP_TYPE_LINKED) {
> +                LinkedHashmap *lh = (LinkedHashmap*)h;
> +                lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
> +        }
> +
> +        reset_direct_storage(h);
> +
> +        if (!shared_hash_key_initialized) {
> +                random_bytes(shared_hash_key, sizeof(shared_hash_key));
> +                shared_hash_key_initialized= true;
> +        }
> +
> +#ifdef ENABLE_HASHMAP_DEBUG
> +        LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
> +        h->debug.func = func;
> +        h->debug.file = file;
> +        h->debug.line = line;
> +#endif
> +
> +        return h;
> +}
> +
> +Hashmap *_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
> +        return (Hashmap*)       __hashmap_new(hash_ops, HASHMAP_TYPE_PLAIN  HASHMAP_DEBUG_PASS_ARGS);
> +}
> +
> +LinkedHashmap *_linked_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
> +        return (LinkedHashmap*) __hashmap_new(hash_ops, HASHMAP_TYPE_LINKED  HASHMAP_DEBUG_PASS_ARGS);
> +}
> +
> +Set *_set_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
> +        return (Set*)           __hashmap_new(hash_ops, HASHMAP_TYPE_SET  HASHMAP_DEBUG_PASS_ARGS);
> +}

Not liking the double underscores... I know this is kernel style, but it's still in conflict with ISO C...

Can we maybe name this internal_xyz or so?

Beyond these superficialities I have nothing to complain. Didn't test
it though. But I trust you...

Lennart

-- 
Lennart Poettering, Red Hat