diff options
author | Alexander Dahl <post@lespocky.de> | 2014-08-21 15:42:50 +0200 |
---|---|---|
committer | Alexander Dahl <post@lespocky.de> | 2014-08-21 15:42:50 +0200 |
commit | 2f5789bdef5c65b951db1add50b08028b0051c36 (patch) | |
tree | 4cb30a8ce95dbac3f9f7dcefa5159ec7728695c5 | |
parent | d4e81f9ec8273914739808737fa0a27a3f0589fb (diff) |
add bsearch for arrays
Arrays can already be sorted with json_object_array_sort() which uses
qsort() of the standard C library. This adds a counterpart using the
bsearch() from C.
-rw-r--r-- | arraylist.c | 10 | ||||
-rw-r--r-- | arraylist.h | 5 | ||||
-rw-r--r-- | json_object.c | 17 | ||||
-rw-r--r-- | json_object.h | 19 |
4 files changed, 49 insertions, 2 deletions
diff --git a/arraylist.c b/arraylist.c index 1d899fa..5ccbdd2 100644 --- a/arraylist.c +++ b/arraylist.c @@ -91,8 +91,14 @@ array_list_add(struct array_list *arr, void *data) void array_list_sort(struct array_list *arr, int(*sort_fn)(const void *, const void *)) { - qsort(arr->array, arr->length, sizeof(arr->array[0]), - (int (*)(const void *, const void *))sort_fn); + qsort(arr->array, arr->length, sizeof(arr->array[0]), sort_fn); +} + +void* array_list_bsearch( const void **key, struct array_list *arr, + int (*sort_fn)(const void *, const void *) ) +{ + return bsearch( key, arr->array, arr->length, sizeof(arr->array[0]), + sort_fn ); } int diff --git a/arraylist.h b/arraylist.h index 4f3113c..50fb320 100644 --- a/arraylist.h +++ b/arraylist.h @@ -49,6 +49,11 @@ array_list_length(struct array_list *al); extern void array_list_sort(struct array_list *arr, int(*compar)(const void *, const void *)); +extern void* array_list_bsearch( const void **key, + struct array_list *arr, + int (*sort_fn)(const void *, const void *) ); + + #ifdef __cplusplus } #endif diff --git a/json_object.c b/json_object.c index 8ed0239..c858a9e 100644 --- a/json_object.c +++ b/json_object.c @@ -889,6 +889,23 @@ void json_object_array_sort(struct json_object *jso, int(*sort_fn)(const void *, array_list_sort(jso->o.c_array, sort_fn); } +struct json_object* json_object_array_bsearch( + const struct json_object *key, + const struct json_object *jso, + int (*sort_fn)(const void *, const void *) ) +{ + struct json_object **result; + + result = (struct json_object **) array_list_bsearch( + (const void **) &key, jso->o.c_array, sort_fn ); + + if ( result == NULL ) { + return NULL; + } else { + return *result; + } +} + int json_object_array_length(struct json_object *jso) { return array_list_length(jso->o.c_array); diff --git a/json_object.h b/json_object.h index 200ac40..44e2b7b 100644 --- a/json_object.h +++ b/json_object.h @@ -402,6 +402,25 @@ extern int json_object_array_length(struct json_object *obj); */ extern void json_object_array_sort(struct json_object *jso, int(*sort_fn)(const void *, const void *)); +/** Binary search a sorted array for a specified key object. + * + * It depends on your compare function what's sufficient as a key. + * Usually you create some dummy object with the parameter compared in + * it, to identify the right item you're actually looking for. + * + * @see json_object_array_sort() for hints on the compare function. + * + * @param key a dummy json_object with the right key + * @param jso the array object we're searching + * @param sort_fn the sort/compare function + * + * @return the wanted json_object instance + */ +extern struct json_object* json_object_array_bsearch( + const struct json_object *key, + const struct json_object *jso, + int (*sort_fn)(const void *, const void *) ); + /** Add an element to the end of a json_object of type json_type_array * * The reference count will *not* be incremented. This is to make adding |