zsshen / c-common-data-structures Goto Github PK

I'd like to propose the new set of operation interfaces for HashMap container.

• Container Status Code:
  • SUCC: Indicate that the operation is finished successfully.
  • END: Indicate that the iterator locates at the end of the map.
  • ERR_NOINIT: Indicate that the container has not initialized.
  • ERR_NOMEM: Indicate that there is no capacity for key value pair insertion.
  • ERR_NOKEY: Indicate that the map entry cannot be found via the given key.
• Operation Interface:
  • int HashMapPut (HashMap*, Key, Value)
    • return: SUCC, ERR_NOINIT, ERR_NOMEM
  • int HashMapGet (HashMap_, Key, Value_)
    • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapFind (HashMap*, Key)
    • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapRemove (HashMap*, Key)
    • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapSize (HashMap*)
    • return: size, ERR_NOINIT
  • int HashMapSetHash (HashMap_, int(_)(Key))
    • return: SUCC, ERR_NOINIT
  • int HashMapSetCompare (HashMap_, int(_)(Key, Key))
    • return: SUCC, ERR_NOINIT
  • int HashMapSetCleanKey (HashMap_, void(_)(Key))
    • return: SUCC, ERR_NOINIT
  • int HashMapSetCleanValue (HashMap_, void(_)(Value))
    • return: SUCC, ERR_NOINIT
  • int HashMapHasNext (HashMap*)
    • return: SUCC, END, ERR_NOINIT
  • int HashMapNext (HashMap_, Pair_)
    • return: SUCC, END, ERR_NOINIT

Here is the simple draft, but there are still some issues to be solved:
Do users really need to care for the error return code?
Or, should we simply return the NULL for users when there is no memory capacity or the key cannot be found?

Hey TienLung,

Please refer to this API draft and try to refine the implementation.

// The constructor
Stack* StackInit();

// The destructor  
void StackDeinit(Stack*);

// Push an item to the top of the stack.
bool StackPush(Stack*, void*);

// Pop an item from the top of the stack.
void StackPop(Stack*);

// Retrieve an item from the top of the stack.
void* StackTop(Stack*);

// Get the number of stored items.
int StackSize(Stack*);

// Set the custom stack element clean method.
void StackSetClean(Stack*);

Regards,
ZongXian.

We should put "extern" for exported function in the header and "static" for internal function in .c files

We should put @code like Entry casting in map. It will be easier for user to understand

We shall use install in CMakeLists.txt to install library, document into system.

Hi Zong Xian,
I am experimenting your library in my own program. Focus is currently on hash_map.c
because I would like to benchmark your implementation.

my example program uses (char *) for hash keys and (void *) for hash values. but the execution fails is the number of pairs exceeds 577. The same problem does not occur if I use (unsigned) for hash keys.

I suspect there is a a problem each time the function _HashMapReHash (hash_map.c:380) is called to resize the hasp map. After the execution of this function some keys cannot be deleted.

take a look at the following output (the number of pairs to use is passed on the command line):
[email protected] 386> ./hash-map-str 577
libcds hashmap testsuite for checking memory with valgrind
Obj .......................... Ok
Alloc/Free ................... Ok
Alloc/Init/Free .............. Ok
Alloc/Insert/Free ............ Ok
Alloc/Insert/Search/Free ..... Ok
Alloc/Insert/Delete/Free ..... Ok
Alloc/Insert/Size/Free ....... 577 Ok
[email protected] 387> ./hash-map-str 578
libcds hashmap testsuite for checking memory with valgrind
Obj .......................... Ok
Alloc/Free ................... Ok
Alloc/Init/Free .............. Ok
Alloc/Insert/Free ............ Ok
Alloc/Insert/Search/Free ..... Ok
hash-map-str: hash-map-str.c:102: alloc_insert_delete_free: Assertion `HashMapRemove (ht, objs [i] -> skey, strlen (objs [i] -> skey)) == (0)' failed.
Alloc/Insert/Delete/Free ..... Abort

[email protected] 388> valgrind ./hash-map-str 577
libcds hashmap testsuite for checking memory with valgrind
Obj .......................... Ok
Alloc/Free ................... Ok
Alloc/Init/Free .............. Ok
Alloc/Insert/Free ............ Ok
Alloc/Insert/Search/Free ..... Ok
Alloc/Insert/Delete/Free ..... Ok
Alloc/Insert/Size/Free ....... 577 Ok
==13140==
==13140== HEAP SUMMARY:
==13140== in use at exit: 0 bytes in 0 blocks
==13140== total heap usage: 9,256 allocs, 9,256 frees, 212,682 bytes allocated
==13140==
==13140== All heap blocks were freed -- no leaks are possible
==13140==
==13140== For counts of detected and suppressed errors, rerun with: -v
==13140== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[email protected] 389> valgrind ./hash-map-str 578
==13144== Invalid read of size 1
==13144== at 0x402012: HashMurMur32 (hash.c:36)
==13144== by 0x401E31: _HashMapReHash (hash_map.c:380)
==13144== by 0x401505: HashMapPut (hash_map.c:152)
==13144== by 0x400BBA: alloc_insert_free (hash-map-str.c:61)
==13144== by 0x4010B8: main (hash-map-str.c:157)
==13144== Address 0x51debe2 is 0 bytes after a block of size 2 alloc'd
==13144== at 0x4C29C0F: malloc (vg_replace_malloc.c:299)
==13144== by 0x4EB6F19: strdup (in /lib/x86_64-linux-gnu/libc-2.22.so)
==13144== by 0x40096F: mkobj (common.c:102)
==13144== by 0x400A16: mkobjargv (common.c:124)
==13144== by 0x400B3A: alloc_insert_free (hash-map-str.c:53)
==13144== by 0x4010B8: main (hash-map-str.c:157)
==13144==

Example program is attached.

libcds-examples.tar.gz

Please do not hesitate to contact me [email protected] if you need more information.

/rocco

Currently, we just get the DS size and rely on the single operator to iterate the entire DS.
But it will be inefficient if the operator cannot access the item in O(1) time.

This issue opens the window for performance optimization.
And the enhanced operators are listed below:

Vector:
next().

LinkedList:
next().

BinaryTree:
RedBlackTree:
inorder_successor().
inorder_predecessor().
preorder_successor().
preorder_predecessor().
postorder_successor().
postorder_predecesor().

We shall use set_target_properties to setup SOVERSION.

Vector:
sort()

List:
sort()

Many programs use pkgconfig to manage their dependencies. We shall also provide it for better user experience.