Repository: qpid-proton Updated Branches: refs/heads/master 88f915112 -> a439ee2de
added pn_list_minpush/minpop Project: http://git-wip-us.apache.org/repos/asf/qpid-proton/repo Commit: http://git-wip-us.apache.org/repos/asf/qpid-proton/commit/a439ee2d Tree: http://git-wip-us.apache.org/repos/asf/qpid-proton/tree/a439ee2d Diff: http://git-wip-us.apache.org/repos/asf/qpid-proton/diff/a439ee2d Branch: refs/heads/master Commit: a439ee2de6a969a583096d34c673d57eb28f635f Parents: 88f9151 Author: Rafael Schloming <[email protected]> Authored: Wed Jan 7 14:41:35 2015 -0500 Committer: Rafael Schloming <[email protected]> Committed: Wed Jan 7 14:41:35 2015 -0500 ---------------------------------------------------------------------- proton-c/include/proton/object.h | 2 ++ proton-c/src/object/list.c | 38 ++++++++++++++++++++++++++++ proton-c/src/object/object.c | 6 ++--- proton-c/src/tests/object.c | 47 +++++++++++++++++++++++++++++++++++ 4 files changed, 90 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/a439ee2d/proton-c/include/proton/object.h ---------------------------------------------------------------------- diff --git a/proton-c/include/proton/object.h b/proton-c/include/proton/object.h index f432d43..49cb333 100644 --- a/proton-c/include/proton/object.h +++ b/proton-c/include/proton/object.h @@ -144,6 +144,8 @@ PN_EXTERN bool pn_list_remove(pn_list_t *list, void *value); PN_EXTERN void pn_list_del(pn_list_t *list, int index, int n); PN_EXTERN void pn_list_clear(pn_list_t *list); PN_EXTERN void pn_list_iterator(pn_list_t *list, pn_iterator_t *iter); +PN_EXTERN void pn_list_minpush(pn_list_t *list, void *value); +PN_EXTERN void *pn_list_minpop(pn_list_t *list); #define PN_REFCOUNT_KEY (0x2) #define PN_REFCOUNT_VALUE (0x4) http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/a439ee2d/proton-c/src/object/list.c ---------------------------------------------------------------------- diff --git a/proton-c/src/object/list.c b/proton-c/src/object/list.c index 899a4fd..842ef9e 100644 --- a/proton-c/src/object/list.c +++ b/proton-c/src/object/list.c @@ -136,6 +136,44 @@ void pn_list_fill(pn_list_t *list, void *value, int n) } } +void pn_list_minpush(pn_list_t *list, void *value) +{ + assert(list); + pn_list_add(list, value); + // we use one based indexing for the heap + void **heap = list->elements - 1; + int now = list->size; + while (now > 1 && pn_class_compare(list->clazz, heap[now/2], value) > 0) { + heap[now] = heap[now/2]; + now /= 2; + } + heap[now] = value; +} + +void *pn_list_minpop(pn_list_t *list) +{ + assert(list); + // we use one based indexing for the heap + void **heap = list->elements - 1; + void *min = heap[1]; + void *last = pn_list_pop(list); + int size = pn_list_size(list); + int now, child; + for (now = 1; now*2 <= size; now = child) { + child = now*2; + if (child != size && pn_class_compare(list->clazz, heap[child], heap[child + 1]) > 0) { + child++; + } + if (pn_class_compare(list->clazz, last, heap[child]) > 0) { + heap[now] = heap[child]; + } else { + break; + } + } + heap[now] = last; + return min; +} + typedef struct { pn_list_t *list; size_t index; http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/a439ee2d/proton-c/src/object/object.c ---------------------------------------------------------------------- diff --git a/proton-c/src/object/object.c b/proton-c/src/object/object.c index b0cfcc7..9c91343 100644 --- a/proton-c/src/object/object.c +++ b/proton-c/src/object/object.c @@ -27,7 +27,7 @@ #define pn_object_finalize NULL #define pn_object_inspect NULL uintptr_t pn_object_hashcode(void *object) { return (uintptr_t) object; } -intptr_t pn_object_compare(void *a, void *b) { return (intptr_t) b - (intptr_t) a; } +intptr_t pn_object_compare(void *a, void *b) { return (intptr_t) a - (intptr_t) b; } const pn_class_t PNI_OBJECT = PN_CLASS(pn_object); const pn_class_t *PN_OBJECT = &PNI_OBJECT; @@ -41,7 +41,7 @@ static int pn_void_refcount(void *object) { return -1; } static void pn_void_free(void *object) { free(object); } static const pn_class_t *pn_void_reify(void *object) { return PN_VOID; } uintptr_t pn_void_hashcode(void *object) { return (uintptr_t) object; } -intptr_t pn_void_compare(void *a, void *b) { return (intptr_t) b - (intptr_t) a; } +intptr_t pn_void_compare(void *a, void *b) { return (intptr_t) a - (intptr_t) b; } int pn_void_inspect(void *object, pn_string_t *dst) { return pn_string_addf(dst, "%p", object); } const pn_class_t PNI_VOID = PN_METACLASS(pn_void); @@ -162,7 +162,7 @@ intptr_t pn_class_compare(const pn_class_t *clazz, void *a, void *b) if (a && b && clazz->compare) { return clazz->compare(a, b); } else { - return (intptr_t) b - (intptr_t) a; + return (intptr_t) a - (intptr_t) b; } } http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/a439ee2d/proton-c/src/tests/object.c ---------------------------------------------------------------------- diff --git a/proton-c/src/tests/object.c b/proton-c/src/tests/object.c index ad83006..2596bec 100644 --- a/proton-c/src/tests/object.c +++ b/proton-c/src/tests/object.c @@ -862,6 +862,48 @@ void test_iterator(void) pn_free(it); } +void test_heap(int seed, int size) +{ + srand(seed); + pn_list_t *list = pn_list(PN_VOID, 0); + + intptr_t min; + intptr_t max; + + for (int i = 0; i < size; i++) { + intptr_t r = rand(); + + if (i == 0) { + min = r; + max = r; + } else { + if (r < min) { + min = r; + } + if (r > max) { + max = r; + } + } + + pn_list_minpush(list, (void *) r); + } + + intptr_t prev = (intptr_t) pn_list_minpop(list); + assert(prev == min); + assert(pn_list_size(list) == (size_t)(size - 1)); + int count = 0; + while (pn_list_size(list)) { + intptr_t r = (intptr_t) pn_list_minpop(list); + assert(r >= prev); + prev = r; + count++; + } + assert(count == size - 1); + assert(prev == max); + + pn_free(list); +} + int main(int argc, char **argv) { for (size_t i = 0; i < 128; i++) { @@ -923,6 +965,11 @@ int main(int argc, char **argv) test_map_inspect(); test_list_compare(); test_iterator(); + for (int seed = 0; seed < 64; seed++) { + for (int size = 1; size <= 64; size++) { + test_heap(seed, size); + } + } return 0; } --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
