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
branchcustombridgeheads
changeset 5650 aefc131bf5ce
parent 5649 55c8267c933f
child 5860 7fdc9b423ba1
equal deleted inserted replaced
5649:55c8267c933f 5650:aefc131bf5ce 
     1 /* $Id$ */
 
     1 /* $Id$ */
 
     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 
     7 
     7 static void Stack_Clear(Queue* q, bool free_values)
 
     8 static void Stack_Clear(Queue* q, bool free_values)
 
     8 {
 
     9 {
 
     9 	if (free_values) {
 
    10 	if (free_values) {
 
    10 		uint i;
 
    11 		uint i;
 
    46 	q->del = Stack_Delete;
 
    47 	q->del = Stack_Delete;
 
    47 	q->clear = Stack_Clear;
 
    48 	q->clear = Stack_Clear;
 
    48 	q->free = Stack_Free;
 
    49 	q->free = Stack_Free;
 
    49 	q->data.stack.max_size = max_size;
 
    50 	q->data.stack.max_size = max_size;
 
    50 	q->data.stack.size = 0;
 
    51 	q->data.stack.size = 0;
 
    51 	q->data.stack.elements = malloc(max_size * sizeof(*q->data.stack.elements));
 
    52 	MallocT(&q->data.stack.elements, max_size);
 
    52 	q->freeq = false;
 
    53 	q->freeq = false;
 
    53 	return q;
 
    54 	return q;
 
    54 }
 
    55 }
 
    55 
    56 
    56 Queue* new_Stack(uint max_size)
 
    57 Queue* new_Stack(uint max_size)
 
    57 {
 
    58 {
 
    58 	Queue* q = malloc(sizeof(*q));
 
    59 	Queue* q;
 
       
    60 	MallocT(&q, 1);
 
    59 
    61 
    60 	init_stack(q, max_size);
 
    62 	init_stack(q, max_size);
 
    61 	q->freeq = true;
 
    63 	q->freeq = true;
 
    62 	return q;
 
    64 	return q;
 
    63 }
 
    65 }
 
   123 	q->clear = Fifo_Clear;
 
   125 	q->clear = Fifo_Clear;
 
   124 	q->free = Fifo_Free;
 
   126 	q->free = Fifo_Free;
 
   125 	q->data.fifo.max_size = max_size;
 
   127 	q->data.fifo.max_size = max_size;
 
   126 	q->data.fifo.head = 0;
 
   128 	q->data.fifo.head = 0;
 
   127 	q->data.fifo.tail = 0;
 
   129 	q->data.fifo.tail = 0;
 
   128 	q->data.fifo.elements = malloc(max_size * sizeof(*q->data.fifo.elements));
 
   130 	MallocT(&q->data.fifo.elements, max_size);
 
   129 	q->freeq = false;
 
   131 	q->freeq = false;
 
   130 	return q;
 
   132 	return q;
 
   131 }
 
   133 }
 
   132 
   134 
   133 Queue* new_Fifo(uint max_size)
 
   135 Queue* new_Fifo(uint max_size)
 
   134 {
 
   136 {
 
   135 	Queue* q = malloc(sizeof(*q));
 
   137 	Queue* q;
 
       
   138 	MallocT(&q, 1);
 
   136 
   139 
   137 	init_fifo(q, max_size);
 
   140 	init_fifo(q, max_size);
 
   138 	q->freeq = true;
 
   141 	q->freeq = true;
 
   139 	return q;
 
   142 	return q;
 
   140 }
 
   143 }
 
   164 	if (q->freeq) free(q);
 
   167 	if (q->freeq) free(q);
 
   165 }
 
   168 }
 
   166 
   169 
   167 static bool InsSort_Push(Queue* q, void* item, int priority)
 
   170 static bool InsSort_Push(Queue* q, void* item, int priority)
 
   168 {
 
   171 {
 
   169 	InsSortNode* newnode = malloc(sizeof(*newnode));
 
   172 	InsSortNode* newnode;
 
       
   173 	MallocT(&newnode, 1);
 
   170 
   174 
   171 	if (newnode == NULL) return false;
 
   175 	if (newnode == NULL) return false;
 
   172 	newnode->item = item;
 
   176 	newnode->item = item;
 
   173 	newnode->priority = priority;
 
   177 	newnode->priority = priority;
 
   174 	if (q->data.inssort.first == NULL ||
 
   178 	if (q->data.inssort.first == NULL ||
 
   218 	q->freeq = false;
 
   222 	q->freeq = false;
 
   219 }
 
   223 }
 
   220 
   224 
   221 Queue* new_InsSort(void)
 
   225 Queue* new_InsSort(void)
 
   222 {
 
   226 {
 
   223 	Queue* q = malloc(sizeof(*q));
 
   227 	Queue* q;
 
       
   228 	MallocT(&q, 1);
 
   224 
   229 
   225 	init_InsSort(q);
 
   230 	init_InsSort(q);
 
   226 	q->freeq = true;
 
   231 	q->freeq = true;
 
   227 	return q;
 
   232 	return q;
 
   228 }
 
   233 }
 
   297 	assert(q->data.binaryheap.size < q->data.binaryheap.max_size);
 
   302 	assert(q->data.binaryheap.size < q->data.binaryheap.max_size);
 
   298 
   303 
   299 	if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
 
   304 	if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
 
   300 		/* The currently allocated blocks are full, allocate a new one */
 
   305 		/* The currently allocated blocks are full, allocate a new one */
 
   301 		assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
 
   306 		assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
 
   302 		q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(*q->data.binaryheap.elements[0]));
 
   307 		MallocT(&q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS], BINARY_HEAP_BLOCKSIZE);
 
   303 		q->data.binaryheap.blocks++;
 
   308 		q->data.binaryheap.blocks++;
 
   304 #ifdef QUEUE_DEBUG
 
   309 #ifdef QUEUE_DEBUG
 
   305 		printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks *  BINARY_HEAP_BLOCKSIZE);
 
   310 		printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks *  BINARY_HEAP_BLOCKSIZE);
 
   306 #endif
 
   311 #endif
 
   307 	}
 
   312 	}
 
   425 	q->free = BinaryHeap_Free;
 
   430 	q->free = BinaryHeap_Free;
 
   426 	q->data.binaryheap.max_size = max_size;
 
   431 	q->data.binaryheap.max_size = max_size;
 
   427 	q->data.binaryheap.size = 0;
 
   432 	q->data.binaryheap.size = 0;
 
   428 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE
 
   433 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE
 
   429 	//   It autosizes when it runs out of memory
 
   434 	//   It autosizes when it runs out of memory
 
   430 	q->data.binaryheap.elements = calloc((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1, sizeof(*q->data.binaryheap.elements));
 
   435 	CallocT(&q->data.binaryheap.elements, (max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
 
   431 	q->data.binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(*q->data.binaryheap.elements[0]));
 
   436 	MallocT(&q->data.binaryheap.elements[0], BINARY_HEAP_BLOCKSIZE);
 
   432 	q->data.binaryheap.blocks = 1;
 
   437 	q->data.binaryheap.blocks = 1;
 
   433 	q->freeq = false;
 
   438 	q->freeq = false;
 
   434 #ifdef QUEUE_DEBUG
 
   439 #ifdef QUEUE_DEBUG
 
   435 	printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
 
   440 	printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
 
   436 #endif
 
   441 #endif
 
   437 }
 
   442 }
 
   438 
   443 
   439 Queue* new_BinaryHeap(uint max_size)
 
   444 Queue* new_BinaryHeap(uint max_size)
 
   440 {
 
   445 {
 
   441 	Queue* q = malloc(sizeof(*q));
 
   446 	Queue* q;
 
       
   447 	MallocT(&q, 1);
 
   442 
   448 
   443 	init_BinaryHeap(q, max_size);
 
   449 	init_BinaryHeap(q, max_size);
 
   444 	q->freeq = true;
 
   450 	q->freeq = true;
 
   445 	return q;
 
   451 	return q;
 
   446 }
 
   452 }
 
   462 	debug("Allocated hash: %p", h);
 
   468 	debug("Allocated hash: %p", h);
 
   463 #endif
 
   469 #endif
 
   464 	h->hash = hash;
 
   470 	h->hash = hash;
 
   465 	h->size = 0;
 
   471 	h->size = 0;
 
   466 	h->num_buckets = num_buckets;
 
   472 	h->num_buckets = num_buckets;
 
   467 	h->buckets = malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
 
   473 	h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
 
   468 #ifdef HASH_DEBUG
 
   474 #ifdef HASH_DEBUG
 
   469 	debug("Buckets = %p", h->buckets);
 
   475 	debug("Buckets = %p", h->buckets);
 
   470 #endif
 
   476 #endif
 
   471 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);
 
   477 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);
 
   472 	h->freeh = false;
 
   478 	h->freeh = false;
 
   473 	for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
 
   479 	for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
 
   474 }
 
   480 }
 
   475 
   481 
   476 Hash* new_Hash(Hash_HashProc* hash, int num_buckets)
 
   482 Hash* new_Hash(Hash_HashProc* hash, int num_buckets)
 
   477 {
 
   483 {
 
   478 	Hash* h = malloc(sizeof(*h));
 
   484 	Hash* h;
 
       
   485 	MallocT(&h, 1);
 
   479 
   486 
   480 	init_Hash(h, hash, num_buckets);
 
   487 	init_Hash(h, hash, num_buckets);
 
   481 	h->freeh = true;
 
   488 	h->freeh = true;
 
   482 	return h;
 
   489 	return h;
 
   483 }
 
   490 }
 
   707 		uint hash = h->hash(key1, key2);
 
   714 		uint hash = h->hash(key1, key2);
 
   708 		h->buckets_in_use[hash] = true;
 
   715 		h->buckets_in_use[hash] = true;
 
   709 		node = h->buckets + hash;
 
   716 		node = h->buckets + hash;
 
   710 	} else {
 
   717 	} else {
 
   711 		/* Add it after prev */
 
   718 		/* Add it after prev */
 
   712 		node = malloc(sizeof(*node));
 
   719 		MallocT(&node, 1);
 
   713 		prev->next = node;
 
   720 		prev->next = node;
 
   714 	}
 
   721 	}
 
   715 	node->next = NULL;
 
   722 	node->next = NULL;
 
   716 	node->key1 = key1;
 
   723 	node->key1 = key1;
 
   717 	node->key2 = key2;
 
   724 	node->key2 = key2;
openttd-ottdgrfs