Source/bmalloc/libpas/src/libpas/pas_min_heap.h - WebKit - Git at Google

 /*
  * Copyright (c) 2019-2020 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #ifndef PAS_MIN_HEAP_H
 #define PAS_MIN_HEAP_H

 #include "pas_allocation_config.h"
 #include "pas_utils.h"
 #include <stdio.h>

 PAS_BEGIN_EXTERN_C;

 #define PAS_MIN_HEAP_INITIALIZER(name) ((name){ \
         .outline_array = NULL, \
         .size = 0, \
         .outline_capacity = 0 \
     })

 /* A min_heap is a complete binary tree, so it is representable as an array. It's easiest to
    see what is going on by using one-based array indices:

                   1
            2            3
         4     5      6     7
        8 9  10 11  12 13 14 15

    This way, the indices of node X's children are at 2X and 2X+1.

    This also has built-in support for heapsort, but because it's primarily designed as a heap
    not as a sort, it will sort descending. Heapsort has this property that it sorts in the
    opposite order of the heap, so an ascending heapsort will be based on a maxheap. If you want
    to run this as an ascending heapsort, just invert your compare function. */

 #define PAS_CREATE_MIN_HEAP(name, type, inline_capacity, ...) \
     struct name; \
     struct name##_config; \
     typedef struct name name; \
     typedef struct name##_config name##_config; \
     \
     struct name { \
         size_t size; \
         type inline_array[inline_capacity]; \
         type* outline_array; \
         size_t outline_capacity; \
     }; \
     \
     struct name##_config { \
         int (*compare)(type* left, type* right); \
         \
         size_t (*get_index)(type* element); /* Optional - only needed if you call */\
                                             /* pas_min_heap_remove(). */\
         \
         void (*set_index)(type* element, size_t index);  /* Can be a no-op unless you need to */\
                                                          /* know the index or you use */\
                                                          /* pas_min_heap_remove(). */\
     }; \
     \
     static inline type* name##_get_ptr_by_index(name* min_heap, size_t index) \
     { \
         PAS_ASSERT(index); \
         index--; \
         PAS_ASSERT(index < (inline_capacity) + min_heap->outline_capacity); \
         if (index < (inline_capacity)) \
             return min_heap->inline_array + index; \
         return min_heap->outline_array + index - (inline_capacity); \
     } \
     \
     PAS_UNUSED static inline void name##_construct(name* min_heap) \
     { \
         *min_heap = PAS_MIN_HEAP_INITIALIZER(name); \
         pas_zero_memory(min_heap->inline_array, sizeof(type) * (inline_capacity)); \
     } \
     \
     PAS_UNUSED static inline void name##_destruct( \
         name* min_heap, \
         const pas_allocation_config* allocation_config) \
     { \
         allocation_config->deallocate(min_heap->outline_array, \
                                       min_heap->outline_capacity * sizeof(type), \
                                       pas_object_allocation, \
                                       allocation_config->arg); \
     } \
     \
     /* This takes a one-based index. */ \
     PAS_UNUSED static inline type name##_remove_by_index(name* min_heap, \
                                                          size_t index) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         type result; \
         type element_at_index; \
         size_t size; \
         size_t parent_index; \
         \
         PAS_ASSERT(index); \
         \
         size = min_heap->size; \
         \
         PAS_ASSERT(index <= size); \
         \
         result = *name##_get_ptr_by_index(min_heap, index); \
         element_at_index = *name##_get_ptr_by_index(min_heap, size); \
         \
         /* We keep the array zeroed in the parts that we're not using. That just makes */ \
         /* debugging easier. */ \
         pas_zero_memory(name##_get_ptr_by_index(min_heap, size), \
                     sizeof(type)); \
         \
         /* Doing this aids debugging. */ \
         pas_zero_memory(name##_get_ptr_by_index(min_heap, index), \
                     sizeof(type)); \
         \
         size--; \
         \
         min_heap->size = size; \
         \
         if (index == size + 1) { \
             /* This is a fantastic special case. If the last element is the one we are removing */ \
             /* then it's a waste of time for us to do any bubbling. Also, we cannot bubble the */ \
             /* last element if it is already out-of-order - in that case we will end up removing */ \
             /* some other element. */ \
             config.set_index(&result, 0); \
             return result; \
         } \
         \
         parent_index = index >> 1; \
         if (parent_index) { \
             type parent; \
             bool less_than_parent; \
             \
             parent = *name##_get_ptr_by_index(min_heap, parent_index); \
             less_than_parent = config.compare(&element_at_index, &parent) < 0; \
             \
             if (less_than_parent) { \
                 do { \
                     config.set_index(&parent, index); \
                     \
                     *name##_get_ptr_by_index(min_heap, index) = parent; \
                     \
                     index = parent_index; \
                     PAS_ASSERT(index >= 1); \
                     if (index == 1) \
                         break; \
                     \
                     parent_index = index >> 1; \
                     \
                     parent = *name##_get_ptr_by_index(min_heap, parent_index); \
                     less_than_parent = config.compare(&element_at_index, &parent) < 0; \
                 } while (less_than_parent); \
                 \
                 goto done; \
             } \
         } \
         \
         for (;;) { \
             size_t index_of_left; \
             size_t index_of_right; \
             type element_right; \
             bool less_equal_right; \
             type element_left; \
             bool less_equal_left; \
             \
             /* It already must be the case that the node at `index` is greater than its parent, */\
             /* since that node came from the bottom of the heap. But it may not be less than or */\
             /* equal to its children. */\
             \
             index_of_left = index << 1; \
             index_of_right = (index << 1) + 1; \
             \
             pas_zero_memory(&element_right, sizeof(element_right)); \
             less_equal_right = true; \
             pas_zero_memory(&element_left, sizeof(element_left)); \
             less_equal_left = true; \
             \
             if (index_of_right <= size) { \
                 element_right = *name##_get_ptr_by_index(min_heap, index_of_right); \
                 less_equal_right = config.compare(&element_at_index, &element_right) <= 0; \
             } \
             \
             if (index_of_left <= size) { \
                 element_left = *name##_get_ptr_by_index(min_heap, index_of_left); \
                 less_equal_left = config.compare(&element_at_index, &element_left) <= 0; \
             } \
             \
             if (!less_equal_right \
                 && (less_equal_left || config.compare(&element_right, &element_left) < 0)) { \
                 config.set_index(&element_right, index); \
                 \
                 *name##_get_ptr_by_index(min_heap, index) = element_right; \
                 \
                 index = index_of_right; \
                 continue; \
             } \
             \
             if (!less_equal_left) { \
                 config.set_index(&element_left, index); \
                 \
                 *name##_get_ptr_by_index(min_heap, index) = element_left; \
                 \
                 index = index_of_left; \
                 continue; \
             } \
             \
         done: \
             *name##_get_ptr_by_index(min_heap, index) = element_at_index; \
             config.set_index(&element_at_index, index); \
             config.set_index(&result, 0); \
             return result; \
         } \
     } \
     \
     PAS_UNUSED static inline type name##_get_min(name* min_heap) \
     { \
         if (!min_heap->size) { \
             type result; \
             pas_zero_memory(&result, sizeof(type)); \
             return result; \
         } \
         \
         return *name##_get_ptr_by_index(min_heap, 1); \
     } \
     \
     PAS_UNUSED static inline type name##_take_min(name* min_heap) \
     { \
         if (!min_heap->size) { \
             type result; \
             pas_zero_memory(&result, sizeof(type)); \
             return result; \
         } \
         \
         return name##_remove_by_index(min_heap, 1); \
     } \
     \
     PAS_UNUSED static inline void name##_remove(name* min_heap, \
                                                 type element) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         size_t index = config.get_index(&element); \
         PAS_ASSERT(index); \
         PAS_ASSERT(!bcmp(name##_get_ptr_by_index(min_heap, index), &element, sizeof(type))); \
         name##_remove_by_index(min_heap, index); \
     } \
     \
     PAS_UNUSED static inline void name##_add( \
         name* min_heap, \
         type element, \
         const pas_allocation_config* allocation_config) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         size_t size; \
         size_t outline_capacity; \
         size_t index; \
         \
         size = min_heap->size; \
         outline_capacity = min_heap->outline_capacity; \
         \
         if (size >= (inline_capacity) + outline_capacity) { \
             type* new_outline_array; \
             size_t new_outline_capacity; \
             \
             PAS_ASSERT(size == (inline_capacity) + outline_capacity); \
             \
             new_outline_capacity = PAS_MAX((size_t)4, outline_capacity << 1); \
             PAS_ASSERT(new_outline_capacity > outline_capacity); \
             new_outline_array = (type*)allocation_config->allocate( \
                 new_outline_capacity * sizeof(type), \
                 #name "/outline_array", \
                 pas_object_allocation, \
                 allocation_config->arg); \
             \
             PAS_ASSERT(size < (inline_capacity) + new_outline_capacity); \
             \
             pas_zero_memory(new_outline_array, sizeof(type) * new_outline_capacity); \
             \
             memcpy(new_outline_array, \
                    min_heap->outline_array, \
                    (size - (inline_capacity)) * sizeof(type)); \
             \
             allocation_config->deallocate( \
                 min_heap->outline_array, \
                 outline_capacity * sizeof(type), \
                 pas_object_allocation, \
                 allocation_config->arg); \
             \
             outline_capacity = new_outline_capacity; \
             \
             min_heap->outline_array = new_outline_array; \
             min_heap->outline_capacity = new_outline_capacity; \
         } \
         \
         index = ++size; \
         PAS_ASSERT(size <= (inline_capacity) + outline_capacity); \
         \
         /* Doing this aids debugging. */ \
         pas_zero_memory(name##_get_ptr_by_index(min_heap, index), sizeof(type)); \
         \
         min_heap->size = size; \
         \
         while (index > 1) { \
             size_t index_of_parent; \
             type parent; \
             bool greater_equal_parent; \
             \
             index_of_parent = index >> 1; \
             \
             parent = *name##_get_ptr_by_index(min_heap, index_of_parent); \
             greater_equal_parent = config.compare(&element, &parent) >= 0; \
             \
             if (greater_equal_parent) \
                 break; \
             \
             config.set_index(&parent, index); \
             \
             *name##_get_ptr_by_index(min_heap, index) = parent; \
             \
             index = index_of_parent; \
         } \
         \
         config.set_index(&element, index); \
         *name##_get_ptr_by_index(min_heap, index) = element; \
     } \
     \
     PAS_UNUSED static inline bool name##_is_index_still_ordered(name* min_heap, \
                                                                 size_t index, \
                                                                 type element) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         size_t size; \
         \
         size = min_heap->size; \
         \
         if (index > 1 \
             && config.compare(&element, name##_get_ptr_by_index(min_heap, \
                                                                 index >> 1)) < 0) \
             return false; \
         \
         if ((index << 1) <= size \
             && config.compare(&element, name##_get_ptr_by_index(min_heap, \
                                                                 index << 1)) > 0) \
             return false; \
         \
         if ((index << 1) + 1 <= size \
             && config.compare(&element, name##_get_ptr_by_index(min_heap, \
                                                                 (index << 1) + 1)) > 0) \
             return false; \
         \
         return true; \
     } \
     \
     PAS_UNUSED static inline bool name##_is_still_ordered(name* min_heap, \
                                                           type element) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         return name##_is_index_still_ordered( \
             min_heap, config.get_index(&element), element); \
     } \
     \
     PAS_UNUSED static inline void name##_update_order(name* min_heap, \
                                                       type element, \
                                                       const pas_allocation_config* allocation_config) \
     { \
         name##_config config = {__VA_ARGS__}; \
         \
         if (config.get_index(&element)) { \
             if (name##_is_still_ordered(min_heap, element)) \
                 return; \
             \
             name##_remove(min_heap, element); \
         } \
         \
         name##_add(min_heap, element, allocation_config); \
     } \
     \
     PAS_UNUSED static inline void name##_sort_descending(name* min_heap) \
     { \
         size_t original_size = min_heap->size; \
         \
         while (min_heap->size) { \
             type value; \
             \
             value = name##_take_min(min_heap); \
             \
             *name##_get_ptr_by_index(min_heap, min_heap->size + 1) = value; \
         } \
         \
         /* At this point, this isn't a heap anymore. It's an array sorted in descending */ \
         /* order. */ \
         min_heap->size = original_size; \
     } \
     \
     struct pas_dummy

 PAS_END_EXTERN_C;

 #endif /* PAS_MIN_HEAP_H */
	/*
	* Copyright (c) 2019-2020 Apple Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#ifndef PAS_MIN_HEAP_H
	#define PAS_MIN_HEAP_H

	#include "pas_allocation_config.h"
	#include "pas_utils.h"
	#include <stdio.h>

	PAS_BEGIN_EXTERN_C;

	#define PAS_MIN_HEAP_INITIALIZER(name) ((name){ \
	.outline_array = NULL, \
	.size = 0, \
	.outline_capacity = 0 \
	})

	/* A min_heap is a complete binary tree, so it is representable as an array. It's easiest to
	see what is going on by using one-based array indices:

	1
	2 3
	4 5 6 7
	8 9 10 11 12 13 14 15

	This way, the indices of node X's children are at 2X and 2X+1.

	This also has built-in support for heapsort, but because it's primarily designed as a heap
	not as a sort, it will sort descending. Heapsort has this property that it sorts in the
	opposite order of the heap, so an ascending heapsort will be based on a maxheap. If you want
	to run this as an ascending heapsort, just invert your compare function. */

	#define PAS_CREATE_MIN_HEAP(name, type, inline_capacity, ...) \
	struct name; \
	struct name##_config; \
	typedef struct name name; \
	typedef struct name##_config name##_config; \
	\
	struct name { \
	size_t size; \
	type inline_array[inline_capacity]; \
	type* outline_array; \
	size_t outline_capacity; \
	}; \
	\
	struct name##_config { \
	int (compare)(type left, type* right); \
	\
	size_t (get_index)(type element); /* Optional - only needed if you call */\
	/* pas_min_heap_remove(). */\
	\
	void (set_index)(type element, size_t index); /* Can be a no-op unless you need to */\
	/* know the index or you use */\
	/* pas_min_heap_remove(). */\
	}; \
	\
	static inline type* name##_get_ptr_by_index(name* min_heap, size_t index) \
	{ \
	PAS_ASSERT(index); \
	index--; \
	PAS_ASSERT(index < (inline_capacity) + min_heap->outline_capacity); \
	if (index < (inline_capacity)) \
	return min_heap->inline_array + index; \
	return min_heap->outline_array + index - (inline_capacity); \
	} \
	\
	PAS_UNUSED static inline void name##_construct(name* min_heap) \
	{ \
	*min_heap = PAS_MIN_HEAP_INITIALIZER(name); \
	pas_zero_memory(min_heap->inline_array, sizeof(type) * (inline_capacity)); \
	} \
	\
	PAS_UNUSED static inline void name##_destruct( \
	name* min_heap, \
	const pas_allocation_config* allocation_config) \
	{ \
	allocation_config->deallocate(min_heap->outline_array, \
	min_heap->outline_capacity * sizeof(type), \
	pas_object_allocation, \
	allocation_config->arg); \
	} \
	\
	/* This takes a one-based index. */ \
	PAS_UNUSED static inline type name##_remove_by_index(name* min_heap, \
	size_t index) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	type result; \
	type element_at_index; \
	size_t size; \
	size_t parent_index; \
	\
	PAS_ASSERT(index); \
	\
	size = min_heap->size; \
	\
	PAS_ASSERT(index <= size); \
	\
	result = *name##_get_ptr_by_index(min_heap, index); \
	element_at_index = *name##_get_ptr_by_index(min_heap, size); \
	\
	/* We keep the array zeroed in the parts that we're not using. That just makes */ \
	/* debugging easier. */ \
	pas_zero_memory(name##_get_ptr_by_index(min_heap, size), \
	sizeof(type)); \
	\
	/* Doing this aids debugging. */ \
	pas_zero_memory(name##_get_ptr_by_index(min_heap, index), \
	sizeof(type)); \
	\
	size--; \
	\
	min_heap->size = size; \
	\
	if (index == size + 1) { \
	/* This is a fantastic special case. If the last element is the one we are removing */ \
	/* then it's a waste of time for us to do any bubbling. Also, we cannot bubble the */ \
	/* last element if it is already out-of-order - in that case we will end up removing */ \
	/* some other element. */ \
	config.set_index(&result, 0); \
	return result; \
	} \
	\
	parent_index = index >> 1; \
	if (parent_index) { \
	type parent; \
	bool less_than_parent; \
	\
	parent = *name##_get_ptr_by_index(min_heap, parent_index); \
	less_than_parent = config.compare(&element_at_index, &parent) < 0; \
	\
	if (less_than_parent) { \
	do { \
	config.set_index(&parent, index); \
	\
	*name##_get_ptr_by_index(min_heap, index) = parent; \
	\
	index = parent_index; \
	PAS_ASSERT(index >= 1); \
	if (index == 1) \
	break; \
	\
	parent_index = index >> 1; \
	\
	parent = *name##_get_ptr_by_index(min_heap, parent_index); \
	less_than_parent = config.compare(&element_at_index, &parent) < 0; \
	} while (less_than_parent); \
	\
	goto done; \
	} \
	} \
	\
	for (;;) { \
	size_t index_of_left; \
	size_t index_of_right; \
	type element_right; \
	bool less_equal_right; \
	type element_left; \
	bool less_equal_left; \
	\
	/* It already must be the case that the node at `index` is greater than its parent, */\
	/* since that node came from the bottom of the heap. But it may not be less than or */\
	/* equal to its children. */\
	\
	index_of_left = index << 1; \
	index_of_right = (index << 1) + 1; \
	\
	pas_zero_memory(&element_right, sizeof(element_right)); \
	less_equal_right = true; \
	pas_zero_memory(&element_left, sizeof(element_left)); \
	less_equal_left = true; \
	\
	if (index_of_right <= size) { \
	element_right = *name##_get_ptr_by_index(min_heap, index_of_right); \
	less_equal_right = config.compare(&element_at_index, &element_right) <= 0; \
	} \
	\
	if (index_of_left <= size) { \
	element_left = *name##_get_ptr_by_index(min_heap, index_of_left); \
	less_equal_left = config.compare(&element_at_index, &element_left) <= 0; \
	} \
	\
	if (!less_equal_right \
	&& (less_equal_left \|\| config.compare(&element_right, &element_left) < 0)) { \
	config.set_index(&element_right, index); \
	\
	*name##_get_ptr_by_index(min_heap, index) = element_right; \
	\
	index = index_of_right; \
	continue; \
	} \
	\
	if (!less_equal_left) { \
	config.set_index(&element_left, index); \
	\
	*name##_get_ptr_by_index(min_heap, index) = element_left; \
	\
	index = index_of_left; \
	continue; \
	} \
	\
	done: \
	*name##_get_ptr_by_index(min_heap, index) = element_at_index; \
	config.set_index(&element_at_index, index); \
	config.set_index(&result, 0); \
	return result; \
	} \
	} \
	\
	PAS_UNUSED static inline type name##_get_min(name* min_heap) \
	{ \
	if (!min_heap->size) { \
	type result; \
	pas_zero_memory(&result, sizeof(type)); \
	return result; \
	} \
	\
	return *name##_get_ptr_by_index(min_heap, 1); \
	} \
	\
	PAS_UNUSED static inline type name##_take_min(name* min_heap) \
	{ \
	if (!min_heap->size) { \
	type result; \
	pas_zero_memory(&result, sizeof(type)); \
	return result; \
	} \
	\
	return name##_remove_by_index(min_heap, 1); \
	} \
	\
	PAS_UNUSED static inline void name##_remove(name* min_heap, \
	type element) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	size_t index = config.get_index(&element); \
	PAS_ASSERT(index); \
	PAS_ASSERT(!bcmp(name##_get_ptr_by_index(min_heap, index), &element, sizeof(type))); \
	name##_remove_by_index(min_heap, index); \
	} \
	\
	PAS_UNUSED static inline void name##_add( \
	name* min_heap, \
	type element, \
	const pas_allocation_config* allocation_config) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	size_t size; \
	size_t outline_capacity; \
	size_t index; \
	\
	size = min_heap->size; \
	outline_capacity = min_heap->outline_capacity; \
	\
	if (size >= (inline_capacity) + outline_capacity) { \
	type* new_outline_array; \
	size_t new_outline_capacity; \
	\
	PAS_ASSERT(size == (inline_capacity) + outline_capacity); \
	\
	new_outline_capacity = PAS_MAX((size_t)4, outline_capacity << 1); \
	PAS_ASSERT(new_outline_capacity > outline_capacity); \
	new_outline_array = (type*)allocation_config->allocate( \
	new_outline_capacity * sizeof(type), \
	#name "/outline_array", \
	pas_object_allocation, \
	allocation_config->arg); \
	\
	PAS_ASSERT(size < (inline_capacity) + new_outline_capacity); \
	\
	pas_zero_memory(new_outline_array, sizeof(type) * new_outline_capacity); \
	\
	memcpy(new_outline_array, \
	min_heap->outline_array, \
	(size - (inline_capacity)) * sizeof(type)); \
	\
	allocation_config->deallocate( \
	min_heap->outline_array, \
	outline_capacity * sizeof(type), \
	pas_object_allocation, \
	allocation_config->arg); \
	\
	outline_capacity = new_outline_capacity; \
	\
	min_heap->outline_array = new_outline_array; \
	min_heap->outline_capacity = new_outline_capacity; \
	} \
	\
	index = ++size; \
	PAS_ASSERT(size <= (inline_capacity) + outline_capacity); \
	\
	/* Doing this aids debugging. */ \
	pas_zero_memory(name##_get_ptr_by_index(min_heap, index), sizeof(type)); \
	\
	min_heap->size = size; \
	\
	while (index > 1) { \
	size_t index_of_parent; \
	type parent; \
	bool greater_equal_parent; \
	\
	index_of_parent = index >> 1; \
	\
	parent = *name##_get_ptr_by_index(min_heap, index_of_parent); \
	greater_equal_parent = config.compare(&element, &parent) >= 0; \
	\
	if (greater_equal_parent) \
	break; \
	\
	config.set_index(&parent, index); \
	\
	*name##_get_ptr_by_index(min_heap, index) = parent; \
	\
	index = index_of_parent; \
	} \
	\
	config.set_index(&element, index); \
	*name##_get_ptr_by_index(min_heap, index) = element; \
	} \
	\
	PAS_UNUSED static inline bool name##_is_index_still_ordered(name* min_heap, \
	size_t index, \
	type element) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	size_t size; \
	\
	size = min_heap->size; \
	\
	if (index > 1 \
	&& config.compare(&element, name##_get_ptr_by_index(min_heap, \
	index >> 1)) < 0) \
	return false; \
	\
	if ((index << 1) <= size \
	&& config.compare(&element, name##_get_ptr_by_index(min_heap, \
	index << 1)) > 0) \
	return false; \
	\
	if ((index << 1) + 1 <= size \
	&& config.compare(&element, name##_get_ptr_by_index(min_heap, \
	(index << 1) + 1)) > 0) \
	return false; \
	\
	return true; \
	} \
	\
	PAS_UNUSED static inline bool name##_is_still_ordered(name* min_heap, \
	type element) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	return name##_is_index_still_ordered( \
	min_heap, config.get_index(&element), element); \
	} \
	\
	PAS_UNUSED static inline void name##_update_order(name* min_heap, \
	type element, \
	const pas_allocation_config* allocation_config) \
	{ \
	name##_config config = {__VA_ARGS__}; \
	\
	if (config.get_index(&element)) { \
	if (name##_is_still_ordered(min_heap, element)) \
	return; \
	\
	name##_remove(min_heap, element); \
	} \
	\
	name##_add(min_heap, element, allocation_config); \
	} \
	\
	PAS_UNUSED static inline void name##_sort_descending(name* min_heap) \
	{ \
	size_t original_size = min_heap->size; \
	\
	while (min_heap->size) { \
	type value; \
	\
	value = name##_take_min(min_heap); \
	\
	*name##_get_ptr_by_index(min_heap, min_heap->size + 1) = value; \
	} \
	\
	/* At this point, this isn't a heap anymore. It's an array sorted in descending */ \
	/* order. */ \
	min_heap->size = original_size; \
	} \
	\
	struct pas_dummy

	PAS_END_EXTERN_C;

	#endif /* PAS_MIN_HEAP_H */