1 #include "stdafx.h"

     2 #include "ttd.h"

     3 #include "queue.h"

     4 

     5 void Stack_Clear(Queue* q, bool free_values)

     6 {

     7 	uint i;

     8 	if (free_values)

     9 		for (i=0;i<q->stack.size;i++)

    10 			free(q->stack.elements[i]);

    11 	q->stack.size = 0;

    12 }

    13 

    14 void Stack_Free(Queue* q, bool free_values)

    15 {

    16 	q->clear(q, free_values);

    17 	free(q->stack.elements);

    18 	if (q->freeq)

    19 		free(q);

    20 }

    21 

    22 bool Stack_Push(Queue* q, void* item, int priority) {

    23 	if (q->stack.size == q->stack.max_size)

    24 		return false;

    25 	q->stack.elements[q->stack.size++] = item;

    26 	return true;

    27 }

    28 

    29 void* Stack_Pop(Queue* q) {

    30 	void* result;

    31 	if (q->stack.size == 0)

    32 		return NULL;

    33 	result = q->stack.elements[--q->stack.size];

    34 

    35 	return result;

    36 }

    37 

    38 bool Stack_Delete(Queue* q, void* item, int priority)

    39 {

    40 	return false;

    41 }

    42 

    43 Queue* init_stack(Queue* q, uint max_size) {

    44 	q->push = Stack_Push;

    45 	q->pop = Stack_Pop;

    46 	q->del = Stack_Delete;

    47 	q->clear = Stack_Clear;

    48 	q->free = Stack_Free;

    49 	q->stack.max_size = max_size;

    50 	q->stack.size = 0;

    51 	q->stack.elements = malloc(max_size * sizeof(void*));

    52 	q->freeq = false;

    53 	return q;

    54 }

    55 

    56 Queue* new_Stack(uint max_size)

    57 {

    58 	Queue* q = malloc(sizeof(Queue));

    59 	init_stack(q, max_size);

    60 	q->freeq = true;

    61 	return q;

    62 }

    63 

    64 /*

    65  * Fifo

    66  */

    67 

    68 void Fifo_Clear(Queue* q, bool free_values)

    69 {

    70 	uint head, tail;

    71 	if (free_values) {

    72 		head = q->fifo.head;

    73 		tail = q->fifo.tail; /* cache for speed */

    74 		while (head != tail) {

    75 			free(q->fifo.elements[tail]);

    76 			tail = (tail + 1) % q->fifo.max_size;

    77 		}

    78 	}

    79 	q->fifo.head = q->fifo.tail = 0;

    80 }

    81 

    82 void Fifo_Free(Queue* q, bool free_values)

    83 {

    84 	q->clear(q, free_values);

    85 	free(q->fifo.elements);

    86 	if (q->freeq)

    87 		free(q);

    88 }

    89 

    90 bool Fifo_Push(Queue* q, void* item, int priority) {

    91 	uint next = (q->fifo.head + 1) % q->fifo.max_size;

    92 	if (next == q->fifo.tail)

    93 		return false;

    94 	q->fifo.elements[q->fifo.head] = item;

    95 

    96 

    97 	q->fifo.head = next;

    98 	return true;

    99 }

   100 

   101 void* Fifo_Pop(Queue* q) {

   102 	void* result;

   103 	if (q->fifo.head == q->fifo.tail)

   104 		return NULL;

   105 	result = q->fifo.elements[q->fifo.tail];

   106 

   107 

   108 	q->fifo.tail = (q->fifo.tail + 1) % q->fifo.max_size;

   109 	return result;

   110 }

   111 

   112 bool Fifo_Delete(Queue* q, void* item, int priority)

   113 {

   114 	return false;

   115 }

   116 

   117 Queue* init_fifo(Queue* q, uint max_size) {

   118 	q->push = Fifo_Push;

   119 	q->pop = Fifo_Pop;

   120 	q->del = Fifo_Delete;

   121 	q->clear = Fifo_Clear;

   122 	q->free = Fifo_Free;

   123 	q->fifo.max_size = max_size;

   124 	q->fifo.head = 0;

   125 	q->fifo.tail = 0;

   126 	q->fifo.elements = malloc(max_size * sizeof(void*));

   127 	q->freeq = false;

   128 	return q;

   129 }

   130 

   131 Queue* new_Fifo(uint max_size)

   132 {

   133 	Queue* q = malloc(sizeof(Queue));

   134 	init_fifo(q, max_size);

   135 	q->freeq = true;

   136 	return q;

   137 }

   138 

   139 

   140 /*

   141  * Insertion Sorter

   142  */

   143 

   144 void InsSort_Clear(Queue* q, bool free_values) {

   145 	InsSortNode* node = q->inssort.first;

   146 	InsSortNode* prev;

   147 	while (node != NULL) {

   148 		if (free_values)

   149 			free(node->item);

   150 		prev = node;

   151 		node = node->next;

   152 		free(prev);

   153 		

   154 	}

   155 	q->inssort.first = NULL;

   156 }

   157 

   158 void InsSort_Free(Queue* q, bool free_values)

   159 {

   160 	q->clear(q, free_values);

   161 	if (q->freeq)

   162 		free(q);

   163 }

   164 

   165 bool InsSort_Push(Queue* q, void* item, int priority) {

   166 	InsSortNode* newnode = malloc(sizeof(InsSortNode));

   167 	if (newnode == NULL) return false;

   168 	newnode->item = item;

   169 	newnode->priority = priority;

   170 	if (q->inssort.first == NULL || q->inssort.first->priority >= priority) {

   171 		newnode->next = q->inssort.first;

   172 		q->inssort.first = newnode;

   173 	} else {

   174 		InsSortNode* node = q->inssort.first;

   175 		while( node != NULL ) {

   176 			if (node->next == NULL || node->next->priority >= priority) {

   177 				newnode->next = node->next;

   178 				node->next = newnode;

   179 				break;

   180 			}

   181 			node = node->next;

   182 		}

   183 	}

   184 	return true;

   185 }

   186 

   187 void* InsSort_Pop(Queue* q) {

   188 	InsSortNode* node = q->inssort.first;

   189 	void* result;

   190 	if (node == NULL)

   191 		return NULL;

   192 	result = node->item;

   193 	q->inssort.first = q->inssort.first->next;

   194 	if (q->inssort.first)

   195 		assert(q->inssort.first->priority >= node->priority);

   196 	free(node);

   197 	return result;

   198 }

   199 

   200 bool InsSort_Delete(Queue* q, void* item, int priority)

   201 {

   202 	return false;

   203 }

   204 

   205 void init_InsSort(Queue* q) {

   206 	q->push = InsSort_Push;

   207 	q->pop = InsSort_Pop;

   208 	q->del = InsSort_Delete;

   209 	q->clear = InsSort_Clear;

   210 	q->free = InsSort_Free;

   211 	q->inssort.first = NULL;

   212 	q->freeq = false;

   213 }

   214 

   215 Queue* new_InsSort() {

   216 	Queue* q = malloc(sizeof(Queue));

   217 	init_InsSort(q);

   218 	q->freeq = true;

   219 	return q;

   220 }

   221 

   222 

   223 /*

   224  * Binary Heap

   225  * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm

   226  */

   227 

   228 #define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

   229 #define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE-1)

   230 

   231 // To make our life easy, we make the next define

   232 //  Because Binary Heaps works with array from 1 to n,

   233 //  and C with array from 0 to n-1, and we don't like typing

   234 //  q->binaryheap.elements[i-1] every time, we use this define.

   235 #define BIN_HEAP_ARR(i) q->binaryheap.elements[((i)-1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i)-1) & BINARY_HEAP_BLOCKSIZE_MASK]

   236 

   237 void BinaryHeap_Clear(Queue* q, bool free_values)

   238 {

   239 	/* Free all items if needed and free all but the first blocks of

   240 	 * memory */

   241 	uint i,j;

   242 	for (i=0;i<q->binaryheap.blocks;i++) {

   243 		if (q->binaryheap.elements[i] == NULL) {

   244 			/* No more allocated blocks */

   245 			break;

   246 		}

   247 		/* For every allocated block */

   248 		if (free_values)

   249 			for (j=0;j<(1<<BINARY_HEAP_BLOCKSIZE_BITS);j++) {

   250 				/* For every element in the block */

   251 				if ((q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i

   252 					&& (q->binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j)

   253 					break; /* We're past the last element */

   254 				free(q->binaryheap.elements[i][j].item);

   255 			}

   256 		if (i != 0) {

   257 			/* Leave the first block of memory alone */

   258 			free(q->binaryheap.elements[i]);

   259 			q->binaryheap.elements[i] = NULL;

   260 		}

   261 	}

   262 	q->binaryheap.size = 0;

   263 	q->binaryheap.blocks = 1;

   264 }

   265 

   266 void BinaryHeap_Free(Queue* q, bool free_values)

   267 {

   268 	uint i;

   269 	q->clear(q, free_values);

   270 	for (i=0;i<q->binaryheap.blocks;i++) {

   271 		if (q->binaryheap.elements[i] == NULL)

   272 			break;

   273 		free(q->binaryheap.elements[i]);

   274 	}

   275 	if (q->freeq)

   276 		free(q);

   277 }

   278 

   279 bool BinaryHeap_Push(Queue* q, void* item, int priority) {

   280 	#ifdef QUEUE_DEBUG

   281 			printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->binaryheap.size);

   282 	#endif

   283 	if (q->binaryheap.size == q->binaryheap.max_size)

   284 		return false;

   285 	assert(q->binaryheap.size < q->binaryheap.max_size);

   286 	

   287 	if (q->binaryheap.elements[q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {

   288 		/* The currently allocated blocks are full, allocate a new one */

   289 		assert((q->binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);

   290 		q->binaryheap.elements[q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode));

   291 		q->binaryheap.blocks++;

   292 #ifdef QUEUE_DEBUG

   293 		printf("[BinaryHeap] Increasing size of elements to %d nodes\n",q->binaryheap.blocks *  BINARY_HEAP_BLOCKSIZE);

   294 #endif

   295 	}

   296 

   297 	// Add the item at the end of the array

   298 	BIN_HEAP_ARR(q->binaryheap.size+1).priority = priority;

   299 	BIN_HEAP_ARR(q->binaryheap.size+1).item = item;

   300 	q->binaryheap.size++;

   301 

   302 	// Now we are going to check where it belongs. As long as the parent is

   303 	// bigger, we switch with the parent

   304 	{

   305 		int i, j;

   306 		BinaryHeapNode temp;

   307 		i = q->binaryheap.size;

   308 		while (i > 1) {

   309 			// Get the parent of this object (divide by 2)

   310 			j = i / 2;

   311 			// Is the parent bigger then the current, switch them

   312 			if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) {

   313 				temp = BIN_HEAP_ARR(j);

   314 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   315 				BIN_HEAP_ARR(i) = temp;

   316 				i = j;

   317 			} else {

   318 				// It is not, we're done!

   319 				break;

   320 			}

   321 		}

   322 	}

   323 

   324 	return true;

   325 }

   326 

   327 bool BinaryHeap_Delete(Queue* q, void* item, int priority)

   328 {

   329 	#ifdef QUEUE_DEBUG

   330 			printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->binaryheap.size);

   331 	#endif

   332 	uint i = 0;

   333 	// First, we try to find the item..

   334 	do {

   335 		if (BIN_HEAP_ARR(i+1).item == item) break;

   336 		i++;

   337 	} while (i < q->binaryheap.size);

   338 	// We did not find the item, so we return false

   339 	if (i == q->binaryheap.size) return false;

   340 

   341 	// Now we put the last item over the current item while decreasing the size of the elements

   342 	q->binaryheap.size--;

   343 	BIN_HEAP_ARR(i+1) = BIN_HEAP_ARR(q->binaryheap.size+1);

   344 

   345 	// Now the only thing we have to do, is resort it..

   346 	// On place i there is the item to be sorted.. let's start there

   347 	{

   348 		uint j;

   349 		BinaryHeapNode temp;

   350 		// Because of the fast that Binary Heap uses array from 1 to n, we need to increase

   351 		//   i with 1

   352 		i++;

   353 

   354 		for (;;) {

   355 			j = i;

   356 			// Check if we have 2 childs

   357 			if (2*j+1 <= q->binaryheap.size) {

   358 				// Is this child smaller then the parent?

   359 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) {i = 2*j; }

   360 				// Yes, we _need_ to use i here, not j, because we want to have the smallest child

   361 				//  This way we get that straight away!

   362 				if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2*j+1).priority) { i = 2*j+1; }

   363 			// Do we have one child?

   364 			} else if (2*j <= q->binaryheap.size) {

   365 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) { i = 2*j; }

   366 			}

   367 

   368 			// One of our childs is smaller then we are, switch

   369 			if (i != j) {

   370 				temp = BIN_HEAP_ARR(j);

   371 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   372 				BIN_HEAP_ARR(i) = temp;

   373 			} else {

   374 				// None of our childs is smaller, so we stay here.. stop :)

   375 				break;

   376 			}

   377 		}

   378 	}

   379 

   380 	return true;

   381 }

   382 

   383 void* BinaryHeap_Pop(Queue* q) {

   384 	#ifdef QUEUE_DEBUG

   385 			printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->binaryheap.size);

   386 	#endif

   387 	void* result;

   388 	if (q->binaryheap.size == 0)

   389 		return NULL;

   390 

   391 	// The best item is always on top, so give that as result

   392 	result = BIN_HEAP_ARR(1).item;

   393 	// And now we should get ride of this item...

   394 	BinaryHeap_Delete(q,BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority);

   395 

   396 	return result;

   397 }

   398 

   399 void init_BinaryHeap(Queue* q, uint max_size)

   400 {

   401 	assert(q);

   402 	q->push = BinaryHeap_Push;

   403 	q->pop = BinaryHeap_Pop;

   404 	q->del = BinaryHeap_Delete;

   405 	q->clear = BinaryHeap_Clear;

   406 	q->free = BinaryHeap_Free;

   407 	q->binaryheap.max_size = max_size;

   408 	q->binaryheap.size = 0;

   409 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   410 	//   It autosizes when it runs out of memory

   411 	q->binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE) + 1);

   412 	q->binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode));

   413 	q->binaryheap.blocks = 1;

   414 	q->freeq = false;

   415 #ifdef QUEUE_DEBUG

   416 		printf("[BinaryHeap] Initial size of elements is %d nodes\n",(1024));

   417 #endif

   418 }

   419 

   420 Queue* new_BinaryHeap(uint max_size) {

   421 	Queue* q = malloc(sizeof(Queue));

   422 	init_BinaryHeap(q, max_size);

   423 	q->freeq = true;

   424 	return q;

   425 }

   426 

   427 // Because we don't want anyone else to bother with our defines

   428 #undef BIN_HEAP_ARR

   429 

   430 /*

   431  * Hash

   432  */

   433 

   434 void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets) {

   435 	/* Allocate space for the Hash, the buckets and the bucket flags */

   436 	int i;

   437 	assert(h);

   438 	#ifdef HASH_DEBUG

   439 	debug("Allocated hash: %p", h);

   440 	#endif

   441 	h->hash = hash;

   442 	h->size = 0;

   443 	h->num_buckets = num_buckets;

   444 	h->buckets = malloc(num_buckets * (sizeof(HashNode) + sizeof(bool)));

   445 	#ifdef HASH_DEBUG

   446 	debug("Buckets = %p", h->buckets);

   447 	#endif

   448 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);

   449 	h->freeh = false;

   450 	for (i=0;i<num_buckets;i++)

   451 		h->buckets_in_use[i] = false;

   452 }

   453 

   454 Hash* new_Hash(Hash_HashProc* hash, int num_buckets) {

   455 	Hash* h = malloc(sizeof(Hash));

   456 	init_Hash(h, hash, num_buckets);

   457 	h->freeh = true;

   458 	return h;

   459 }

   460 

   461 void delete_Hash(Hash* h, bool free_values) {

   462 	uint i;

   463 	/* Iterate all buckets */

   464 	for (i=0;i<h->num_buckets;i++)

   465 	{

   466 		if (h->buckets_in_use[i]) {

   467 			HashNode* node;

   468 			/* Free the first value */

   469 			if (free_values) 

   470 				free(h->buckets[i].value);

   471 			node = h->buckets[i].next;

   472 			while (node != NULL) {

   473 				HashNode* prev = node;

   474 				node = node->next;

   475 				/* Free the value */

   476 				if (free_values) 

   477 					free(prev->value);

   478 				/* Free the node */

   479 				free(prev);

   480 			}

   481 		}

   482 	}

   483 	free(h->buckets);

   484 	/* No need to free buckets_in_use, it is always allocated in one

   485 	 * malloc with buckets */

   486 	#ifdef HASH_DEBUG

   487 	debug("Freeing Hash: %p", h);

   488 	#endif

   489 	if (h->freeh)

   490 		free(h);

   491 }

   492 

   493 void clear_Hash(Hash* h, bool free_values)

   494 {

   495 	uint i;

   496 	HashNode* node;

   497 	/* Iterate all buckets */

   498 	for (i=0;i<h->num_buckets;i++)

   499 	{

   500 		if (h->buckets_in_use[i]) {

   501 			h->buckets_in_use[i] = false;

   502 			/* Free the first value */

   503 			if (free_values)

   504 				free(h->buckets[i].value);

   505 			node = h->buckets[i].next;

   506 			while (node != NULL) {

   507 				HashNode* prev = node;

   508 				node = node->next;

   509 				if (free_values)

   510 			 		free(prev->value);

   511 				free(prev);

   512 			}

   513 		}

   514 	}

   515 	h->size = 0;

   516 }

   517 

   518 /* Finds the node that that saves this key pair. If it is not

   519  * found, returns NULL. If it is found, *prev is set to the

   520  * node before the one found, or if the node found was the first in the bucket

   521  * to NULL. If it is not found, *prev is set to the last HashNode in the

   522  * bucket, or NULL if it is empty. prev can also be NULL, in which case it is

   523  * not used for output.

   524  */

   525 HashNode* Hash_FindNode(Hash* h, uint key1, uint key2, HashNode** prev_out) {

   526 	uint hash = h->hash(key1, key2);

   527 	HashNode* result = NULL;

   528 	#ifdef HASH_DEBUG

   529 	debug("Looking for %u, %u", key1, key2);

   530 	#endif

   531 	/* Check if the bucket is empty */

   532 	if (!h->buckets_in_use[hash]) {

   533 		if (prev_out)

   534 			*prev_out = NULL;

   535 		result = NULL;

   536 	/* Check the first node specially */

   537 	} else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) {

   538 		/* Save the value */

   539 		result = h->buckets + hash;

   540 		if (prev_out)

   541 			*prev_out = NULL;

   542 	#ifdef HASH_DEBUG

   543 		debug("Found in first node: %p", result);

   544 	#endif

   545 	/* Check all other nodes */

   546 	} else {

   547 		HashNode* prev = h->buckets + hash;

   548 		HashNode* node = prev->next;

   549 		while (node != NULL) {

   550 			if (node->key1 == key1 && node->key2 == key2) {

   551 				/* Found it */

   552 				result = node;

   553 	#ifdef HASH_DEBUG

   554 				debug("Found in other node: %p", result);

   555 	#endif

   556 				break;

   557 			}

   558 			prev = node;

   559 			node = node->next;

   560 		}

   561 		if (prev_out)

   562 			*prev_out = prev;

   563 	}

   564 	#ifdef HASH_DEBUG

   565 	if (result == NULL)

   566 		debug("Not found");

   567 	#endif

   568 	return result;

   569 }

   570 

   571 void* Hash_Delete(Hash* h, uint key1, uint key2) {

   572 	void* result;

   573 	HashNode* prev; /* Used as output var for below function call */

   574 	HashNode* node = Hash_FindNode(h, key1, key2, &prev);

   575 

   576 	if (node == NULL) {

   577 		/* not found */

   578 		result = NULL;

   579 	} else if (prev == NULL) {

   580 		/* It is in the first node, we can't free that one, so we free

   581 		 * the next one instead (if there is any)*/

   582 		/* Save the value */

   583 		result = node->value;

   584 		if (node->next != NULL) {

   585 			HashNode* next = node->next;

   586 			/* Copy the second to the first */

   587 			*node = *next;

   588 			/* Free the second */

   589 		#ifndef NOFREE

   590 			free(next);

   591 		#endif

   592 		} else {

   593 			/* This was the last in this bucket */

   594 			/* Mark it as empty */

   595 			uint hash = h->hash(key1, key2);

   596 			h->buckets_in_use[hash] = false;

   597 		}

   598 	} else {

   599 		/* It is in another node */

   600 		/* Save the value */

   601 		result = node->value;

   602 		/* Link previous and next nodes */

   603 		prev->next = node->next;

   604 		/* Free the node */

   605 		#ifndef NOFREE

   606 		free(node);

   607 		#endif

   608 	}

   609 	if (result != NULL)

   610 		h->size--;

   611 	return result;

   612 }

   613 

   614 

   615 void* Hash_Set(Hash* h, uint key1, uint key2, void* value) {

   616 	HashNode* prev;

   617 	HashNode* node = Hash_FindNode(h, key1, key2, &prev);

   618 	void* result = NULL;

   619 	if (node != NULL) {

   620 		/* Found it */

   621 		result = node->value;

   622 		node->value = value;

   623 		return result;

   624 	}

   625 	/* It is not yet present, let's add it */

   626 	if (prev == NULL) {

   627 		/* The bucket is still empty */

   628 		uint hash = h->hash(key1, key2);

   629 		h->buckets_in_use[hash] = true;

   630 		node = h->buckets + hash;

   631 	} else {

   632 		/* Add it after prev */

   633 		node = malloc(sizeof(HashNode));

   634 		prev->next = node;

   635 	}

   636 	node->next = NULL;

   637 	node->key1 = key1;

   638 	node->key2 = key2;

   639 	node->value = value;

   640 	h->size++;

   641 	return NULL;

   642 }

   643 

   644 void* Hash_Get(Hash* h, uint key1, uint key2) {

   645 	HashNode* node = Hash_FindNode(h, key1, key2, NULL);

   646 	#ifdef HASH_DEBUG

   647 	debug("Found node: %p", node);

   648 	#endif

   649 	if (node == NULL) {

   650 		/* Node not found */

   651 		return NULL;

   652 	} else {

   653 		return node->value;

   654 	}

   655 }

   656 

   657 uint Hash_Size(Hash* h) {

   658     return h->size;

   659 }