Documentation for uthash is available at:
troydhanson / uthash Goto Github PK
View Code? Open in Web Editor NEWC macros for hash tables and more
License: Other
C macros for hash tables and more
License: Other
Documentation for uthash is available at:
Self explanatory really.
uthash already supports custom allocators, maybe utarray should as well.
Hello.
While working on #85, we discussed the necessity of ptrdiff_t. In general, it's advised to use it instead of a pointer in pointer arithmetic if a value can ever become negative.
In uthash, ptrdiff_t type is used exclusively for calculating the distance between the beginning of the hashed structure and the location of the hash handle inside the structure.
There are 2 instances in the code where the pointers are subtracted. Any addition that is happening is between two positive values. In both instances where the subtraction is done, the subtraction is always between &PTR->HH
and PTR
, which guarantees that the result is not negative.
The question would be - what to replace it with, though. There is no universally guaranteed C type that is precisely the size of the pointer. long
has been often used, but I bet there are targets where this is not the case (C standard does not require that). I would replace it with void*
, but I'm not sure that all C compilers support pointer arithmetic between two void*
.
The clang reports "use after free" when analyzing the following piece of code:
#include <stdio.h> /* gets */
#include <stdlib.h> /* atoi, malloc */
#include <string.h> /* strcpy */
#include "uthash.h"
struct my_struct {
int id; /* key */
char name[10];
UT_hash_handle hh; /* makes this structure hashable */
};
struct my_struct *users = NULL;
void add_user(int user_id, char *name) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */
if (s==NULL) {
s = (struct my_struct*)malloc(sizeof(struct my_struct));
s->id = user_id;
HASH_ADD_INT( users, id, s ); /* id: name of key field */
}
strcpy(s->name, name);
}
void delete_all() {
struct my_struct *current_user, *tmp;
HASH_ITER(hh, users, current_user, tmp) {
HASH_DEL(users, current_user); /* delete it (users advances to next) */
free(current_user); /* free it */
}
}
int main(int argc, char *argv[]) {
char in[10];
int id=1, running=1;
struct my_struct *s;
unsigned num_users;
add_user(1, "111111");
add_user(2, "222222222");
add_user(3, "3");
delete_all(); /* free any structures */
return 0;
}
Clang report:
uthash.c:30:5: warning: Use of memory after it is freed
HASH_DEL(users, current_user); /* delete it (users advances to next) */
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:421:5: note: expanded from macro 'HASH_DEL'
HASH_DELETE(hh,head,delptr)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:369:5: note: expanded from macro 'HASH_DELETE'
HASH_DELETE_HH(hh, head, &(delptr)->hh)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:376:17: note: expanded from macro 'HASH_DELETE_HH'
uthash_free((head)->hh.tbl->buckets, \
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:89:34: note: expanded from macro 'uthash_free'
#define uthash_free(ptr,sz) free(ptr) /* free fcn */
^
uthash.c:30:5: warning: Use of memory after it is freed
HASH_DEL(users, current_user); /* delete it (users advances to next) */
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:421:5: note: expanded from macro 'HASH_DEL'
HASH_DELETE(hh,head,delptr)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:369:5: note: expanded from macro 'HASH_DELETE'
HASH_DELETE_HH(hh, head, &(delptr)->hh)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./uthash.h:382:23: note: expanded from macro 'HASH_DELETE_HH'
if (_hd_hh_del == (head)->hh.tbl->tail) { \
^~~~~~~~~~~~~~
2 warnings generated.
Should HASH_REPLACE_PTR have a "replaced" field at the end?
configure: error: Could not find HASH_ITER
HI,
I'm packaging it into Fedora as other software needs it.
Can you provide me a 1.9.8 tarball on sf.net? I know github support tarball download, but it's difficult for packagers because we have to follow the guidelines.
Easier life ,please~
Thanks.
Hello,
Why Performance is Bad? @troydhanson
Array PHP
vs UtHash C
$ time php test.php
<?php
$list=array();
for($i=0; $i<=9999999;$i++)
{
$list[$i]=$i*$i;
}
?>
real 0m0.335s
user 0m0.244s
sys 0m0.088s
$ cc -I../src -g -Wall -o custom custom.c
$ time ./custom
#include "uthash.h"
#include <stdlib.h>
#include <stdio.h>
typedef struct example_user_t {
int id;
int cookie;
UT_hash_handle hh;
} example_user_t;
int main(int argc,char *argv[])
{
int i;
example_user_t *user, *users=NULL;
for(i=0; i<=9999999; i++) {
user = (example_user_t*)malloc(sizeof(example_user_t));
if (user == NULL) {
exit(-1);
}
user->id = i;
user->cookie = i*i;
HASH_ADD_INT(users,id,user);
}
return 0;
}
real 0m4.529s
user 0m4.288s
sys 0m0.240s
Hello,
Is there plan to releasing a new release? It seems many important fixes was done since last one.
Thank you!
Hello,
How can get List of array?
#include <stdio.h>
#include "utarray.h"
typedef struct example_user_t {
int id;
int cookie;
} example_user_t;
static UT_icd icd = {
.sz = sizeof(example_user_t),
.init = NULL,
.copy = NULL,
.dtor = NULL
};
int main()
{
UT_array users;
utarray_init(&users, &icd);
for (int i=1; i<=100000000; i++)
{
example_user_t user = {i, i*i};
utarray_push_back(&users, &user);
}
printf("%d\n",users.i);
for (int i=1; i<=users.i;i++)
{
}
}
also how can remove a index from array? example _remove(&users,5);
Braces are missing around the for loop within the HASH_FNV macro. It will still work, but isn't quite correct. The fix should be trivial.
Here a suggestion for the inline documentation of uthash.h
without any changes to the code in order to make doxygen recognize the documentation text. This is - at least for me - helpful to better understand the code in the documented version.
Thanks,
J.
Index: uthash.h
===================================================================
--- uthash.h (revision 8)
+++ uthash.h (revision 9)
@@ -79,13 +79,13 @@
#endif
#ifndef uthash_fatal
-#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */
+#define uthash_fatal(msg) exit(-1) /**< fatal error (out of memory,etc) */
#endif
#ifndef uthash_malloc
-#define uthash_malloc(sz) malloc(sz) /* malloc fcn */
+#define uthash_malloc(sz) malloc(sz) /**< malloc fcn */
#endif
#ifndef uthash_free
-#define uthash_free(ptr,sz) free(ptr) /* free fcn */
+#define uthash_free(ptr,sz) free(ptr) /**< free fcn */
#endif
#ifndef uthash_strlen
#define uthash_strlen(s) strlen(s)
@@ -95,20 +95,20 @@
#endif
#ifndef uthash_noexpand_fyi
-#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */
+#define uthash_noexpand_fyi(tbl) /**< can be defined to log noexpand */
#endif
#ifndef uthash_expand_fyi
-#define uthash_expand_fyi(tbl) /* can be defined to log expands */
+#define uthash_expand_fyi(tbl) /**< can be defined to log expands */
#endif
/* initial number of buckets */
-#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */
-#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */
-#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */
+#define HASH_INITIAL_NUM_BUCKETS 32U /**< initial number of buckets */
+#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /**< lg2 of initial number of buckets */
+#define HASH_BKT_CAPACITY_THRESH 10U /**< expand when bucket count reaches */
-/* calculate the element whose hash handle address is hhp */
+/** calculate the element whose hash handle address is hhp */
#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
-/* calculate the hash handle from element address elp */
+/** calculate the hash handle from element address elp */
#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho)))
#define HASH_VALUE(keyptr,keylen,hashv) \
@@ -322,7 +322,7 @@
bkt = ((hashv) & ((num_bkts) - 1U)); \
} while (0)
-/* delete "delptr" from the hash table.
+/** delete "delptr" from the hash table.
* "the usual" patch-up process for the app-order doubly-linked-list.
* The use of _hd_hh_del below deserves special explanation.
* These used to be expressed using (delptr) but that led to a bug
@@ -473,7 +473,7 @@
#define HASH_FCN HASH_JEN
#endif
-/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
+/** The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
#define HASH_BER(key,keylen,hashv) \
do { \
unsigned _hb_keylen=(unsigned)keylen; \
@@ -485,7 +485,7 @@
} while (0)
-/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
+/** SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
* http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
#define HASH_SAX(key,keylen,hashv) \
do { \
@@ -496,7 +496,7 @@
hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
} \
} while (0)
-/* FNV-1a variation */
+/** FNV-1a variation */
#define HASH_FNV(key,keylen,hashv) \
do { \
unsigned _fn_i; \
@@ -732,7 +732,7 @@
} \
} while (0)
-/* add an item to a bucket */
+/** add an item to a bucket */
#define HASH_ADD_TO_BKT(head,addhh) \
do { \
head.count++; \
@@ -759,7 +759,7 @@
hh_del->hh_next->hh_prev = hh_del->hh_prev; \
}
-/* Bucket expansion has the effect of doubling the number of buckets
+/** Bucket expansion has the effect of doubling the number of buckets
* and redistributing the items into the new buckets. Ideally the
* items will distribute more or less evenly into the new buckets
* (the extent to which this is true is a measure of the quality of
@@ -837,7 +837,7 @@
} while (0)
-/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
+/** This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
/* Note that HASH_SORT assumes the hash handle name to be hh.
* HASH_SRT was added to allow the hash handle name to be passed in. */
#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
@@ -928,7 +928,7 @@
} \
} while (0)
-/* This function selects items from one hash into another hash.
+/** This function selects items from one hash into another hash.
* The end result is that the selected items have dual presence
* in both hashes. There is no copy of the items made; rather
* they are added into the new hash through a secondary hash
@@ -999,7 +999,7 @@
(el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
#endif
-/* obtain a count of items in the hash */
+/** obtain a count of items in the hash */
#define HASH_COUNT(head) HASH_CNT(hh,head)
#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
@@ -1034,16 +1034,16 @@
struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
- /* in an ideal situation (all buckets used equally), no bucket would have
+ /** in an ideal situation (all buckets used equally), no bucket would have
* more than ceil(#items/#buckets) items. that's the ideal chain length. */
unsigned ideal_chain_maxlen;
- /* nonideal_items is the number of items in the hash whose chain position
+ /** nonideal_items is the number of items in the hash whose chain position
* exceeds the ideal chain maxlen. these items pay the penalty for an uneven
* hash distribution; reaching them in a chain traversal takes >ideal steps */
unsigned nonideal_items;
- /* ineffective expands occur when a bucket doubling was performed, but
+ /** ineffective expands occur when a bucket doubling was performed, but
* afterward, more than half the items in the hash had nonideal chain
* positions. If this happens on two consecutive expansions we inhibit any
* further expansion, as it's not helping; this happens when the hash
@@ -1062,13 +1062,13 @@
typedef struct UT_hash_handle {
struct UT_hash_table *tbl;
- void *prev; /* prev element in app order */
- void *next; /* next element in app order */
- struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
- struct UT_hash_handle *hh_next; /* next hh in bucket order */
- void *key; /* ptr to enclosing struct's key */
- unsigned keylen; /* enclosing struct's key len */
- unsigned hashv; /* result of hash-fcn(key) */
+ void *prev; /**< prev element in app order */
+ void *next; /**< next element in app order */
+ struct UT_hash_handle *hh_prev; /**< previous hh in bucket order */
+ struct UT_hash_handle *hh_next; /**< next hh in bucket order */
+ void *key; /**< ptr to enclosing struct's key */
+ unsigned keylen; /**< enclosing struct's key len */
+ unsigned hashv; /**< result of hash-fcn(key) */
} UT_hash_handle;
#endif /* UTHASH_H */
Hello masters,
Sometimes we need to change the sorting logic at run-time, however, the HASH_SORT
doesn't offer any way to do that, unless using global variables (argh...). So, what do you think about adding a HASH_SORT2
macro allowing the programmer to send a closure in a third parameter? We could reuse the code, moving all HASH_SORT
's implementation into HASH_SORT2
, so the HASH_SORT
would change to something like #define HASH_SORT(head,cmpfcn) HASH_SORT2(head,cmpfcn,NULL)
, and finally we would able to do something like this pseudo code below:
static int cmp_func(void *cls, void *a, void *b) {
struct my_order *order = cls;
struct my_type *ta = a;
struct my_type *tb = b;
switch (order->by) {
case name_asc: return strcmp(ta->name, tb->name);
case name_desc: return -strcmp(ta->name, tb->name);
case value_asc: return strcmp(ta->value, tb->value);
case value_desc: return -strcmp(ta->value, tb->value);
}
}
...
struct my_order *order;
HASH_SORT2(hash, &cmp_func, order); // to use "order by"
Hi!
I'm using UThash in a scientific environment where we would need to store a huge number of elements in the hash table.
I have tested to insert 8.589.934.592 elements (2^33), and I got a SEGFAULT when inserting the 2.067.785.503th element, very close to the INT_MAX value (2^31 = 2.147.483.648).
The gdb core analysis shows this information:
(gdb) print *sc
$2 = {cubekey = 2067785503, particles = 0x4d09ed9e70, nparticles = 0, hh = {tbl = 0x1fd2890, prev = 0x4d09ed9d70, next = 0x0, hh_prev = 0x0, hh_next = 0x4af1685368, key = 0x4d09ed9e10, keylen = 8, hashv = 3935987613}, patch_id = 18446744073709551615}
Don't know if next and hh_prev pointers equal to NULL says something to you...
Could be any way to increase the limit of elements per UThash table?
I have seen several unsigned and uint32_t declarations in uthash.h, but I'm not able to understand and modify the code.
Could I increase the HASH_BKT_CAPACITY_THRESH value as a solution to avoid huge number of buckets?
Any help will be very appreciated!
Thanks a lot in advance
Best Regards
Fer
Utlist.html says: For all types of lists, prepending elements and deleting elements are constant-time operations.
For singly linked lists, the code iterates to the node, so it's O(n).
Since none of string.h, stddef.h nor stdlib.h are available in a kernel module, is there a way for this library to be used in one? If "yes", how?
EDIT: BTW, I saw https://github.com/dbellavista/edfomai/blob/master/datastructures/uthash.h which kind of does what I want, but it's integrated with rtdm_driver.h. I could clean that and use it on my project, but it would be nice if you could merge their changes so your project can compile on both userspace and kernelspace projects :)
Hi,
After checking files, I found that the LICENSE file has 755 perms.
Please fix it, thanks.
Dose someone have the same problem? Is there any bypass I can use?
many thanks
Hello
first of all thank you very much for your hard work on such a good library
i have a c code it compiles and runs fine on ubuntu x64 machine but for somereason when i hit the call of one of your macros it gives me segmantation fault , (i am hoping that i am wrong for it is not compatible with mipsel devices and only my code is wrong ) can you please give this a snippet a look tell me what i am missing
thanks alot
MK
when i call this below function
it gives me segmantation fault only on mipsel devices / openwrt
int add_nas_device_to_table(reclient *device) {
if (find_nas_device_by_deviceid(device->nas_id) == NULL) {
HASH_ADD(hh, nasdevices, nas_id, strlen(device->nas_id), device);
return 0;
}
else {
return -1;
}
}
Hi,
Am using the uthash. Wanted to know what is the maximum number of items that can be added to uthash.
The structure am using as
struct my_struct {
int id; /* key */
emp_data_t emp_data; //a structure of 920 bytes of memory
UT_hash_handle hh;
};
When am adding it goes around 42630 records ( am starting the id from 1 ) then the memory allocation fails .Is there any way to overcome from it.
I am using the 2.0.2 release, my system: openSUSE Leap 42.2 (64bit) gcc 4.8.5.
When running the tests test88 fails for HASH_FUNCTION=HASH_BER
and HASH_FUNCTION=HASH_SFH
.
uthash/tests% ./all_funcs
[...]
perl ./do_tests
test88 failed
90 tests conducted, 1 failed.
Makefile:111: recipe for target 'run_tests' failed
make: *** [run_tests] Error 1
I have attached the .out
files.
In the sources you have : #define UTHASH_VERSION 1.9.9
Any special reason for it not being a string? Since it is not a valid number, a string would make things easier. In my code I have a macro available so this is not an issue.
...
LOG(LOG_INFO, "USING uthash version " STR(UTHASH_VERSION));
Thanks.
There are few issues with libglvnd (using uthash) package as reported by rpmlint.
libglvnd.armv7hl: W: shared-lib-calls-exit /usr/lib/libGLX.so.0.0.0 exit@GLIBC_2.4
libglvnd.i686: W: shared-lib-calls-exit /usr/lib/libGLX.so.0.0.0 exit@GLIBC_2.0
libglvnd.x86_64: W: shared-lib-calls-exit /usr/lib64/libGLX.so.0.0.0 exit@GLIBC_2.2.5
This is caused by the (bundled) utash library that handle fatal errors such as:
#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */
rpmlint notice about shared-lib-calls-exit:
This library package calls exit() or _exit(), probably in a non-fork()
context. Doing so from a library is strongly discouraged - when a library
function calls exit(), it prevents the calling program from handling the
error, reporting it to the user, closing files properly, and cleaning up any
state that the program has. It is preferred for the library to return an
actual error code and let the calling program decide how to handle the
situation.
Is this notice relevant for uthash ?
Is there a way to improve error handling here?
Thx
I ran into test failures for test83 and test84. This happens on a amd64 machine using gcc 4.8.2 or clang 3.3, but not on a x86 machine running gcc 4.8.1. The outputs below are from the amd64 machine (same output for gcc and clang).
test83.out:
items in hash: 1, overhead: 632
items in hash: 2, overhead: 688
items in hash: 3, overhead: 744
items in hash: 4, overhead: 800
items in hash: 5, overhead: 856
items in hash: 6, overhead: 912
items in hash: 7, overhead: 968
items in hash: 8, overhead: 1024
items in hash: 9, overhead: 1080
items in hash: 10, overhead: 1136
items in hash: 11, overhead: 1192
items in hash: 12, overhead: 1248
items in hash: 13, overhead: 1304
items in hash: 14, overhead: 1360
items in hash: 15, overhead: 1416
items in hash: 16, overhead: 1472
items in hash: 17, overhead: 1528
items in hash: 18, overhead: 1584
items in hash: 19, overhead: 1640
items in hash: 20, overhead: 1696
items in hash: 21, overhead: 1752
items in hash: 22, overhead: 1808
items in hash: 23, overhead: 1864
items in hash: 24, overhead: 1920
items in hash: 25, overhead: 1976
items in hash: 26, overhead: 2032
items in hash: 27, overhead: 2088
items in hash: 28, overhead: 2144
items in hash: 29, overhead: 2200
items in hash: 30, overhead: 2256
items in hash: 31, overhead: 2312
items in hash: 32, overhead: 2368
items in hash: 33, overhead: 2424
items in hash: 34, overhead: 2480
items in hash: 35, overhead: 2536
items in hash: 36, overhead: 2592
items in hash: 37, overhead: 2648
items in hash: 38, overhead: 2704
items in hash: 39, overhead: 2760
items in hash: 40, overhead: 2816
items in hash: 41, overhead: 2872
items in hash: 42, overhead: 2928
items in hash: 43, overhead: 2984
items in hash: 44, overhead: 3040
items in hash: 45, overhead: 3096
items in hash: 46, overhead: 3152
items in hash: 47, overhead: 3208
items in hash: 48, overhead: 3264
items in hash: 49, overhead: 3320
items in hash: 50, overhead: 3376
items in hash: 51, overhead: 3432
test84.out:
items in hash: 1, overhead: 8840
items in hash: 2, overhead: 8896
items in hash: 3, overhead: 8952
items in hash: 4, overhead: 9008
items in hash: 5, overhead: 9064
items in hash: 6, overhead: 9120
items in hash: 7, overhead: 9176
items in hash: 8, overhead: 9232
items in hash: 9, overhead: 9288
items in hash: 10, overhead: 9344
items in hash: 11, overhead: 9400
items in hash: 12, overhead: 9456
items in hash: 13, overhead: 9512
items in hash: 14, overhead: 9568
items in hash: 15, overhead: 9624
items in hash: 16, overhead: 9680
items in hash: 17, overhead: 9736
items in hash: 18, overhead: 9792
items in hash: 19, overhead: 9848
items in hash: 20, overhead: 9904
items in hash: 21, overhead: 9960
items in hash: 22, overhead: 10016
items in hash: 23, overhead: 10072
items in hash: 24, overhead: 10128
items in hash: 25, overhead: 10184
items in hash: 26, overhead: 10240
items in hash: 27, overhead: 10296
items in hash: 28, overhead: 10352
items in hash: 29, overhead: 10408
items in hash: 30, overhead: 10464
items in hash: 31, overhead: 10520
items in hash: 32, overhead: 10576
items in hash: 33, overhead: 10632
items in hash: 34, overhead: 10688
items in hash: 35, overhead: 10744
items in hash: 36, overhead: 10800
items in hash: 37, overhead: 10856
items in hash: 38, overhead: 10912
items in hash: 39, overhead: 10968
items in hash: 40, overhead: 11024
items in hash: 41, overhead: 11080
items in hash: 42, overhead: 11136
items in hash: 43, overhead: 11192
items in hash: 44, overhead: 11248
items in hash: 45, overhead: 11304
items in hash: 46, overhead: 11360
items in hash: 47, overhead: 11416
items in hash: 48, overhead: 11472
items in hash: 49, overhead: 11528
items in hash: 50, overhead: 11584
items in hash: 51, overhead: 11640
typedef struct
{
int id;
UT_hash_handle hh;
}user;
int hash_test()
{
user *u=NULL;
user *users=NULL;
int i=0;
for(i=0;i<100;i++)
{
u=(user *)malloc(sizeof(user));
u->id =i ;
HASH_ADD_INT(users,id,u);
}
u=(user *)malloc(sizeof(user));
memset(u,0,sizeof(user));
u->id=99;
printf("befor del:%d\n",HASH_COUNT(users));// 100
HASH_DEL(users,u);
printf("after del:%d\n",HASH_COUNT(users));// 0
}
Hi!
I'm using uthash and utarray libs in a scientific application.
When trying to use utarray_next(UT_array *a,void *e)
I got "โssize_tโ undeclared" error.
I fixed it with this change:
@@ -37,6 +37,7 @@
#include <stddef.h> /* size_t /
#include <string.h> / memset, etc /
#include <stdlib.h> / exit /
+#include <sys/types.h> / ssize_t */
#define oom() exit(-1)
Was it a bug?? am I doing something wrong??
Thanks a lot
Regards
The convenience macros HASH_FIND_STR, HASH_ADD_STR and HASH_REPLACE_STR call uthash_strlen more frequently than necessary. I would recommend to cache this key length and pass it to HASH_FIND, HASH_ADD and HASH_REPLACE, respectively.
I am using uthash 1.9.4 in the Hamlib project to sort and display a list. I've recently tried cppcheck on the Hamlib source and it reports that _ha_bkt is uninitialized. I see this variable is in the HASH_ADD_KEYPTR macro definition and appears to be intended to be used as an index but is never initialized.
Is this a problem?
I saw that seemly SSE4.2 CRC is the fastest hash function for hash tables, sometimes having speeds 10 times faster than FNV for example.
Thus I was wondering if uthash can use it somehow.
Hello masters,
Thanks for this awesome library! It worked like a charm for my ARMv7 and finally I can use an efficient C hash table in my Android (tested on version 5 and 6) application. My C structure is just a table saving function pointers (providing aliases to the FFI library) that can be found by a string key, so uthash was the perfect choice for implementing that.
So, could you add the Android
item in the uthash's platforms list? If you prefer I can send a step-by-step text showing how to integrate the uthash sample to the official Google's hello-jni
example.
Thank you! ๐
After commit 2eeb5f4 macro utarray_eltidx()
produces warning
/.../utarray.h:216:117: warning: signed and unsigned type in conditional expression [-Wsign-compare]
#define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(size_t)(a)->icd.sz) : -1)
^
Hello, me again!
I have pulled the latest utlist and uthash after issue #111 was resolved, and now I have more warnings to report.
lib/utils/utlist.h:95:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _SV(elt,list)
^
lib/utils/utlist.h:96:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _NEXT(elt,list,next) ((elt)->next)
^
lib/utils/utlist.h:97:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
^
lib/utils/utlist.h:99:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
^
lib/utils/utlist.h:100:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _RS(list)
^
lib/utils/utlist.h:101:9: warning: macro name is a reserved identifier [-Wreserved-id-macro]
#define _CASTASGN(a,b) (a)=(b)
^
6 warnings generated.
The problem is that identifiers with a leading underscore are marked reserved by the language specification.
I get a compile error compiling a minimal test programme:
$ ccomp -o utc.o -c utc.c
utc.c:19: warning: implicit declaration of function '__typeof' is invalid in C99 [-Wimplicit-function-declaration]
utc.c:19: error: called object type 'int' is neither a function nor function pointer
Where utc.c
is:
#include <stdio.h> /* gets */
#include <stdlib.h> /* atoi, malloc */
#include <string.h> /* strcpy */
#include "uthash.h"
struct my_struct {
int id; /* key */
char name[10];
UT_hash_handle hh; /* makes this structure hashable */
};
struct my_struct *users = NULL;
void add_user(int user_id, char *name) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */
}
Compiling as C in Visual Studio breaks. NO_DECLTYPE
is defined, but several "functions" are not redefined to use VS2008 versions. Many of those "functions" still attempt to use LDECLTYPE
, which is defined as char*
. This leads to compile errors for assigning a struct*
to a char*
or trying to access (char*)->next
.
Short example:
#include <stdlib.h>
#include "utlist.h"
typedef struct mystruct {
struct mystruct *next;
int someValue;
} mystruct;
void testutlist()
{
mystruct *head = NULL;
mystruct *elem1 = (mystruct*)malloc(sizeof(mystruct));
mystruct *elem2 = (mystruct*)malloc(sizeof(mystruct));
LL_APPEND(head, elem1);
LL_PREPEND_ELEM(head, elem1, elem2);
}
Two compile errors on the LL_PREPEND_ELEM line:
1>c:\...\source.c(16): warning C4133: '=' : incompatible types - from 'mystruct *' to 'char *'
1>c:\...\source.c(16): error C2223: left of '->next' must point to struct/union
are actually due to utlist.h lines 493 & 494, because _tmp
was declared as a char*
.
Greetings.
I've been using uthash for years but recently it seems I found a bug in it.
Bug is in pointer keys with sorting function, i.e. in HASH_ADD_KEYPTR_INORDER. And it causes segfault.
It seems strange, but it really looks like a bug. I read documentation some times and I guess I used it properly, but it failed.
I made a small test case to show the bug.
I also sketched a patch (only for GCC, since I don't have other compilers at hand, but it's easily extendable for other declarations).
I uploaded the test case and patch here:
https://github.com/IronBug/uthash_test
Sincerely, Yana A. Kireyonok aka Iron Bug
I recently switched to uthash. Whereas my previous C code kept Cppcheck 1.67 silent it now reports errors, warnings and style issues. See file test.c for an example.
#include "uthash.h"
struct my_struct {
int id; /* we'll use this field as the key */
char name[10];
UT_hash_handle hh; /* makes this structure hashable */
};
struct my_struct *users = NULL;
void add_user(struct my_struct *s) {
HASH_ADD_INT( users, id, s );
}
struct my_struct *find_user(int user_id) {
struct my_struct *s;
HASH_FIND_INT( users, &user_id, s );
return s;
}
void delete_user(struct my_struct *user) {
HASH_DEL( users, user);
}
yields
<?xml version="1.0" encoding="UTF-8"?>
<results version="2">
<cppcheck version="1.67"/>
<errors>
<error id="redundantAssignInSwitch" severity="warning" msg="Variable &#039;hashv&#039; is reassigned a value before the old one has been used. &#039;break;&#039; missing?" verbose="Variable &#039;hashv&#039; is reassigned a value before the old one has been used. &#039;break;&#039; missing?">
<location file="test.c" line="12"/>
<location file="test.c" line="12"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_hf_bkt&#039; can be reduced." verbose="The scope of the variable &#039;_hf_bkt&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="18"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_hf_hashv&#039; can be reduced." verbose="The scope of the variable &#039;_hf_hashv&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="18"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_hd_bkt&#039; can be reduced." verbose="The scope of the variable &#039;_hd_bkt&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="23"/>
</error>
<error id="invalidPrintfArgType_sint" severity="warning" msg="%d in format string (no. 1) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;." verbose="%d in format string (no. 1) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;.">
<location file="test.c" line="12"/>
</error>
<error id="invalidPrintfArgType_sint" severity="warning" msg="%d in format string (no. 2) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;." verbose="%d in format string (no. 2) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;.">
<location file="test.c" line="12"/>
</error>
<error id="invalidPrintfArgType_sint" severity="warning" msg="%d in format string (no. 1) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;." verbose="%d in format string (no. 1) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;.">
<location file="test.c" line="23"/>
</error>
<error id="invalidPrintfArgType_sint" severity="warning" msg="%d in format string (no. 2) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;." verbose="%d in format string (no. 2) requires &#039;int&#039; but the argument type is &#039;unsigned int&#039;.">
<location file="test.c" line="23"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_bkt_i&#039; can be reduced." verbose="The scope of the variable &#039;_bkt_i&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="12"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_count&#039; can be reduced." verbose="The scope of the variable &#039;_count&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="12"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_bkt_count&#039; can be reduced." verbose="The scope of the variable &#039;_bkt_count&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="12"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_prev&#039; can be reduced." verbose="The scope of the variable &#039;_prev&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="12"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_bkt_i&#039; can be reduced." verbose="The scope of the variable &#039;_bkt_i&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="23"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_count&#039; can be reduced." verbose="The scope of the variable &#039;_count&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="23"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_bkt_count&#039; can be reduced." verbose="The scope of the variable &#039;_bkt_count&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="23"/>
</error>
<error id="variableScope" severity="style" msg="The scope of the variable &#039;_prev&#039; can be reduced." verbose="The scope of the variable &#039;_prev&#039; can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for &#039;i&#039; can be reduced: void f(int x) { int i = 0; if (x) { // it&#039;s safe to move &#039;int i = 0;&#039; here for (int n = 0; n &lt; 10; ++n) { // it is possible but not safe to move &#039;int i = 0;&#039; here do_something(&amp;i); } } } When you see this message it is always safe to reduce the variable scope 1 level.">
<location file="test.c" line="23"/>
</error>
<error id="unassignedVariable" severity="style" msg="Variable &#039;_ha_bkt&#039; is not assigned a value." verbose="Variable &#039;_ha_bkt&#039; is not assigned a value.">
<location file="test.c" line="12"/>
</error>
<error id="uninitvar" severity="error" msg="Uninitialized variable: _ha_bkt" verbose="Uninitialized variable: _ha_bkt">
<location file="test.c" line="12"/>
</error>
</errors>
</results>
Some of the style issues are already addressed by #39.
Yes, we did use HASH_ADD_KEYPTR, following the examples exactly.
Hi, I didn't do C programming for quite a while, please excuse any beginner's mistakes :) I'm building a ruby module to implement a few graph algorithms so that they run faster than they would in native ruby.
In general the node type looks like this:
struct gNode {
long id;
char *name;
struct gLink *links;
UT_hash_handle hh;
};
As you can see, this is also the data structure I would like to use uthash on. Since the key is a long
, I am using the general macros to add nodes like this:
HASH_ADD(hh, data->nodes, id, sizeof(new_node->id), new_node);
I add many (> 250,000) nodes to the hash and then I iterate it like this:
for(node = data->nodes; node != NULL; node = node->hh.next) {
printf("item %ld: name %s\n", node->id, node->name);
}
This prints out the vast majority of the nodes nicely. However, once in a while (in about 5500 of > 250,000 cases) it prints a line like
item 0: name 1
where the 1 is sometimes another small integer or some string. I'm reasonably certain that I'm not sending this data via HASH_ADD.
Do you have an idea why this might be happening? Thanks!
I would like to know if there is any possibility to use a long int
or long long int
as a key in uthash. I made some tests using keys like 4498690746, but when I retrieve the value, it is 203723450. Thanks in advance.
I'm an embedded developer on a university satellite project, and plan to fly uthash as part of our core data structures library. We're currently using 2.0.1 and have not had any issues, but I was wondering if there were "stable" versions beyond just what we find here on GitHub. Sort of like how Ubuntu has LTS and normal releases, I'm trying to see if this library has an LTS version. No need for guarantees or support, just stability.
Hello!
Is it possible to serialize hashmap to string? I need it to send app state to other thread and unserialize there.
Hi,
According to http://www.isthe.com/chongo/tech/comp/fnv/ FNV-1a alternate algorithm should be used instead of the FNV-1 hash where possible. But uthash implements FNV-1 by default. Would it be possible to have FNV-1a instead?
I've found the use of ssize_t in utarray.h
, but it is not defined in C99. Microsoft Windows compiler does not recognize this type, which leads to many build failure. Can we replace ssize_t
by something else? Thanks!
Hi,
Building RPM has an error, this only happen in the pure clean buildroot, if I built RPM on system, no problem here:
Can you tell me what these two exactly is?
Building an application using uthash with Clang 3.8 and -Wpadded
yields the following diagnostic:
./lib/utils/uthash.h:1056:27: warning: padding struct 'struct UT_hash_table' with 4 bytes to align 'tail' [-Wpadded]
struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
^
This is because it is a pointer value but it is located after a number of smaller variables whose total alignment does not equal that of the pointer.
Rearranging the structure, from:
typedef struct UT_hash_table {
UT_hash_bucket *buckets;
unsigned num_buckets, log2_num_buckets;
unsigned num_items;
struct UT_hash_handle *tail;
ptrdiff_t hho;
unsigned ideal_chain_maxlen;
unsigned nonideal_items;
unsigned ineff_expands, noexpand;
uint32_t signature;
#ifdef HASH_BLOOM
uint32_t bloom_sig;
uint8_t *bloom_bv;
uint8_t bloom_nbits;
#endif
} UT_hash_table;
To:
typedef struct UT_hash_table {
struct UT_hash_handle *tail;
UT_hash_bucket *buckets;
ptrdiff_t hho;
unsigned num_buckets, log2_num_buckets;
unsigned num_items;
unsigned ideal_chain_maxlen;
unsigned nonideal_items;
unsigned ineff_expands, noexpand;
uint32_t signature;
#ifdef HASH_BLOOM
uint32_t bloom_sig;
uint8_t *bloom_bv;
uint8_t bloom_nbits;
#endif
} UT_hash_table;
Reduces its size from 64 bytes:
(gdb) print /s sizeof(struct UT_hash_table)
$1 = 64
To 56 bytes:
(gdb) print /s sizeof(struct UT_hash_table)
$1 = 56
... and eliminates the diagnostic, making uthash build cleaner under common warnings, while saving a small amount of memory.
For more information, see here.
The following C99 code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utlist.h"
struct entry
{
struct entry *prev;
struct entry *next;
char text[32];
};
struct entry *list = NULL;
static struct entry * __attribute__((malloc))
new_list_item(const char *const restrict text)
{
struct entry *item = calloc(1, sizeof *item);
if (! item)
return NULL;
(void) snprintf(item->text, sizeof item->text, "%s", text);
DL_APPEND(list, item);
return item;
}
int
main(void)
{
if (! new_list_item("foo"))
return EXIT_FAILURE;
if (! new_list_item("bar"))
return EXIT_FAILURE;
if (! new_list_item("baz"))
return EXIT_FAILURE;
struct entry *item, *tmp;
DL_FOREACH_SAFE(list, item, tmp)
{
DL_DELETE(list, item);
free(item);
}
return EXIT_SUCCESS;
}
Results in the following Clang 3.8 static analyzer output:
$ /usr/bin/scan-build-3.8 -maxloop 32 \
/usr/share/clang/scan-build-3.8/libexec/ccc-analyzer \
-std=c99 -Wall -Wextra -Wpedantic test.c -o test
scan-build: Using '/usr/lib/llvm-3.8/bin/clang' for static analysis
test.c:45:3: warning: Access to field 'prev' results in a dereference
of a null pointer (loaded from variable 'list')
DL_DELETE(list, item);
^ ~~~~
./utlist.h:590:33: note: expanded from macro 'DL_DELETE'
#define DL_DELETE(head, del) DL_DELETE2(head, del, prev, next)
^ ~~~~
./utlist.h:450:15: note: expanded from macro 'DL_DELETE2'
head->prev = del->prev; \
~~~~ ^
1 warning generated.
scan-build: 1 bug found.
The code does not crash, and Valgrind memcheck does not complain about it, so it is probably a false positive, but you may want to look into it anyway. Perhaps the macros could be rewritten slightly to avoid the warning.
The following:
struct entry *item, *tmp;
DL_FOREACH_SAFE(list, item, tmp)
{
if (! list)
break;
DL_DELETE(list, item);
free(item);
}
Also silences the warning.
Hi,
How do I create a case insensitive string key ,so that while searching it will not take the case into account.
example
Suppose I have added the key as America. In my search if I will put ameriCA also it can be found by the FIND_STR .
Thanks
Sar
Basically I'd like to either explicitly support (and unit-test) cases like the following, or explicitly document that these cases are not supported. But if we do the latter, we'll be explicitly "unsupporting" some code that's already out there in the wild (see #92).
#include "uthash.h"
#undef uthash_fatal
#undef uthash_malloc
void *uthash_malloc(size_t sz) {
static int count = 0;
if (++count == FAIL_ON_THIS_ALLOCATION) return NULL;
return malloc(sz);
}
struct Table {
int hashkey;
UT_hash_handle hh;
};
bool addItemOrFail(struct Table *t, int newValue) {
struct Table *item = malloc(sizeof *item);
item->hashkey = 42;
#define uthash_fatal(msg) return false
HASH_ADD_INT(table, hashkey, item);
#undef uthash_fatal
return true;
}
int main() {
struct Table *t = NULL;
addItemOrFail(t, 41); // Suppose this fails.
addItemOrFail(t, 42); // Is this undefined behavior, or does it Just Work?
addItemOrFail(t, 43);
HASH_CLEAR(hh, t); // Is this undefined behavior, or does it Just Work?
}
For example, I want to download the Version 1.9.8 (2013-03-10)
, but i failed to find the URL of this version, it just led me to the master
branch of this repo.
Why not set a new tag when a release version is out?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.