10
\$\begingroup\$
  • Will be very grateful for thoughtful code review.
  • I needed hash table (again) and I wrote one. Code here is here or inline:
    #ifndef HASHTABLE_DEFINITION // single file library cannot use pragma once
    #define HASHTABLE_DEFINITION // https://en.wikipedia.org/wiki/Header-only
                                 // https://github.com/nothings/single_file_libs
    /*

     License: "Unlicense" (public domain) see bottom of the file for details.

     This is brain dead 4 hours implementation of #153 of absolutely non-universal,
     simple, growing, lineral rehash, key and value retaining hashtable with open
     read/write access to table entries.

     What it is NOT:
        It is not performance champion by any means.
        It does not use cyptograhically strong hash function.
        It is not designed for usage convience.

     Goals:
        As simple as possible.
        As reliable as possible.

     Limitations:
        key, val cannot exceed 2GB-1 bytes in size (can use int64_t instead of int32_t to make it bigger).
        Number of entries in a table cannot exceed (2GB - sizeof(hashtable_t)) / sizeof(hashtable_entry_t).
        Even replacing int32_t by int64_t does NOT make array of entries index 64 bit on the platforms
        where "int" is 32-bit (most of 64 bits platforms at the time of coding).
        It will be capable of indexing 2G entries (with some luck in indexof) but not 2^63 entries
        unless some additional indexing effort is added.

     Usage example:

        #define HASHTABLE_IMPLEMENTATION
        #include "hashtable.h"

        hashtable_t* ht = hashtable_create(16);
        if (ht == null) {
            perror("hashtable_create() failed"); // error is in "errno"
        } else {
            hashtable_kv_t key = {};
            hashtable_kv_t val = {};
            key.data = "Hello World!";
            key.bytes = (int32_t)strlen((char*)key.data);
            val.data = "Good bye cruel Universe...";
            val.bytes = (int32_t)strlen((char*)val.data);
            int r = hashtable_put(ht, &key, &val);
            // Adding key value pair to hashtable makes ht owned copy of kv data.
            // Adding can grow hashtable and pointers to entries will migrate to new
            // addressed. Called must NOT hold pointers to entry over "hashtable_add" call.
            if (r != 0) {
                perror("hashtable_put() failed"); // error is in "r" and also in errno
            } else {
                hashtable_entry_t* e = hashtable_get(ht, key.data, key.bytes);
                assert(e != null);
                assert(e->key.bytes == key.bytes && memcmp(e->key.data, key.data, key.bytes) == 0);
                assert(e->val.bytes == val.bytes && memcmp(e->val.data, val.data, val.bytes) == 0);
                // The content of e->val can be read and written at this point.
                // It will be very bad idea to touch e->key or e->hash here. Treat "key" as being read-only.
                // Caller should not hold the pointer to the entry over hashtable_add/remove/dispose calls.
                // See note above and below.
                hashtable_remove(ht, key.data, key.bytes);
                // Removal frees the hashtable owned copy of key value pair data.
                e = hashtable_get(ht, key.data, key.bytes);
                assert(e == null);
                hashtable_dispose(ht); // Frees all the memory used by hashtable.
            }
        }

      Inspiration: (nostalgic, obsolete, esoteric and buggy... but still in use)
        https://www.gnu.org/software/libc/manual/html_node/Hash-Search-Function.html
        https://github.com/ARM-software/u-boot/blob/master/lib/hashtable.c
        with the comment in the source code:
          [Aho, Sethi, Ullman] Compilers: Principles, Techniques and Tools, ***1986***
          [Knuth]              The Art of Computer Programming, part 3 (6.4)

      Questions and comments: Leo.Kuznetsov@gmail.com

    */

    #include <stdint.h>

    #ifdef __cplusplus
    extern "C" {
    #endif

    typedef struct hashtable_kv_s {
        void* data;
        int32_t bytes;
    } hashtable_kv_t;

    typedef struct hashtable_entry_s {
        hashtable_kv_t key;
        hashtable_kv_t val;
        uint32_t hash;
    } hashtable_entry_t;

    typedef struct hashtable_t {
        int32_t capacity;
        int32_t n;
        hashtable_entry_t* entries; // array[capacity]
    } hashtable_t;

    enum {
        HASHTABLE_INT32_MAX = (int32_t)-1U/2 == (int32_t)(-1U/2) ? (int32_t)-1U : (int32_t)(-1U/2), // INT_MAX
        HASHTABLE_MAX_CAPACITY = (HASHTABLE_INT32_MAX - sizeof(hashtable_t)) / sizeof(hashtable_entry_t)
    };

    hashtable_t* hashtable_create(int capacity); // capacity [16..HASHTABLE_MAX_CAPACITY]
    hashtable_entry_t* hashtable_get(hashtable_t* ht, const void* key, int32_t bytes);
    int  hashtable_put(hashtable_t* ht, const hashtable_kv_t* key, const hashtable_kv_t* val);
    void hashtable_remove(hashtable_t* ht, const void* key, int32_t bytes);
    void hashtable_dispose(hashtable_t* ht);

    #ifdef __cplusplus
    } // extern "C"
    #endif

    #endif // HASHTABLE_DEFINITION

    #ifdef HASHTABLE_IMPLEMENTATION

    #include <stdlib.h>
    #include <stdbool.h>
    #include <string.h>
    #include <errno.h>
    #include <assert.h>

    #define byte uint8_t
    #define null ((void*)0)
    #define memequ(a, b, n) (memcmp((a), (b), (n)) == 0)
    #define hashtable_mem_alloc malloc
    #define hashtable_mem_free free

    static const byte HASHTABLE_REMOVED_KEY; // unique address designating removed key for linear rehash

    static inline void hashtable_mem_free_not_removed(void* data) {
        // since &HASHTABLE_REMOVED_KEY is unique no harm comparing any other address with it
        if (data != &HASHTABLE_REMOVED_KEY) { hashtable_mem_free(data); }
    }

    static inline void hashtable_kv_free(hashtable_kv_t* kv) {
        if (kv != null) { // unnecessary := null and := 0 assignments will be removed by optimizations
            hashtable_mem_free_not_removed(kv->data); kv->data = null; kv->bytes = 0;
        }
    }

    static uint32_t hashtable_hash(const byte* key, int bytes);
    static int hashtable_kv_dup(hashtable_kv_t* d, const hashtable_kv_t* s);
    static int hashtable_grow(hashtable_t* ht);
    static int hashtable_indexof(hashtable_t* ht, const hashtable_entry_t* e) { return (int)(e - ht->entries); }

    hashtable_t* hashtable_create(int capacity) { // capacity [16..HASHTABLE_MAX_CAPACITY]
        int r = 0;
        hashtable_t* ht = null;
        assert(16 <= capacity && capacity < HASHTABLE_MAX_CAPACITY);
        if (16 <= capacity && capacity < HASHTABLE_MAX_CAPACITY) {
            ht = (hashtable_t*)hashtable_mem_alloc(sizeof(hashtable_t));
            if (ht == null) {
                r = errno;
            } else {
                memset(ht, 0, sizeof(hashtable_t));
                int32_t bytes = capacity * sizeof(hashtable_entry_t);
                ht->entries = (hashtable_entry_t*)hashtable_mem_alloc(bytes);
                if (ht->entries == null) {
                    r = errno; // save to protect against hashtable_mem_free() setting "errno"
                    hashtable_mem_free(ht);
                    ht = null;
                } else {
                    ht->capacity = capacity;
                    memset(ht->entries, 0, bytes);
                }
            }
        } else {
            r = EINVAL;
        }
        if (r != 0) { errno = r; }
        return ht;
    }

    void hashtable_free_entries(hashtable_t* ht) {
        for (int i = 0; i < ht->capacity; i++) {
            hashtable_kv_free(&ht->entries[i].key);
            hashtable_kv_free(&ht->entries[i].val);
        }
    }

    void hashtable_dispose(hashtable_t* ht) {
        hashtable_free_entries(ht);
        hashtable_mem_free(ht->entries);
        hashtable_mem_free(ht);
    }

    static hashtable_entry_t* hashtable_find(hashtable_t* ht, uint32_t hash, const void* key, int32_t bytes) {
        // Last time I've checked idiv r32:r32 was pretty expensive on most ARM, Intel and AMD
        // processors, thus loop below uses increment and compare instead of extra "%" operation.
        // http://uops.info/table.html
        int ix = (int)(hash % ht->capacity); // arrays are indexed by "int" in C
        const int a = ix; // `again` full circle index value after visiting all entries
        do {
            hashtable_entry_t* e = &ht->entries[ix];
            if (e->key.data == null) { break; }
            if (hash == e->hash && e->key.bytes == bytes && memequ(e->key.data, key, bytes)) { return e; }
            ix++;
            if (ix == ht->capacity) { ix = 0; }
        } while (ix != a);
        return null;
    }

    hashtable_entry_t* hashtable_get(hashtable_t* ht, const void* key, int32_t bytes) {
        return hashtable_find(ht, hashtable_hash(key, bytes), key, bytes);
    }

    int hashtable_put(hashtable_t* ht, const hashtable_kv_t* key, const hashtable_kv_t* val) {
        int r = 0;
        assert(key->data != null && 1 <= key->bytes && key->bytes < HASHTABLE_INT32_MAX);
        if (key->data != null && 1 <= key->bytes && key->bytes < HASHTABLE_INT32_MAX) {
            uint32_t hash = hashtable_hash(key->data, key->bytes);
            hashtable_entry_t* e = hashtable_find(ht, hash, key->data, key->bytes);
            if (e != null) {
                r = hashtable_kv_dup(&e->val, val);
            } else {
                int ix = (int)(hash % ht->capacity);
                const int a = ix;
                while (r == 0) {
                    e = &ht->entries[ix];
                    bool removed = e->key.data == &HASHTABLE_REMOVED_KEY;
                    if (e->key.data == null || removed) {
                        r = hashtable_kv_dup(&e->key, key);
                        if (r == 0) {
                            r = hashtable_kv_dup(&e->val, val);
                            if (r != 0) { // restore key to retained value
                                hashtable_kv_free(&e->val);
                                e->key.data = removed ? (void*)&HASHTABLE_REMOVED_KEY : null;
                            }
                        }
                        if (r == 0) {
                            e->hash = hash;
                            ht->n++;
                            if (ht->n > ht->capacity * 3 / 4) { r = hashtable_grow(ht); }
                        }
                        break;
                    }
                    ix++;
                    if (ix == ht->capacity) { ix = 0; }
                    // the only way for ix == a is the table previous failure to grow was ignored
                    if (ix == a) { r = ENOMEM; break; } // hit initial value of 'h' again...
                }
            }
        } else {
            r = EINVAL;
        }
        return r;
    }

    void hashtable_remove(hashtable_t* ht, const void* key, int32_t bytes) {
        hashtable_entry_t* e = hashtable_get(ht, key, bytes);
        if (e != null) {
            assert(e->key.data != (void*)&HASHTABLE_REMOVED_KEY);
            hashtable_kv_free(&e->key);
            hashtable_kv_free(&e->val);
            int next = hashtable_indexof(ht, e) + 1;
            if (next == ht->capacity) { next = 0; }
            e->key.data = ht->entries[next].key.data == null ? null : (void*)&HASHTABLE_REMOVED_KEY;
            ht->n--;
        }
    }

    static int hashtable_grow(hashtable_t* ht) {
        int r = 0;
        if (ht->capacity < HASHTABLE_MAX_CAPACITY * 2 / 3) {
            int capacity = ht->capacity * 3 / 2;
            int32_t bytes = capacity * sizeof(hashtable_entry_t);
            hashtable_entry_t* entries = (hashtable_entry_t*)hashtable_mem_alloc(bytes);
            if (entries == null) {
                r = errno;
            } else {
                memset(entries, 0, bytes);
                for (int i = 0; i < ht->capacity; i++) {
                    hashtable_entry_t* e = &ht->entries[i];
                    if (e->key.data != null && e->key.data != &HASHTABLE_REMOVED_KEY) {
                        int ix = (int)(e->hash % capacity);
                        for (;;) {
                            if (entries[ix].key.data == null) { entries[ix] = *e; break; }
                            ix++;
                            if (ix == capacity) { ix = 0; }
                        }
                    }
                }
                hashtable_mem_free(ht->entries);
                ht->entries = entries;
                ht->capacity = capacity;
            }
        } else {
            r = E2BIG;
        }
        if (r != 0) { errno = r; }
        return r;
    }

    static int hashtable_kv_dup(hashtable_kv_t* d, const hashtable_kv_t* s) {
        int r = 0; // similar to strdup() but for a (data,bytes) pair
        if (d->bytes == s->bytes) {
            memcpy(d->data, s->data, s->bytes);
        } else {
            void* dup = hashtable_mem_alloc(s->bytes);
            if (dup == null) {
                r = errno;
            } else {
                hashtable_mem_free_not_removed(d->data);
                d->data = dup;
                d->bytes = s->bytes;
                memcpy(d->data, s->data, s->bytes);
            }
        }
        return r;
    }

    static uint32_t hashtable_hash(const byte* data, int bytes) { // http://www.azillionmonkeys.com/qed/hash.html
        #define get16bits(a) (*((const uint16_t*)(a)))
        uint32_t hash = bytes;
        uint32_t tmp;
        if (bytes <= 0 || data == null) { return 0; }
        int32_t reminder = bytes & 3;
        bytes >>= 2;
        while (bytes > 0) {
            hash  +=  get16bits(data);
            tmp    = (get16bits(data + 2) << 11) ^ hash;
            hash   = (hash << 16) ^ tmp;
            data  += 2 * sizeof(uint16_t);
            hash  += hash >> 11;
            bytes--;
        }
        switch (reminder) { /* Handle end cases */
            case 3: hash += get16bits(data);
                hash ^= hash << 16;
                hash ^= ((int8_t)data[sizeof(uint16_t)]) << 18;
                hash += hash >> 11;
                break;
            case 2: hash += get16bits(data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
            case 1: hash += (int8_t)data[0];
                hash ^= hash << 10;
                hash += hash >> 1;
                break;
            case 0: break;
        }
        /* Force "avalanching" of final 127 bits */
        hash ^= hash << 3;
        hash += hash >> 5;
        hash ^= hash << 4;
        hash += hash >> 17;
        hash ^= hash << 25;
        hash += hash >> 6;
        return hash;
    }

    /*

    This is free and unencumbered software released into the public domain.

    Anyone is free to copy, modify, publish, use, compile, sell, or
    distribute this software, either in source code form or as a compiled
    binary, for any purpose, commercial or non-commercial, and by any
    means.

    In jurisdictions that recognize copyright laws, the author or authors
    of this software dedicate any and all copyright interest in the
    software to the public domain. We make this dedication for the benefit
    of the public at large and to the detriment of our heirs and
    successors. We intend this dedication to be an overt act of
    relinquishment in perpetuity of all present and future rights to this
    software under copyright law.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
    OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    OTHER DEALINGS IN THE SOFTWARE.

    For more information, please refer to <http://unlicense.org/>

    */
    #endif
\$\endgroup\$
  • 3
    \$\begingroup\$ URL shorteners are deprecated on Stack Exchange. To those people who don't want to risk: the link OP posted is gist.github.com/leok7v/e5a5acdf79cc222cbac007b309fd0e01, and does not contain malware. To OP: consider replace the URL shortener with the actual link, so everyone can securely visit it. \$\endgroup\$ – L. F. Jul 8 at 23:44
  • \$\begingroup\$ @L.F. It's better to just suggest an edit for things like this. ;) \$\endgroup\$ – jpmc26 Jul 9 at 1:37
  • \$\begingroup\$ @jpmc26 OK, I guess I'll do that in the future :) \$\endgroup\$ – L. F. Jul 9 at 1:41
  • \$\begingroup\$ Is there a reason you don't want to use an existing library? I'm not a C expert, but uthash appears to be popular and there are others. \$\endgroup\$ – jpmc26 Jul 9 at 1:52
10
\$\begingroup\$

typedef _t

POSIX reserves identifiers ending in _t. You should maybe use _s also for the typedef:

struct Foobar {
    void    *foo;
    int32_t bar;
};
typedef struct Foobar foobar_s;

Or not use typedef at all.


#define _MAX

POSIX reserves identifiers ending in _MAX or _MIN.

For your macros (or consts, but don't use enum for that) that design maximums or minimums, I recommend using prefixes:

#define MAX_FOO (5)

C / C++

C and C++ are very different languages. Working in the common subset is very difficult, and not always optimum. I recommend writing the program in C, and then writing specialized C++ headers (.hpp) which link to your C code.


ODR

C17:

J.5.11 Multiple external definitions

1 There may be more than one external definition for the identifier of an object, with or without the explicit use of the keyword extern ; if the definitions disagree, or more than one is initialized, the behavior is undefined (6.9.2).

Don't define extern functions (non-static functions) in header files. If you include this header from multiple source files, you will have defined your functions more than once, and the linker will (or at least should) complain.


static inline vs C99 inline

static inline might look as a magic macro: One uses static inline when one wants a function to always be inlined. It has extra safety that a macro doesn't, and all the benefits (in theory).

Problem: inline is only a hint to the compiler; it can decide not to inline a function, and then the bloating starts: being a static function, every file will have its own copy of the same function.

Secondary problem (unlikely to be important for most programs): Two pointers to the same static inline function acquired from different files are unequal even when the function contents are the same.

Solution: C99 inline. The scheme for using C99 inline is the following:

file.h:

inline
int     foo(int a);

inline
int     foo(int a)
{
        /* definition */
}

file.c:

extern
int     foo(int a);

If you want your function to always be inlined you can use compiler specific extensions. Note: Use always_inline only for very short functions (1 - 3 lines), or when you are 100% sure that most of the code will go away at compile time. I will add an example for GCC, but if you want portability you will have to create a macro that adapts to all the compilers you want to support:

file.h:

__attribute__((always_inline))
inline
int     foo(int a);

inline
int     foo(int a)
{
        /* definition */
}

file.c:

extern
int     foo(int a);

Source: http://www.greenend.org.uk/rjk/tech/inline.html


magic numbers

What is a magic number, and why is it bad?

Don't use any numbers different than 0, 1, or 2 in your code. The only place where numbers deserve to go is in constant macros like this:

#define FOO (5)

Don't cast the result of malloc

Do I cast the result of malloc?

NEVER, in my opinion. (There's a debate in that link. There's people that argues that you should always cast it. Form your own opinion based on what you read there).


Safe usage of malloc

Malloc is easily misused. Problems that can arise using malloc are the following:

  • casting the result: As said above, never do this.

  • sizeof(type) vs sizeof(*foo):

foo = malloc(sizeof(*foo) * nmemb); is better because if you ever change the type of foo, this call will still be valid, while if not, you would have to change every line where malloc is called with foo. If you forget any of those lines, good luck.

  • overflow:

If (sizeof(*foo) * nmemb) > SIZE_MAX, it will silently wrap around, and allocate a very small amount of memory, and you will most likely end up accessing to memory that you shouldn't.

Solution:

Use this enclosure around malloc


errno

free() doesn't set errno so you don't need to save the value of errno in a temp variable .

Source: man 3 free


re#define the name of a function

Don't do this. It is very weird and unexpected. Unless you have a very good reason use an always_inline function:

inline
void    hashtable_mem_free(void *p)
        __attribute__((always_inline));


inline
void    hashtable_mem_free(void *p)
{

        free(p);
}

Right margin at 80 characters

This is a rule in most coding standards for good reasons.

This (copied from your code) is unreadable:

                if (hash == e->hash && e->key.bytes == bytes && memequ(e->key.data, key, bytes)) { return e; }

And the most important thing is that you are hiding a return statement where most of the screens will not show (unless you scroll).

Solution:

                if ((hash == e->hash)  &&  (e->key.bytes == bytes)  &&
                                        memequ(e->key.data, key, bytes)) {
                        return e;
                }

static in headers

Don't use static in headers. The reason is basically the same as static inline; given that inline is a hint, they are literally the same (for functions).

In variables, it's even more dangerous, because modifying a variable from one file won't affect the same (actually not the same) variable in another file.

A good compiler should warn about this.


assert

static_assert (> C11) is a very good thing. assert isn't that much.

A user of a program expects the program to handle errors silently and maybe warn the user when some error is important; but the user expects a program to never break, so a program should only break when there is absolutely no other possibility.

Remember BSOD? Like it? I hope not.

A good reading about it: LKML thread

\$\endgroup\$
  • 1
    \$\begingroup\$ you should add that people strongly disagree about whether to cast the result of malloc. you may say never, but I would say always \$\endgroup\$ – sudo rm -rf slash Jul 9 at 7:18
  • \$\begingroup\$ @sudorm-rfslash agree to disagree :) \$\endgroup\$ – Cacahuete Frito Jul 9 at 7:56
  • 1
    \$\begingroup\$ That's a really weird argument against asserts. Personally I prefer programs to crash instead of silently corrupting my data, opening up security exploits or simply doing the wrong thing. Kernel mode is a completely different beast to user mode - are you also going to argue against limited recursion and the use of floating point because both of those things are rarely used in Kernel code? (and even in the Kernel there are very good arguments to simply crash and burn if some important state is corrupted - there's just a higher threshold for that) \$\endgroup\$ – Voo Jul 9 at 8:04
  • \$\begingroup\$ @Voo Those are cases where assert would be OK, but for example: If a program needs to be sure that a data is correct to do an operation: you can assert it and save the data (and abort otherwise), or you can save the data if it is correct, and just not save it if it's not and tell the user why and maybe return to a main menu or something like that. Maybe it's the "absolutely no other possibility" threshold that is a bit lower on user programs, but I think the reason is very valid \$\endgroup\$ – Cacahuete Frito Jul 9 at 8:11
3
\$\begingroup\$

It's been a long time since I've coded in C, so bear with me.

#define

Your implementation's #define statements puzzle me. #define is a directive, essentially a macro, best used to define constants. With that said:

  • You should use typedef for type definitions. #define will only be respected by a preprocessor as a copy/paste directive, and nothing more. typedef will actually name a new type.

Example:

// using #define
#define PTR char*

PTR a, b, c; // creates char *a, char b, char c
// using typedef
typedef char* PTR;

PTR a, b, c; // creates char *a, char *b, char *c
  • Why not use NULL for null pointer?
  • Why redefine malloc/free? You don't lose any clarity by leaving them as-is
  • memequ(a, b, n) should just be a function, regardless of how simple it is

assert

The assert statement below already necessitates the following condition. Its corresponding else statement will never be executed.

assert(16 <= capacity && capacity < HASHTABLE_MAX_CAPACITY);
if (16 <= capacity && capacity < HASHTABLE_MAX_CAPACITY) {

And while we're looking at those lines, why is 16 hardcoded here? Wouldn't it make sense to #define that as a minimum capacity?

#define HASHTABLE_MIN_CAPACITY 16

enum

On that same note, the enum in HASHTABLE_DEFINITION doesn't make sense. Enums are generally used to define constants of the same enumeration.

Example:

enum State{SUCCESS, FAILED, INTERRUPTED}

I would recommend making them const variables instead.

I haven't read through any of the hashtable logic itself yet, but I felt the rest here was important enough already.

\$\endgroup\$
  • \$\begingroup\$ assert shouldn't be used lightly. I don't want a program to break unexpectedly, but instead solve the problems and report them if necessary. assert should be used in extreme cases. Read this thread in LKML: lkml.iu.edu/hypermail/linux/kernel/1610.0/00878.html \$\endgroup\$ – Cacahuete Frito Jul 8 at 15:23
  • \$\begingroup\$ @Cacahuete Frito Makes sense! I was specifically referring to how his assert statement did not play well with the subsequent conditional logic, but I can see how not using assert to begin with would be preferable. \$\endgroup\$ – TCFP Jul 8 at 15:32
  • \$\begingroup\$ Oh, sorry. I thought you were changing an if to an assert. I didn't see that the OP used assert :-) \$\endgroup\$ – Cacahuete Frito Jul 8 at 15:34
2
\$\begingroup\$

The comment

        // It will be very bad idea to touch e->key or e->hash here. Treat "key" as being read-only.
        // Caller should not hold the pointer to the entry over hashtable_add/remove/dispose calls.

suggests that hashtable_get should return the value, rather than the entry pointer. The caller already knows the key, there is no point returning it.

In fact, I don't see a legitimate reason for a client to know the entry pointer at all. Consider hashtable_get_and_remove() and hashtable_put_or_replace() interfaces instead.


I am not sure I like the idea of partitioning the hashtable.h file by HASHTABLE_DEFINITION and HASHTABLE_IMPLEMENTATION macros. A change in the lower portion of the file will still cause recompilation of the client code, even though it is absolutely irrelevant. Besides, with this organization the client must pay a special attention to #define HASHTABLE_IMPLEMENTATION exactly once ad only once. Consider moving the implementation part into a separate hashtable_impl.c


Do not throw away what has been computed. find returns null even though it has found an insertion point. Should it return the insertion point instead, you could use this information in put.


It is usually a good idea to let the client pick another hash function, which would suite their dataset better. A cost of an indirect function call would be offset by smaller number of collisions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.