From 1a29a798ac5f8b903b8cb552038f31288020b0c1 Mon Sep 17 00:00:00 2001 From: Alex Wang Date: Wed, 16 Oct 2013 03:32:31 +0000 Subject: [PATCH] heap: Change type of "priority" in "struct heap". This commit changes the variable type of priority in "struct heap" from uint32_t to uint64_t. Signed-off-by: Alex Wang Signed-off-by: Ethan Jackson Acked-by: Ethan Jackson --- lib/heap.c | 6 +++--- lib/heap.h | 12 ++++++------ 2 files changed, 9 insertions(+), 9 deletions(-) diff --git a/lib/heap.c b/lib/heap.c index b2d547a5e..682915ac3 100644 --- a/lib/heap.c +++ b/lib/heap.c @@ -65,7 +65,7 @@ heap_swap(struct heap *a, struct heap *b) * * This takes time O(lg n). */ void -heap_insert(struct heap *heap, struct heap_node *node, uint32_t priority) +heap_insert(struct heap *heap, struct heap_node *node, uint64_t priority) { heap_raw_insert(heap, node, priority); float_up(heap, node->idx); @@ -89,7 +89,7 @@ heap_remove(struct heap *heap, struct heap_node *node) * * This takes time O(lg n). */ void -heap_change(struct heap *heap, struct heap_node *node, uint32_t priority) +heap_change(struct heap *heap, struct heap_node *node, uint64_t priority) { heap_raw_change(node, priority); float_up_or_down(heap, node->idx); @@ -104,7 +104,7 @@ heap_change(struct heap *heap, struct heap_node *node, uint32_t priority) * * This takes time O(1). */ void -heap_raw_insert(struct heap *heap, struct heap_node *node, uint32_t priority) +heap_raw_insert(struct heap *heap, struct heap_node *node, uint64_t priority) { if (heap->n >= heap->allocated) { heap->allocated = heap->n == 0 ? 1 : 2 * heap->n; diff --git a/lib/heap.h b/lib/heap.h index 5c07e0454..870f58255 100644 --- a/lib/heap.h +++ b/lib/heap.h @@ -24,7 +24,7 @@ /* A heap node, to be embedded inside the data structure in the heap. */ struct heap_node { size_t idx; - uint32_t priority; + uint64_t priority; }; /* A max-heap. */ @@ -43,8 +43,8 @@ static inline size_t heap_count(const struct heap *); static inline bool heap_is_empty(const struct heap *); /* Insertion and deletion. */ -void heap_insert(struct heap *, struct heap_node *, uint32_t priority); -void heap_change(struct heap *, struct heap_node *, uint32_t priority); +void heap_insert(struct heap *, struct heap_node *, uint64_t priority); +void heap_change(struct heap *, struct heap_node *, uint64_t priority); void heap_remove(struct heap *, struct heap_node *); static inline struct heap_node *heap_pop(struct heap *); @@ -54,8 +54,8 @@ static inline struct heap_node *heap_max(const struct heap *); /* The "raw" functions below do not preserve the heap invariants. After you * call them, heap_max() will not necessarily return the right value until you * subsequently call heap_rebuild(). */ -void heap_raw_insert(struct heap *, struct heap_node *, uint32_t priority); -static inline void heap_raw_change(struct heap_node *, uint32_t priority); +void heap_raw_insert(struct heap *, struct heap_node *, uint64_t priority); +static inline void heap_raw_change(struct heap_node *, uint64_t priority); void heap_raw_remove(struct heap *, struct heap_node *); void heap_rebuild(struct heap *); @@ -155,7 +155,7 @@ heap_pop(struct heap *heap) * * This takes time O(1). */ static inline void -heap_raw_change(struct heap_node *node, uint32_t priority) +heap_raw_change(struct heap_node *node, uint64_t priority) { node->priority = priority; } -- 2.43.0