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