Support for value pointers that are not word-aligned

[jeffpeterson]

Just an FYI! char pointers are not guaranteed to be word-aligned. For example, consider pointers into strings which can point to any byte. My first test of libhamt failed because this static string is not word aligned (the th pointer ended with 0010):

  struct hamt_config cfg = {.key_hash_fn = hash_string,
                            .key_cmp_fn = key_cmp,
                            .ator = &hamt_allocator_default};

  struct hamt *h = hamt_create(&cfg);

  char *hi = "hi";
  char *th = "there";
  hamt_set(h, hi, th);
  const char *v = hamt_get(h, hi);
  assert(key_cmp(v, th) == 0);

[mkirchner]

@jeffpeterson, thanks for reaching out and apologies for my tardiness.

You are correct: in the current implementation we require value pointers to be word-aligned so we can use a tagged pointer to distinguish between internal and leaf nodes. So using char pointers, depending on your use case, may break the (implicit and, yes, undocumented) contract for value pointers.

That said, this is really just a memory footprint optimization that we could easily forego with an explicit node type definition and a tagged struct:

enum hamt_node_type { HAMT_NODE_INTERNAL, HAMT_NODE_LEAF };

struct hamt_node {
    enum hamt_node_type node_type;  // <-- HERE
    union {
        struct {
            void *value;
            void *key;
        } kv;
        struct {
            struct hamt_node *ptr;
            uint32_t index;
        } table;
    } as;
};

We would also need to redefine the is_value(p) macro to test based on explicit type information and adapt the use of the tagged() and untagged() macros. Overall, this could probably be wrapped in a compilation flag HAMT_USE_TAGGED_POINTERS or similar to make the option available depending on the specific use case.

On the application side, there are two things we might want to keep in mind (and document): (a) increased memory usage; (b) memory allocation/deallocation might need to be able to deal with overlapping regions (e.g. in the substring case).

Is this of sufficient interest to you that you'd be willing to look into implementing this? If yes, great and let's collaborate. If no, thanks for sharing and I am happy to add it to the backlog but I don't have an ETA for completion.