diff options
| -rw-r--r-- | builtins/array.c | 121 |
1 files changed, 18 insertions, 103 deletions
diff --git a/builtins/array.c b/builtins/array.c index 0c629610..22abf976 100644 --- a/builtins/array.c +++ b/builtins/array.c @@ -453,23 +453,8 @@ public uint32_t Array$hash(const array_t *arr, const TypeInfo *type) return hash; } } -/* -def _siftdown(heap, startpos, pos): - newitem = heap[pos] - # Follow the path to the root, moving parents down until finding a place - # newitem fits. - while pos > startpos: - parentpos = (pos - 1) >> 1 - parent = heap[parentpos] - if newitem < parent: - heap[pos] = parent - pos = parentpos - continue - break - heap[pos] = newitem - */ - -static int siftdown(array_t *heap, int64_t startpos, int64_t pos, closure_t comparison, const TypeInfo *type) + +static void siftdown(array_t *heap, int64_t startpos, int64_t pos, closure_t comparison, const TypeInfo *type) { assert(pos > 0 && pos < heap->length); int64_t item_size = get_item_size(type); @@ -489,10 +474,9 @@ static int siftdown(array_t *heap, int64_t startpos, int64_t pos, closure_t comp pos = parentpos; } - return 0; } -static int siftup(array_t *heap, int64_t pos, closure_t comparison, const TypeInfo *type) +static void siftup(array_t *heap, int64_t pos, closure_t comparison, const TypeInfo *type) { int64_t endpos = heap->length; int64_t startpos = pos; @@ -510,8 +494,6 @@ static int siftup(array_t *heap, int64_t pos, closure_t comparison, const TypeIn heap->data + heap->stride*childpos, heap->data + heap->stride*(childpos + 1), comparison.userdata); - // if (cmp < 0) - // return -1; childpos += (cmp >= 0); } @@ -529,18 +511,18 @@ static int siftup(array_t *heap, int64_t pos, closure_t comparison, const TypeIn pos = childpos; } /* Bubble it up to its final resting place (by sifting its parents down). */ - return siftdown(heap, startpos, pos, comparison, type); + siftdown(heap, startpos, pos, comparison, type); } public void Array$heap_push(array_t *heap, const void *item, closure_t comparison, const TypeInfo *type) { Array$insert(heap, item, 0, type); - if (heap->data_refcount > 0) - Array$compact(heap, type); - - if (heap->length > 1) + if (heap->length > 1) { + if (heap->data_refcount > 0) + Array$compact(heap, type); siftdown(heap, 0, heap->length-1, comparison, type); + } } public void Array$heap_pop(array_t *heap, void *out, closure_t comparison, const TypeInfo *type) @@ -550,96 +532,29 @@ public void Array$heap_pop(array_t *heap, void *out, closure_t comparison, const int64_t item_size = get_item_size(type); memcpy(out, heap->data, item_size); - if (heap->length > 1) { + if (heap->length == 1) { + *heap = (array_t){}; + } else if (heap->length == 2) { + heap->data += heap->stride; + --heap->length; + } else { if (heap->data_refcount > 0) Array$compact(heap, type); memcpy(heap->data, heap->data + heap->stride*(heap->length-1), item_size); --heap->length; - if (heap->length > 1) - siftup(heap, 0, comparison, type); - } else { - *heap = (array_t){}; + siftup(heap, 0, comparison, type); } } -static int64_t -keep_top_bit(int64_t n) -{ - int i = 0; - for (; n > 1; n >>= 1) - ++i; - return n << i; -} - public void Array$heapify(array_t *heap, closure_t comparison, const TypeInfo *type) { if (heap->data_refcount > 0) Array$compact(heap, type); ARRAY_INCREF(*heap); - /* For heaps likely to be bigger than L1 cache, we use the cache - friendly heapify function. For smaller heaps that fit entirely - in cache, we prefer the simpler algorithm with less branching. - */ - if (heap->length <= 2500) { - /* Transform bottom-up. The largest index there's any point to - looking at is the largest with a child index in-range, so must - have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is - (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If - n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest, - and that's again n//2-1. - */ - int64_t i, n = heap->length; - for (i = (n >> 1) - 1 ; i >= 0 ; i--) - if (siftup(heap, i, comparison, type)) - goto cleanup; - } else { - /* Cache friendly version of heapify() - ----------------------------------- - - Build-up a heap in O(n) time by performing siftup() operations - on nodes whose children are already heaps. - - The simplest way is to sift the nodes in reverse order from - n//2-1 to 0 inclusive. The downside is that children may be - out of cache by the time their parent is reached. - - A better way is to not wait for the children to go out of cache. - Once a sibling pair of child nodes have been sifted, immediately - sift their parent node (while the children are still in cache). - - Both ways build child heaps before their parents, so both ways - do the exact same number of comparisons and produce exactly - the same heap. The only difference is that the traversal - order is optimized for cache efficiency. - */ - int64_t m = heap->length >> 1; /* index of first childless node */ - int64_t leftmost = keep_top_bit(m + 1) - 1; /* leftmost node in row of m */ - int64_t mhalf = m >> 1; /* parent of first childless node */ - int64_t i; - for (i = leftmost - 1 ; i >= mhalf ; i--) { - int64_t j = i; - while (1) { - if (siftup(heap, j, comparison, type)) - goto cleanup; - if (!(j & 1)) - break; - j >>= 1; - } - } - - for (i = m - 1 ; i >= leftmost ; i--) { - int64_t j = i; - while (1) { - if (siftup(heap, j, comparison, type)) - goto cleanup; - if (!(j & 1)) - break; - j >>= 1; - } - } - } - cleanup: + int64_t i, n = heap->length; + for (i = (n >> 1) - 1 ; i >= 0 ; i--) + siftup(heap, i, comparison, type); ARRAY_DECREF(*heap); } |