Mercurial Mercurial > openttd-ottdgrfs / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/queue.cpp
branchcpp_gui
changeset 6268 4b5241e5dd10
parent 5860 7fdc9b423ba1
child 6303 84c215fc8eb8
equal deleted inserted replaced
6267:7c8ec33959b1 6268:4b5241e5dd10 
     2 
     2 
     3 #include "stdafx.h"
 
     3 #include "stdafx.h"
 
     4 #include "openttd.h"
 
     4 #include "openttd.h"
 
     5 #include "queue.h"
 
     5 #include "queue.h"
 
     6 #include "helpers.hpp"
 
     6 #include "helpers.hpp"
 
     7 
       
     8 static void Stack_Clear(Queue* q, bool free_values)
 
       
     9 {
 
       
    10 	if (free_values) {
 
       
    11 		uint i;
 
       
    12 
       
    13 		for (i = 0; i < q->data.stack.size; i++) free(q->data.stack.elements[i]);
 
       
    14 	}
 
       
    15 	q->data.stack.size = 0;
 
       
    16 }
 
       
    17 
       
    18 static void Stack_Free(Queue* q, bool free_values)
 
       
    19 {
 
       
    20 	q->clear(q, free_values);
 
       
    21 	free(q->data.stack.elements);
 
       
    22 	if (q->freeq) free(q);
 
       
    23 }
 
       
    24 
       
    25 static bool Stack_Push(Queue* q, void* item, int priority)
 
       
    26 {
 
       
    27 	if (q->data.stack.size == q->data.stack.max_size) return false;
 
       
    28 	q->data.stack.elements[q->data.stack.size++] = item;
 
       
    29 	return true;
 
       
    30 }
 
       
    31 
       
    32 static void* Stack_Pop(Queue* q)
 
       
    33 {
 
       
    34 	if (q->data.stack.size == 0) return NULL;
 
       
    35 	return q->data.stack.elements[--q->data.stack.size];
 
       
    36 }
 
       
    37 
       
    38 static bool Stack_Delete(Queue* q, void* item, int priority)
 
       
    39 {
 
       
    40 	return false;
 
       
    41 }
 
       
    42 
       
    43 static Queue* init_stack(Queue* q, uint max_size)
 
       
    44 {
 
       
    45 	q->push = Stack_Push;
 
       
    46 	q->pop = Stack_Pop;
 
       
    47 	q->del = Stack_Delete;
 
       
    48 	q->clear = Stack_Clear;
 
       
    49 	q->free = Stack_Free;
 
       
    50 	q->data.stack.max_size = max_size;
 
       
    51 	q->data.stack.size = 0;
 
       
    52 	q->data.stack.elements = MallocT<void*>(max_size);
 
       
    53 	q->freeq = false;
 
       
    54 	return q;
 
       
    55 }
 
       
    56 
       
    57 Queue* new_Stack(uint max_size)
 
       
    58 {
 
       
    59 	Queue* q = MallocT<Queue>(1);
 
       
    60 
       
    61 	init_stack(q, max_size);
 
       
    62 	q->freeq = true;
 
       
    63 	return q;
 
       
    64 }
 
       
    65 
       
    66 /*
 
       
    67  * Fifo
 
       
    68  */
 
       
    69 
       
    70 static void Fifo_Clear(Queue* q, bool free_values)
 
       
    71 {
 
       
    72 	if (free_values) {
 
       
    73 		uint head = q->data.fifo.head;
 
       
    74 		uint tail = q->data.fifo.tail; /* cache for speed */
 
       
    75 
       
    76 		while (head != tail) {
 
       
    77 			free(q->data.fifo.elements[tail]);
 
       
    78 			tail = (tail + 1) % q->data.fifo.max_size;
 
       
    79 		}
 
       
    80 	}
 
       
    81 	q->data.fifo.head = 0;
 
       
    82 	q->data.fifo.tail = 0;
 
       
    83 }
 
       
    84 
       
    85 static void Fifo_Free(Queue* q, bool free_values)
 
       
    86 {
 
       
    87 	q->clear(q, free_values);
 
       
    88 	free(q->data.fifo.elements);
 
       
    89 	if (q->freeq) free(q);
 
       
    90 }
 
       
    91 
       
    92 static bool Fifo_Push(Queue* q, void* item, int priority)
 
       
    93 {
 
       
    94 	uint next = (q->data.fifo.head + 1) % q->data.fifo.max_size;
 
       
    95 
       
    96 	if (next == q->data.fifo.tail) return false;
 
       
    97 	q->data.fifo.elements[q->data.fifo.head] = item;
 
       
    98 
       
    99 	q->data.fifo.head = next;
 
       
   100 	return true;
 
       
   101 }
 
       
   102 
       
   103 static void* Fifo_Pop(Queue* q)
 
       
   104 {
 
       
   105 	void* result;
 
       
   106 
       
   107 	if (q->data.fifo.head == q->data.fifo.tail) return NULL;
 
       
   108 	result = q->data.fifo.elements[q->data.fifo.tail];
 
       
   109 
       
   110 	q->data.fifo.tail = (q->data.fifo.tail + 1) % q->data.fifo.max_size;
 
       
   111 	return result;
 
       
   112 }
 
       
   113 
       
   114 static bool Fifo_Delete(Queue* q, void* item, int priority)
 
       
   115 {
 
       
   116 	return false;
 
       
   117 }
 
       
   118 
       
   119 static Queue* init_fifo(Queue* q, uint max_size)
 
       
   120 {
 
       
   121 	q->push = Fifo_Push;
 
       
   122 	q->pop = Fifo_Pop;
 
       
   123 	q->del = Fifo_Delete;
 
       
   124 	q->clear = Fifo_Clear;
 
       
   125 	q->free = Fifo_Free;
 
       
   126 	q->data.fifo.max_size = max_size;
 
       
   127 	q->data.fifo.head = 0;
 
       
   128 	q->data.fifo.tail = 0;
 
       
   129 	q->data.fifo.elements = MallocT<void*>(max_size);
 
       
   130 	q->freeq = false;
 
       
   131 	return q;
 
       
   132 }
 
       
   133 
       
   134 Queue* new_Fifo(uint max_size)
 
       
   135 {
 
       
   136 	Queue* q = MallocT<Queue>(1);
 
       
   137 	init_fifo(q, max_size);
 
       
   138 	q->freeq = true;
 
       
   139 	return q;
 
       
   140 }
 
       
   141 
     7 
   142 
     8 
   143 /*
 
     9 /*
 
   144  * Insertion Sorter
 
    10  * Insertion Sorter
 
   145  */
 
    11  */
 
   159 }
 
    25 }
 
   160 
    26 
   161 static void InsSort_Free(Queue* q, bool free_values)
 
    27 static void InsSort_Free(Queue* q, bool free_values)
 
   162 {
 
    28 {
 
   163 	q->clear(q, free_values);
 
    29 	q->clear(q, free_values);
 
   164 	if (q->freeq) free(q);
 
       
   165 }
 
    30 }
 
   166 
    31 
   167 static bool InsSort_Push(Queue* q, void* item, int priority)
 
    32 static bool InsSort_Push(Queue* q, void* item, int priority)
 
   168 {
 
    33 {
 
   169 	InsSortNode* newnode = MallocT<InsSortNode>(1);
 
    34 	InsSortNode* newnode = MallocT<InsSortNode>(1);
 
   213 	q->pop = InsSort_Pop;
 
    78 	q->pop = InsSort_Pop;
 
   214 	q->del = InsSort_Delete;
 
    79 	q->del = InsSort_Delete;
 
   215 	q->clear = InsSort_Clear;
 
    80 	q->clear = InsSort_Clear;
 
   216 	q->free = InsSort_Free;
 
    81 	q->free = InsSort_Free;
 
   217 	q->data.inssort.first = NULL;
 
    82 	q->data.inssort.first = NULL;
 
   218 	q->freeq = false;
 
       
   219 }
 
       
   220 
       
   221 Queue* new_InsSort(void)
 
       
   222 {
 
       
   223 	Queue* q = MallocT<Queue>(1);
 
       
   224 
       
   225 	init_InsSort(q);
 
       
   226 	q->freeq = true;
 
       
   227 	return q;
 
       
   228 }
 
    83 }
 
   229 
    84 
   230 
    85 
   231 /*
 
    86 /*
 
   232  * Binary Heap
 
    87  * Binary Heap
 
   282 	for (i = 0; i < q->data.binaryheap.blocks; i++) {
 
   137 	for (i = 0; i < q->data.binaryheap.blocks; i++) {
 
   283 		if (q->data.binaryheap.elements[i] == NULL) break;
 
   138 		if (q->data.binaryheap.elements[i] == NULL) break;
 
   284 		free(q->data.binaryheap.elements[i]);
 
   139 		free(q->data.binaryheap.elements[i]);
 
   285 	}
 
   140 	}
 
   286 	free(q->data.binaryheap.elements);
 
   141 	free(q->data.binaryheap.elements);
 
   287 	if (q->freeq) free(q);
 
       
   288 }
 
   142 }
 
   289 
   143 
   290 static bool BinaryHeap_Push(Queue* q, void* item, int priority)
 
   144 static bool BinaryHeap_Push(Queue* q, void* item, int priority)
 
   291 {
 
   145 {
 
   292 #ifdef QUEUE_DEBUG
 
   146 #ifdef QUEUE_DEBUG
 
   428 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE
 
   282 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE
 
   429 	//   It autosizes when it runs out of memory
 
   283 	//   It autosizes when it runs out of memory
 
   430 	q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
 
   284 	q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
 
   431 	q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
 
   285 	q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
 
   432 	q->data.binaryheap.blocks = 1;
 
   286 	q->data.binaryheap.blocks = 1;
 
   433 	q->freeq = false;
 
       
   434 #ifdef QUEUE_DEBUG
 
   287 #ifdef QUEUE_DEBUG
 
   435 	printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
 
   288 	printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
 
   436 #endif
 
   289 #endif
 
   437 }
 
       
   438 
       
   439 Queue* new_BinaryHeap(uint max_size)
 
       
   440 {
 
       
   441 	Queue* q = MallocT<Queue>(1);
 
       
   442 
       
   443 	init_BinaryHeap(q, max_size);
 
       
   444 	q->freeq = true;
 
       
   445 	return q;
 
       
   446 }
 
   290 }
 
   447 
   291 
   448 // Because we don't want anyone else to bother with our defines
 
   292 // Because we don't want anyone else to bother with our defines
 
   449 #undef BIN_HEAP_ARR
 
   293 #undef BIN_HEAP_ARR
 
   450 
   294 
   467 	h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
 
   311 	h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
 
   468 #ifdef HASH_DEBUG
 
   312 #ifdef HASH_DEBUG
 
   469 	debug("Buckets = %p", h->buckets);
 
   313 	debug("Buckets = %p", h->buckets);
 
   470 #endif
 
   314 #endif
 
   471 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);
 
   315 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);
 
   472 	h->freeh = false;
 
       
   473 	for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
 
   316 	for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
 
   474 }
 
   317 }
 
   475 
   318 
   476 Hash* new_Hash(Hash_HashProc* hash, int num_buckets)
 
       
   477 {
 
       
   478 	Hash* h = MallocT<Hash>(1);
 
       
   479 
       
   480 	init_Hash(h, hash, num_buckets);
 
       
   481 	h->freeh = true;
 
       
   482 	return h;
 
       
   483 }
 
       
   484 
   319 
   485 void delete_Hash(Hash* h, bool free_values)
 
   320 void delete_Hash(Hash* h, bool free_values)
 
   486 {
 
   321 {
 
   487 	uint i;
 
   322 	uint i;
 
   488 
   323 
   509 	/* No need to free buckets_in_use, it is always allocated in one
 
   344 	/* No need to free buckets_in_use, it is always allocated in one
 
   510 	 * malloc with buckets */
 
   345 	 * malloc with buckets */
 
   511 #ifdef HASH_DEBUG
 
   346 #ifdef HASH_DEBUG
 
   512 	debug("Freeing Hash: %p", h);
 
   347 	debug("Freeing Hash: %p", h);
 
   513 #endif
 
   348 #endif
 
   514 	if (h->freeh) free(h);
 
       
   515 }
 
   349 }
 
   516 
   350 
   517 #ifdef HASH_STATS
 
   351 #ifdef HASH_STATS
 
   518 static void stat_Hash(const Hash* h)
 
   352 static void stat_Hash(const Hash* h)
 
   519 {
 
   353 {
openttd-ottdgrfs