I think meson might be beneficial as a build system to simplify the build file and allow building on most targets (without having to hardcode paths to homebrew or likewise).

Hi :)

I write here because I already run out of ideas about how to solve the issue I am facing. The issue may not be 100% related with the library, but I appreciate any help.

At the moment I am using the library in the crazyflie project (https://github.com/bitcraze/crazyflie-firmware). It is a drone running FreeRTOS.

As far as I tested, everything is working properly, except for the dict_free function.

What I did:

• Setup the dict_malloc_func and dict_free_func functions, so instead of using malloc and free, the use the ones provided by freeRTOS:

void configure_dict_malloc() {
  dict_malloc_func = pvPortMalloc;
  dict_free_func = vPortFree;
}

• Call dict_free with the following code:

void key_val_free(void *key, void *value) {
  dict_free_func(key);
  dict_free_func(value);
}

void anyFunction() {
  dict *dct = hashtable2_dict_new(dict_uint_cmp, dict_uint_hash, hash_table_initial_size); 
  
  .... other code inserting/removing keys ....

  dict_free(dct, key_val_free);
}

When calling dict_free, in the execution of key_val_free the application is crashing with the error:

"SYS: Assert failed src/lib/FreeRTOS/portable/MemMang/heap_4.c:317"

The code for heap_4.c is:

After getting all this information, I still did not manage to troubleshoot the issue. Does this error ring any bells?

Thank you very much!

Using uint8_t instead of string will probably improve performance. I tried the following:

static dict *dct = NULL;

int uint8cmp(const uint8_t *left, const uint8_t *right) {
  uint8_t leftValue = *left;
  uint8_t rightValue = *left;

  print("Key: '%d'", leftValue);
  print("Key: '%d'", rightValue);

  if (*left == *right) {
    return 0;
  } else if (*left < *right) {
    return -1;
  } else {
    return 1;
  }
}


static void init() {
  dct = hashtable2_dict_new((dict_compare_func)uint8cmp, dict_str_hash, 10);
}

static void test() {
  uint8_t key = 1;
  dict_insert_result result = dict_insert(dct, &key);

  if (result.inserted) {
    *result.datum_ptr = "example value";
    print("inserted '%d': '%s'\n", key, (char *)*result.datum_ptr);
  } else {
    print("Didnt work!");
  }

  void** search = dict_search(dct, &key);
  if (search) {
    print("found '%d': '%s'\n", key, *(char **)search);
  } else {
    print("'%d' not found!\n", key);
  }
}

When running the test function I got:

inserted '1': 'example value'
'1' not found!

Which means that not even uint8cmp was called.

Also, I tried using int instead of uint_8, and using strcmp instead a custom comparator. This worked (but I guess it was just a coincidence):

static void init() {
  dct = hashtable2_dict_new((dict_compare_func)strcmp, dict_str_hash, 10);
}

static void test() {
  int key = 1;
  dict_insert_result result = dict_insert(dct, &key);

  if (result.inserted) {
    *result.datum_ptr = "example value";
    print("inserted '%d': '%s'\n", key, (char *)*result.datum_ptr);
  } else {
    print("Didnt work!");
  }

  void** search = dict_search(dct, &key);
  if (search) {
    print("found '%d': '%s'\n", key, *(char **)search);
  } else {
    print("'%d' not found!\n", key);
  }
}

TwrSwarmAlgorithm twrSwarmAlgorithm = {
  .init = init,
  .test = test
};

In this case, it worked and I got in the screen:

inserted '1': 'example value'
found '1': 'example value'

I think a pkg-config file would be beneficial to allow other build systems to use this.

Implement selection by index, especially on e.g. weight-balanced tree

I'm trying to use this in a submodule for a project and I can't seem to make just the static library. If I "make bin/libdict.a" then I get errors about certain files not being compiled yet and if I "make all" then it needs CUnit installed (which I cannot guarantee for my own users).

Think unit tests could be less integrated so production builds are possible?

2-clause BSD license is written in the top level LICENSE file.
Through 4-clause BSD license is written in the header of src/hb_tree.c.
Could you update the headers?

Hi Farook,
I am experimenting a Segmentation fault with splay_tree implementation in libdict.

Basically, the memory violation occurs when I attempt to add a high number of items.
With a numer of items up to 1-e5 all my units tests are ok and also valgrind does not give any errors.

If I use 1-e6 number of items the program crashes.

System: Linux nuc 3.2.0-4-amd64 #1 SMP Debian 3.2.96-2 x86_64 GNU/Linux
Compiler: gcc version 7.2.0 (Debian 7.2.0-19)

[0] [email protected] 996> gdb ./splay_glue
GNU gdb (Debian 7.7.1+dfsg-5) 7.7.1
..............
(gdb) r -i add -6
[1] Running add ...............
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff788e1f6 in _int_free () from /lib/x86_64-linux-gnu/libc.so.6
(gdb) up
#1 0x0000555555557687 in tree_node_free (node=0x55555b30c0b0, delete_func=0x0) at /spool/git/tries/c/fmela/libdict/src/tree_common.c:302
302 FREE(node);
(gdb) up
#2 0x00005555555576a1 in tree_node_free (node=0x55555b30c110, delete_func=0x0) at /spool/git/tries/c/fmela/libdict/src/tree_common.c:304
304 tree_node_free(llink, delete_func);

In attempt to fix the problem I made my test program all inlined and you can find it in the attached tar-ball. Simply compile and run it as:
./splay_glue -i add -6 (that means run only the add test-unit using 1-e6 items)
(I have libdict source in /spool/git/tries/c/fmela/libdict/ so you need to edit Makefile to match your env)

Please do not hesitate to contact me if you need more info

splay-tree-crash.tar.gz

Best Regards
/rocco

The 'tree' is passed as argument to tree_node_min() instead
of tree->node. Please apply the following patch.

--- a/usr/lib/libdict/src/tree_common.c
+++ b/usr/lib/libdict/src/tree_common.c
@@ -179,7 +179,7 @@ tree_traverse(void* Tree, dict_visit_func visit)

 size_t count = 0;
 if (tree->root) {

•   tree_node\* node = tree_node_min(tree);
  

•   tree_node\* node = tree_node_min(tree->root);
  

Thanks,
Ashoka

Right now the source must by modified to use a custom malloc. From dict.c:

void* (*dict_malloc_func)(size_t) = malloc;
void (*dict_free_func)(void*) = free;

These functions cannot be changed after compilation, so we must edit dict.c to customize, adding CM complexity.
I propose the simple change:

#ifndef LIBDICT_USE_CUSTOM_MALLOC
void* (*dict_malloc_func)(size_t) = malloc;
void (*dict_free_func)(void*) = free;
#endif

In this way, the object can be compiled without those symbols defined, so that they can be linked in later.
The Makefile must also be changed to support this somehow, to pass the define through on CFLAGS, and also so that tests / pothe binaries built be the Makefile will either get linked with a version of dict.o with those symbols, or their own copies of the symbol definitions if the custom malloc is requested.

I have C and C++ files in my project and need to use your lib in both. After compiling each individually to .o-files, I stumbled upon one small bug that prevented me from linking them correctly with the static library of libdict. The error says "multiple definitions of 'dict_free_func'", as well as 'dict_malloc_func'.

I fixed this problem by adding the keyword 'extern' in front of the defs of these functions in include/dict.h (Line 73 and 75)
Cheers!

When traversing the dictionary types, there is no way to pass state except by holding it in a global variable. This make thread-safety and concurrency harder to implement.

@fmela As we discussed offline, I am making a ticket so I can submit a pull request against it.