diff options
author | Eric Haszlakiewicz <erh+git@nimenees.com> | 2015-03-03 22:00:08 -0500 |
---|---|---|
committer | Eric Haszlakiewicz <erh+git@nimenees.com> | 2015-03-03 22:00:08 -0500 |
commit | a500c1f0b5da18a4108e1844fc50fc2ed4c75a86 (patch) | |
tree | 623f0f5a6bc79e044ce1e21a3d46fcf5e2633e34 | |
parent | 9db3099572ce63a6ed73d1adc674c44f419c0d0f (diff) | |
parent | 2f5789bdef5c65b951db1add50b08028b0051c36 (diff) |
Merge pull request #155 from LeSpocky/bsearch
add bsearch for arrays
-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 5c540b3..e1858aa 100644 --- a/json_object.h +++ b/json_object.h @@ -407,6 +407,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 |