You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by rh...@apache.org on 2015/01/07 20:47:12 UTC
qpid-proton git commit: added pn_list_minpush/minpop
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 <rh...@alum.mit.edu>
Authored: Wed Jan 7 14:41:35 2015 -0500
Committer: Rafael Schloming <rh...@alum.mit.edu>
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: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org