Crossfire Server, Trunk
minheap.cpp
Go to the documentation of this file.
1 /*
2  * Crossfire -- cooperative multi-player graphical RPG and adventure game
3  *
4  * Copyright (c) 1999-2021 The Crossfire Development Team
5  * Copyright (c) 1992 Frank Tore Johansen
6  *
7  * Crossfire is free software and comes with ABSOLUTELY NO WARRANTY. You are
8  * welcome to redistribute it under certain conditions. For details, please
9  * see COPYING and LICENSE.
10  *
11  * The authors can be reached via e-mail at <crossfire@metalforge.org>.
12  */
13 
22 #include "minheap.h"
23 #include "global.h"
24 
25 #include <stdlib.h>
26 
34 static inline int minheap_get_left(int index) {
35  // We can assert the last digit is 0 after a left shift,
36  // so we can do a bitwise-or instead of addition to save time.
37  return (index << 1) | 1;
38 }
39 
47 static inline int minheap_get_right(int index) {
48  return (index << 1) + 2;
49 }
50 
59 static inline int minheap_get_parent(int index) {
60  return index ? (index - 1) >> 1 : -1;
61 }
62 
71 static void minheap_normalize(MinHeap *heap) {
72  int at = 0;
73  // The measurements of the three items being compared.
74  // [0] -- parent
75  // [1] -- left child
76  // [2] -- right child
77  int val[3];
78  // Handle some special cases for when the heap is small.
79  if (heap->len == 1)
80  return;
81  while (at < heap->len) {
82  int left = minheap_get_left(at),
83  right = minheap_get_right(at),
84  minchild;
85  // Break out of the loop if we hit the bottom of the heap.
86  if (left >= heap->len)
87  break;
88  val[0] = heap->get_measure(heap->arr[at]);
89  val[1] = heap->get_measure(heap->arr[left]);
90  // Check to see if there's the right child as well.
91  if (right < heap->len) {
92  // If there is the ight child, determine which child is the smaller of the two.
93  val[2] = heap->get_measure(heap->arr[right]);
94  if (val[1] < val[2])
95  minchild = left;
96  else
97  minchild = right;
98  }
99  // If no right child, the left will be the smaller one.
100  else
101  minchild = left;
102  // If the smaller child is smaller than the value we are percolating, swap them.
103  if (val[0] <= (minchild == left ? val[1] : val[2]))
104  break;
105  void *tmp = heap->arr[at];
106  heap->arr[at] = heap->arr[minchild];
107  heap->arr[minchild] = tmp;
108  // Prepare for next iteration
109  at = minchild;
110  }
111 }
112 
129 MinHeap *minheap_init(int amt, int (*measure_func)(const void *), void (*cleanup_func)(void *)){
130  MinHeap *newheap = static_cast<MinHeap *>(malloc(sizeof(MinHeap)));
131  if (!newheap)
133  newheap->arr = static_cast<void **>(malloc(amt * sizeof(void *)));
134  if (!newheap->arr)
136  newheap->len = 0;
137  newheap->capacity = amt;
138  newheap->get_measure = measure_func;
139  newheap->element_cleanup = cleanup_func;
140  return newheap;
141 }
142 
162 void minheap_init_static(MinHeap *heap, void **arr, int amt, int (*measure_func)(const void *)) {
163  if (heap == NULL)
164  return;
165  heap->arr = arr;
166  heap->len = 0;
167  heap->capacity = amt;
168  heap->get_measure = measure_func;
169  heap->element_cleanup = NULL;
170 }
171 
184 int minheap_insert(MinHeap *heap, void *ob) {
185  if (heap->len == heap->capacity)
186  return -1;
187  // To insert, we pull down elements deeper into the heap,
188  // and then put the new element at the top, and percolate it down.
189  int at = heap->len++;
190  while (at) {
191  int parent = minheap_get_parent(at);
192  heap->arr[at] = heap->arr[parent];
193  at = parent;
194  }
195  heap->arr[0] = ob;
196  minheap_normalize(heap);
197  return 0;
198 }
199 
209 void *minheap_remove(MinHeap *heap) {
210  if (heap->len == 0)
211  return NULL;
212  void *removed = heap->arr[0];
213  // Insert the last element of the heap back into the top,
214  // and percolate down. The previous spot it existed is no longer part of the heap.
215  heap->arr[0] = heap->arr[--heap->len];
216  minheap_normalize(heap);
217  return removed;
218 }
219 
226 void minheap_free(MinHeap *to_free){
227  // If the data elements have a cleanup method provided,
228  // then clean them up. Otherwise just deallocate our references.
229  if (to_free->element_cleanup) {
230  for (int i = 0; i < to_free->len; ++i)
231  to_free->element_cleanup(to_free->arr[i]);
232  }
233  free(to_free->arr);
234  free(to_free);
235 }
MinHeap::capacity
int capacity
Definition: minheap.h:22
global.h
minheap_get_parent
static int minheap_get_parent(int index)
Definition: minheap.cpp:59
MinHeap::get_measure
int(* get_measure)(const void *)
Definition: minheap.h:25
MinHeap
Definition: minheap.h:16
guildjoin.ob
ob
Definition: guildjoin.py:42
Ice.tmp
int tmp
Definition: Ice.py:207
minheap_normalize
static void minheap_normalize(MinHeap *heap)
Definition: minheap.cpp:71
minheap_free
void minheap_free(MinHeap *to_free)
Definition: minheap.cpp:226
minheap.h
minheap_init
MinHeap * minheap_init(int amt, int(*measure_func)(const void *), void(*cleanup_func)(void *))
Definition: minheap.cpp:129
MinHeap::len
int len
Definition: minheap.h:20
fatal
void fatal(enum fatal_error err)
Definition: utils.cpp:590
minheap_remove
void * minheap_remove(MinHeap *heap)
Definition: minheap.cpp:209
npc_dialog.index
int index
Definition: npc_dialog.py:102
minheap_init_static
void minheap_init_static(MinHeap *heap, void **arr, int amt, int(*measure_func)(const void *))
Definition: minheap.cpp:162
MinHeap::element_cleanup
void(* element_cleanup)(void *)
Definition: minheap.h:29
minheap_get_right
static int minheap_get_right(int index)
Definition: minheap.cpp:47
minheap_insert
int minheap_insert(MinHeap *heap, void *ob)
Definition: minheap.cpp:184
OUT_OF_MEMORY
@ OUT_OF_MEMORY
Definition: define.h:48
MinHeap::arr
void ** arr
Definition: minheap.h:18
minheap_get_left
static int minheap_get_left(int index)
Definition: minheap.cpp:34