diff options
| -rw-r--r-- | json_object.c | 104 | ||||
| -rw-r--r-- | json_object.h | 46 | ||||
| -rw-r--r-- | json_object_private.h | 10 | ||||
| -rw-r--r-- | linkhash.c | 73 | ||||
| -rw-r--r-- | linkhash.h | 109 |
5 files changed, 251 insertions, 91 deletions
diff --git a/json_object.c b/json_object.c index e6bd870..6ec67a0 100644 --- a/json_object.c +++ b/json_object.c @@ -69,7 +69,7 @@ static struct lh_table *json_object_table; static void json_object_init(void) __attribute__ ((constructor)); static void json_object_init(void) { MC_DEBUG("json_object_init: creating object table\n"); - json_object_table = lh_kptr_table_new(128, "json_object_table", NULL); + json_object_table = lh_kptr_table_new(128, NULL); } static void json_object_fini(void) __attribute__ ((destructor)); @@ -95,9 +95,18 @@ static void json_object_fini(void) #endif /* REFCOUNT_DEBUG */ +/* helper for accessing the optimized string data component in json_object + */ +static const char * +get_string_component(struct json_object *jso) +{ + return (jso->o.c_string.len < LEN_DIRECT_STRING_DATA) ? + jso->o.c_string.str.data : jso->o.c_string.str.ptr; +} + /* string escaping */ -static int json_escape_str(struct printbuf *pb, char *str, int len) +static int json_escape_str(struct printbuf *pb, const char *str, int len) { int pos = 0, start_offset = 0; unsigned char c; @@ -362,7 +371,8 @@ static int json_object_object_to_json_string(struct json_object* jso, static void json_object_lh_entry_free(struct lh_entry *ent) { - free(ent->k); + if (!ent->k_is_constant) + free(ent->k); json_object_put((struct json_object*)ent->v); } @@ -380,7 +390,7 @@ struct json_object* json_object_new_object(void) jso->_delete = &json_object_object_delete; jso->_to_json_string = &json_object_object_to_json_string; jso->o.c_object = lh_kchar_table_new(JSON_OBJECT_DEF_HASH_ENTRIES, - NULL, &json_object_lh_entry_free); + &json_object_lh_entry_free); if (!jso->o.c_object) { json_object_generic_delete(jso); @@ -403,6 +413,31 @@ struct lh_table* json_object_get_object(struct json_object *jso) } } +void json_object_object_add_ex(struct json_object* jso, + const char *const key, + struct json_object *const val, + const unsigned opts) +{ + // We lookup the entry and replace the value, rather than just deleting + // and re-adding it, so the existing key remains valid. + json_object *existing_value = NULL; + struct lh_entry *existing_entry; + const unsigned long hash = lh_get_hash(jso->o.c_object, (void*)key); + existing_entry = (opts & JSON_C_OBJECT_ADD_KEY_IS_NEW) ? NULL : + lh_table_lookup_entry_w_hash(jso->o.c_object, (void*)key, hash); + if (!existing_entry) + { + void *const k = (opts & JSON_C_OBJECT_KEY_IS_CONSTANT) ? + (void*)key : strdup(key); + lh_table_insert_w_hash(jso->o.c_object, k, val, hash, opts); + return; + } + existing_value = (void *)existing_entry->v; + if (existing_value) + json_object_put(existing_value); + existing_entry->v = val; +} + void json_object_object_add(struct json_object* jso, const char *key, struct json_object *val) { @@ -410,10 +445,11 @@ void json_object_object_add(struct json_object* jso, const char *key, // and re-adding it, so the existing key remains valid. json_object *existing_value = NULL; struct lh_entry *existing_entry; - existing_entry = lh_table_lookup_entry(jso->o.c_object, (void*)key); + const unsigned long hash = lh_get_hash(jso->o.c_object, (void*)key); + existing_entry = lh_table_lookup_entry_w_hash(jso->o.c_object, (void*)key, hash); if (!existing_entry) { - lh_table_insert(jso->o.c_object, strdup(key), val); + lh_table_insert_w_hash(jso->o.c_object, strdup(key), val, hash, 0); return; } existing_value = (json_object *)existing_entry->v; @@ -422,6 +458,7 @@ void json_object_object_add(struct json_object* jso, const char *key, existing_entry->v = val; } + int json_object_object_length(struct json_object *jso) { return lh_table_length(jso->o.c_object); @@ -538,7 +575,7 @@ int32_t json_object_get_int(struct json_object *jso) * Parse strings into 64-bit numbers, then use the * 64-to-32-bit number handling below. */ - if (json_parse_int64(jso->o.c_string.str, &cint64) != 0) + if (json_parse_int64(get_string_component(jso), &cint64) != 0) return 0; /* whoops, it didn't work. */ o_type = json_type_int; } @@ -586,7 +623,7 @@ int64_t json_object_get_int64(struct json_object *jso) case json_type_boolean: return jso->o.c_boolean; case json_type_string: - if (json_parse_int64(jso->o.c_string.str, &cint) == 0) + if (json_parse_int64(get_string_component(jso), &cint) == 0) return cint; default: return 0; @@ -693,10 +730,10 @@ double json_object_get_double(struct json_object *jso) return jso->o.c_boolean; case json_type_string: errno = 0; - cdouble = strtod(jso->o.c_string.str,&errPtr); + cdouble = strtod(get_string_component(jso), &errPtr); /* if conversion stopped at the first character, return 0.0 */ - if (errPtr == jso->o.c_string.str) + if (errPtr == get_string_component(jso)) return 0.0; /* @@ -736,14 +773,15 @@ static int json_object_string_to_json_string(struct json_object* jso, int flags) { sprintbuf(pb, "\""); - json_escape_str(pb, jso->o.c_string.str, jso->o.c_string.len); + json_escape_str(pb, get_string_component(jso), jso->o.c_string.len); sprintbuf(pb, "\""); return 0; } static void json_object_string_delete(struct json_object* jso) { - free(jso->o.c_string.str); + if(jso->o.c_string.len >= LEN_DIRECT_STRING_DATA) + free(jso->o.c_string.str.ptr); json_object_generic_delete(jso); } @@ -754,33 +792,43 @@ struct json_object* json_object_new_string(const char *s) return NULL; jso->_delete = &json_object_string_delete; jso->_to_json_string = &json_object_string_to_json_string; - jso->o.c_string.str = strdup(s); - if (!jso->o.c_string.str) - { - json_object_generic_delete(jso); - errno = ENOMEM; - return NULL; - } jso->o.c_string.len = strlen(s); + if(jso->o.c_string.len < LEN_DIRECT_STRING_DATA) { + memcpy(jso->o.c_string.str.data, s, jso->o.c_string.len); + } else { + jso->o.c_string.str.ptr = strdup(s); + if (!jso->o.c_string.str.ptr) + { + json_object_generic_delete(jso); + errno = ENOMEM; + return NULL; + } + } return jso; } struct json_object* json_object_new_string_len(const char *s, int len) { + char *dstbuf; struct json_object *jso = json_object_new(json_type_string); if (!jso) return NULL; jso->_delete = &json_object_string_delete; jso->_to_json_string = &json_object_string_to_json_string; - jso->o.c_string.str = (char*)malloc(len + 1); - if (!jso->o.c_string.str) - { - json_object_generic_delete(jso); - errno = ENOMEM; - return NULL; + if(len < LEN_DIRECT_STRING_DATA) { + dstbuf = jso->o.c_string.str.data; + } else { + jso->o.c_string.str.ptr = (char*)malloc(len + 1); + if (!jso->o.c_string.str.ptr) + { + json_object_generic_delete(jso); + errno = ENOMEM; + return NULL; + } + dstbuf = jso->o.c_string.str.ptr; } - memcpy(jso->o.c_string.str, (void *)s, len); - jso->o.c_string.str[len] = '\0'; + memcpy(dstbuf, (void *)s, len); + dstbuf[len] = '\0'; jso->o.c_string.len = len; return jso; } @@ -792,7 +840,7 @@ const char* json_object_get_string(struct json_object *jso) switch(jso->o_type) { case json_type_string: - return jso->o.c_string.str; + return get_string_component(jso); default: return json_object_to_json_string(jso); } diff --git a/json_object.h b/json_object.h index 9e81ebe..67137d8 100644 --- a/json_object.h +++ b/json_object.h @@ -63,6 +63,36 @@ extern "C" { */ #define JSON_C_TO_STRING_NOZERO (1<<2) +/** + * A flag for the json_object_object_add_ex function which + * causes the value to be added without a check if it already exists. + * Note: it is the responsibilty of the caller to ensure that no + * key is added multiple times. If this is done, results are + * unpredictable. While this option is somewhat dangerous, it + * permits potentially large performance savings in code that + * knows for sure the key values are unique (e.g. because the + * code adds a well-known set of constant key values). + */ +#define JSON_C_OBJECT_ADD_KEY_IS_NEW (1<<1) +/** + * A flag for the json_object_object_add_ex function which + * flags the key as being constant memory. This means that + * the key will NOT be copied via strdup(), resulting in a + * potentially huge performance win (malloc, strdup and + * free are usually performance hogs). It is acceptable to + * use this flag for keys in non-constant memory blocks if + * the caller ensure that the memory holding the key lives + * longer than the corresponding json object. However, this + * is somewhat dangerous and should only be done if really + * justified. + * The general use-case for this flag is cases where the + * key is given as a real constant value in the function + * call, e.g. as in + * json_object_object_add_ex(obj, "ip", json, + * JSON_C_OBJECT_KEY_IS_CONSTANT); + */ +#define JSON_C_OBJECT_KEY_IS_CONSTANT (1<<2) + #undef FALSE #define FALSE ((json_bool)0) @@ -283,6 +313,22 @@ extern int json_object_object_length(struct json_object* obj); extern void json_object_object_add(struct json_object* obj, const char *key, struct json_object *val); +/** Add an object field to a json_object of type json_type_object + * + * The semantics are identical to json_object_object_add, except that an + * additional flag fields gives you more control over some detail aspects + * of processing. See the description of JSON_C_OBJECT_ADD_* flags for more + * details. + * + * @param obj the json_object instance + * @param key the object field name (a private copy will be duplicated) + * @param val a json_object or NULL member to associate with the given field + * @param opts process-modifying options. To specify multiple options, use + * arithmetic or (OPT1|OPT2) + */ +extern void json_object_object_add_ex(struct json_object* obj, const char *key, + struct json_object *val, const unsigned opts); + /** Get the json_object associate with a given object field * * *No* reference counts will be changed. There is no need to manually adjust diff --git a/json_object_private.h b/json_object_private.h index 5ed791b..67a77f8 100644 --- a/json_object_private.h +++ b/json_object_private.h @@ -16,6 +16,8 @@ extern "C" { #endif +#define LEN_DIRECT_STRING_DATA 32 /**< how many bytes are directly stored in json_object for strings? */ + typedef void (json_object_private_delete_fn)(struct json_object *o); struct json_object @@ -32,7 +34,13 @@ struct json_object struct lh_table *c_object; struct array_list *c_array; struct { - char *str; + union { + /* optimize: if we have small strings, we can store them + * directly. This saves considerable CPU cycles AND memory. + */ + char *ptr; + char data[LEN_DIRECT_STRING_DATA]; + } str; int len; } c_string; } o; @@ -31,6 +31,27 @@ #include "random_seed.h" #include "linkhash.h" +/* hash functions */ +static unsigned long lh_char_hash(const void *k); +static unsigned long lh_perllike_str_hash(const void *k); +static lh_hash_fn *char_hash_fn = lh_char_hash; + +int +json_global_set_string_hash(const int h) +{ + switch(h) { + case JSON_C_STR_HASH_DFLT: + char_hash_fn = lh_char_hash; + break; + case JSON_C_STR_HASH_PERLLIKE: + char_hash_fn = lh_perllike_str_hash; + break; + default: + return -1; + } + return 0; +} + void lh_abort(const char *msg, ...) { va_list ap; @@ -40,7 +61,7 @@ void lh_abort(const char *msg, ...) exit(1); } -unsigned long lh_ptr_hash(const void *k) +static unsigned long lh_ptr_hash(const void *k) { /* CAW: refactored to be 64bit nice */ return (unsigned long)((((ptrdiff_t)k * LH_PRIME) >> 4) & ULONG_MAX); @@ -404,7 +425,21 @@ static uint32_t hashlittle( const void *key, size_t length, uint32_t initval) return c; } -unsigned long lh_char_hash(const void *k) +/* a simple hash function similiar to what perl does for strings. + * for good results, the string should not be excessivly large. + */ +static unsigned long lh_perllike_str_hash(const void *k) +{ + const char *rkey = (char*) k; + unsigned hashval = 1; + + while (*rkey) + hashval = hashval * 33 + *rkey++; + + return hashval; +} + +static unsigned long lh_char_hash(const void *k) { static volatile int random_seed = -1; @@ -430,7 +465,7 @@ int lh_char_equal(const void *k1, const void *k2) return (strcmp((const char*)k1, (const char*)k2) == 0); } -struct lh_table* lh_table_new(int size, const char *name, +struct lh_table* lh_table_new(int size, lh_entry_free_fn *free_fn, lh_hash_fn *hash_fn, lh_equal_fn *equal_fn) @@ -442,7 +477,6 @@ struct lh_table* lh_table_new(int size, const char *name, if(!t) lh_abort("lh_table_new: calloc failed\n"); t->count = 0; t->size = size; - t->name = name; t->table = (struct lh_entry*)calloc(size, sizeof(struct lh_entry)); if(!t->table) lh_abort("lh_table_new: calloc failed\n"); t->free_fn = free_fn; @@ -452,16 +486,16 @@ struct lh_table* lh_table_new(int size, const char *name, return t; } -struct lh_table* lh_kchar_table_new(int size, const char *name, +struct lh_table* lh_kchar_table_new(int size, lh_entry_free_fn *free_fn) { - return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal); + return lh_table_new(size, free_fn, char_hash_fn, lh_char_equal); } -struct lh_table* lh_kptr_table_new(int size, const char *name, +struct lh_table* lh_kptr_table_new(int size, lh_entry_free_fn *free_fn) { - return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal); + return lh_table_new(size, free_fn, lh_ptr_hash, lh_ptr_equal); } void lh_table_resize(struct lh_table *t, int new_size) @@ -469,7 +503,7 @@ void lh_table_resize(struct lh_table *t, int new_size) struct lh_table *new_t; struct lh_entry *ent; - new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn); + new_t = lh_table_new(new_size, NULL, t->hash_fn, t->equal_fn); ent = t->head; while(ent) { lh_table_insert(new_t, ent->k, ent->v); @@ -480,7 +514,6 @@ void lh_table_resize(struct lh_table *t, int new_size) t->size = new_size; t->head = new_t->head; t->tail = new_t->tail; - t->resizes++; free(new_t); } @@ -497,23 +530,21 @@ void lh_table_free(struct lh_table *t) } -int lh_table_insert(struct lh_table *t, void *k, const void *v) +int lh_table_insert_w_hash(struct lh_table *t, void *k, const void *v, const unsigned long h, const unsigned opts) { - unsigned long h, n; + unsigned long n; - t->inserts++; if(t->count >= t->size * LH_LOAD_FACTOR) lh_table_resize(t, t->size * 2); - h = t->hash_fn(k); n = h % t->size; while( 1 ) { if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break; - t->collisions++; if ((int)++n == t->size) n = 0; } t->table[n].k = k; + t->table[n].k_is_constant = (opts & JSON_C_OBJECT_KEY_IS_CONSTANT); t->table[n].v = v; t->count++; @@ -529,15 +560,17 @@ int lh_table_insert(struct lh_table *t, void *k, const void *v) return 0; } +int lh_table_insert(struct lh_table *t, void *k, const void *v) +{ + return lh_table_insert_w_hash(t, k, v, lh_get_hash(t, k), 0); +} -struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k) +struct lh_entry* lh_table_lookup_entry_w_hash(struct lh_table *t, const void *k, const unsigned long h) { - unsigned long h = t->hash_fn(k); unsigned long n = h % t->size; int count = 0; - t->lookups++; while( count < t->size ) { if(t->table[n].k == LH_EMPTY) return NULL; if(t->table[n].k != LH_FREED && @@ -548,6 +581,10 @@ struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k) return NULL; } +struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k) +{ + return lh_table_lookup_entry_w_hash(t, k, lh_get_hash(t, k)); +} const void* lh_table_lookup(struct lh_table *t, const void *k) { @@ -41,6 +41,23 @@ extern "C" { */ #define LH_FREED (void*)-2 +/** + * default string hash function + */ +#define JSON_C_STR_HASH_DFLT 0 + +/** + * perl-like string hash function + */ +#define JSON_C_STR_HASH_PERLLIKE 1 + +/** + * This function sets the hash function to be used for strings. + * Must be one of the JSON_C_STR_HASH_* values. + * @returns 0 - ok, -1 if parameter was invalid + */ +int json_global_set_string_hash(const int h); + struct lh_entry; /** @@ -64,6 +81,7 @@ struct lh_entry { * The key. */ void *k; + int k_is_constant; /** * The value. */ @@ -93,36 +111,6 @@ struct lh_table { int count; /** - * Number of collisions. - */ - int collisions; - - /** - * Number of resizes. - */ - int resizes; - - /** - * Number of lookups. - */ - int lookups; - - /** - * Number of inserts. - */ - int inserts; - - /** - * Number of deletes. - */ - int deletes; - - /** - * Name of the hash table. - */ - const char *name; - - /** * The first entry. */ struct lh_entry *head; @@ -144,16 +132,6 @@ struct lh_table { /** - * Pre-defined hash and equality functions - */ -extern unsigned long lh_ptr_hash(const void *k); -extern int lh_ptr_equal(const void *k1, const void *k2); - -extern unsigned long lh_char_hash(const void *k); -extern int lh_char_equal(const void *k1, const void *k2); - - -/** * Convenience list iterator. */ #define lh_foreach(table, entry) \ @@ -171,7 +149,6 @@ for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp) * Create a new linkhash table. * @param size initial table size. The table is automatically resized * although this incurs a performance penalty. - * @param name the table name. * @param free_fn callback function used to free memory for entries * when lh_table_free or lh_table_delete is called. * If NULL is provided, then memory for keys and values @@ -184,7 +161,7 @@ for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp) * and C strings respectively. * @return a pointer onto the linkhash table. */ -extern struct lh_table* lh_table_new(int size, const char *name, +extern struct lh_table* lh_table_new(int size, lh_entry_free_fn *free_fn, lh_hash_fn *hash_fn, lh_equal_fn *equal_fn); @@ -197,7 +174,7 @@ extern struct lh_table* lh_table_new(int size, const char *name, * @param free_fn callback function used to free memory for entries. * @return a pointer onto the linkhash table. */ -extern struct lh_table* lh_kchar_table_new(int size, const char *name, +extern struct lh_table* lh_kchar_table_new(int size, lh_entry_free_fn *free_fn); @@ -209,7 +186,7 @@ extern struct lh_table* lh_kchar_table_new(int size, const char *name, * @param free_fn callback function used to free memory for entries. * @return a pointer onto the linkhash table. */ -extern struct lh_table* lh_kptr_table_new(int size, const char *name, +extern struct lh_table* lh_kptr_table_new(int size, lh_entry_free_fn *free_fn); @@ -232,6 +209,21 @@ extern int lh_table_insert(struct lh_table *t, void *k, const void *v); /** + * Insert a record into the table. This one accepts the key's hash in additon + * to the key. This is an exension to support functions that need to calculate + * the hash several times and allows them to do it just once and then pass + * in the hash to all utility functions. Depending on use case, this can be a + * very considerate performance improvement. + * @param t the table to insert into. + * @param k a pointer to the key to insert. + * @param v a pointer to the value to insert. + * @param h hash value of the key to insert + * @param opts opts, a subset of JSON_OBJECT_ADD_* flags is supported + */ +extern int lh_table_insert_w_hash(struct lh_table *t, void *k, const void *v, const unsigned long h, const unsigned opts); + + +/** * Lookup a record into the table. * @param t the table to lookup * @param k a pointer to the key to lookup @@ -240,6 +232,19 @@ extern int lh_table_insert(struct lh_table *t, void *k, const void *v); extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k); /** + * Lookup a record into the table. This one accepts the key's hash in additon + * to the key. This is an exension to support functions that need to calculate + * the hash several times and allows them to do it just once and then pass + * in the hash to all utility functions. Depending on use case, this can be a + * very considerate performance improvement. + * @param t the table to lookup + * @param k a pointer to the key to lookup + * @param h hash value of the key to lookup + * @return a pointer to the record structure of the value or NULL if it does not exist. + */ +extern struct lh_entry* lh_table_lookup_entry_w_hash(struct lh_table *t, const void *k, const unsigned long h); + +/** * Lookup a record into the table * @param t the table to lookup * @param k a pointer to the key to lookup @@ -285,6 +290,22 @@ extern int lh_table_length(struct lh_table *t); void lh_abort(const char *msg, ...); void lh_table_resize(struct lh_table *t, int new_size); + +/** + * Calculate the hash of a key for a given table. + * This is an exension to support functions that need to calculate + * the hash several times and allows them to do it just once and then pass + * in the hash to all utility functions. Depending on use case, this can be a + * very considerate performance improvement. + * @param t the table (used to obtain hash function) + * @param k a pointer to the key to lookup + * @return the key's hash + */ +static inline unsigned long lh_get_hash(const struct lh_table *t, const void *k) +{ + return t->hash_fn(k); +} + #ifdef __cplusplus } #endif |