1 /* $Id$ */

     2 

     3 #include "stdafx.h"

     4 #include "openttd.h"

     5 #include "queue.h"

     6 

     7 static void Stack_Clear(Queue* q, bool free_values)

     8 {

     9 	if (free_values) {

    10 		uint i;

    11 

    12 		for (i = 0; i < q->data.stack.size; i++) free(q->data.stack.elements[i]);

    13 	}

    14 	q->data.stack.size = 0;

    15 }

    16 

    17 static void Stack_Free(Queue* q, bool free_values)

    18 {

    19 	q->clear(q, free_values);

    20 	free(q->data.stack.elements);

    21 	if (q->freeq) free(q);

    22 }

    23 

    24 static bool Stack_Push(Queue* q, void* item, int priority)

    25 {

    26 	if (q->data.stack.size == q->data.stack.max_size) return false;

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

    28 	return true;

    29 }

    30 

    31 static void* Stack_Pop(Queue* q)

    32 {

    33 	if (q->data.stack.size == 0) return NULL;

    34 	return q->data.stack.elements[--q->data.stack.size];

    35 }

    36 

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

    38 {

    39 	return false;

    40 }

    41 

    42 static Queue* init_stack(Queue* q, uint max_size)

    43 {

    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->data.stack.max_size = max_size;

    50 	q->data.stack.size = 0;

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

    52 	q->freeq = false;

    53 	return q;

    54 }

    55 

    56 Queue* new_Stack(uint max_size)

    57 {

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

    59 

    60 	init_stack(q, max_size);

    61 	q->freeq = true;

    62 	return q;

    63 }

    64 

    65 /*

    66  * Fifo

    67  */

    68 

    69 static void Fifo_Clear(Queue* q, bool free_values)

    70 {

    71 	if (free_values) {

    72 		uint head = q->data.fifo.head;

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

    74 

    75 		while (head != tail) {

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

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

    78 		}

    79 	}

    80 	q->data.fifo.head = 0;

    81 	q->data.fifo.tail = 0;

    82 }

    83 

    84 static void Fifo_Free(Queue* q, bool free_values)

    85 {

    86 	q->clear(q, free_values);

    87 	free(q->data.fifo.elements);

    88 	if (q->freeq) free(q);

    89 }

    90 

    91 static bool Fifo_Push(Queue* q, void* item, int priority)

    92 {

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

    94 

    95 	if (next == q->data.fifo.tail) return false;

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

    97 

    98 	q->data.fifo.head = next;

    99 	return true;

   100 }

   101 

   102 static void* Fifo_Pop(Queue* q)

   103 {

   104 	void* result;

   105 

   106 	if (q->data.fifo.head == q->data.fifo.tail) return NULL;

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

   108 

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

   110 	return result;

   111 }

   112 

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

   114 {

   115 	return false;

   116 }

   117 

   118 static Queue* init_fifo(Queue* q, uint max_size)

   119 {

   120 	q->push = Fifo_Push;

   121 	q->pop = Fifo_Pop;

   122 	q->del = Fifo_Delete;

   123 	q->clear = Fifo_Clear;

   124 	q->free = Fifo_Free;

   125 	q->data.fifo.max_size = max_size;

   126 	q->data.fifo.head = 0;

   127 	q->data.fifo.tail = 0;

   128 	q->data.fifo.elements = malloc(max_size * sizeof(*q->data.fifo.elements));

   129 	q->freeq = false;

   130 	return q;

   131 }

   132 

   133 Queue* new_Fifo(uint max_size)

   134 {

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

   136 

   137 	init_fifo(q, max_size);

   138 	q->freeq = true;

   139 	return q;

   140 }

   141 

   142 

   143 /*

   144  * Insertion Sorter

   145  */

   146 

   147 static void InsSort_Clear(Queue* q, bool free_values)

   148 {

   149 	InsSortNode* node = q->data.inssort.first;

   150 	InsSortNode* prev;

   151 

   152 	while (node != NULL) {

   153 		if (free_values) free(node->item);

   154 		prev = node;

   155 		node = node->next;

   156 		free(prev);

   157 	}

   158 	q->data.inssort.first = NULL;

   159 }

   160 

   161 static void InsSort_Free(Queue* q, bool free_values)

   162 {

   163 	q->clear(q, free_values);

   164 	if (q->freeq) free(q);

   165 }

   166 

   167 static bool InsSort_Push(Queue* q, void* item, int priority)

   168 {

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

   170 

   171 	if (newnode == NULL) return false;

   172 	newnode->item = item;

   173 	newnode->priority = priority;

   174 	if (q->data.inssort.first == NULL ||

   175 			q->data.inssort.first->priority >= priority) {

   176 		newnode->next = q->data.inssort.first;

   177 		q->data.inssort.first = newnode;

   178 	} else {

   179 		InsSortNode* node = q->data.inssort.first;

   180 		while (node != NULL) {

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

   182 				newnode->next = node->next;

   183 				node->next = newnode;

   184 				break;

   185 			}

   186 			node = node->next;

   187 		}

   188 	}

   189 	return true;

   190 }

   191 

   192 static void* InsSort_Pop(Queue* q)

   193 {

   194 	InsSortNode* node = q->data.inssort.first;

   195 	void* result;

   196 

   197 	if (node == NULL) return NULL;

   198 	result = node->item;

   199 	q->data.inssort.first = q->data.inssort.first->next;

   200 	assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority);

   201 	free(node);

   202 	return result;

   203 }

   204 

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

   206 {

   207 	return false;

   208 }

   209 

   210 void init_InsSort(Queue* q)

   211 {

   212 	q->push = InsSort_Push;

   213 	q->pop = InsSort_Pop;

   214 	q->del = InsSort_Delete;

   215 	q->clear = InsSort_Clear;

   216 	q->free = InsSort_Free;

   217 	q->data.inssort.first = NULL;

   218 	q->freeq = false;

   219 }

   220 

   221 Queue* new_InsSort(void)

   222 {

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

   224 

   225 	init_InsSort(q);

   226 	q->freeq = true;

   227 	return q;

   228 }

   229 

   230 

   231 /*

   232  * Binary Heap

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

   234  */

   235 

   236 #define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

   237 #define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)

   238 

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

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

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

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

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

   244 

   245 static void BinaryHeap_Clear(Queue* q, bool free_values)

   246 {

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

   248 	uint i;

   249 	uint j;

   250 

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

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

   253 			/* No more allocated blocks */

   254 			break;

   255 		}

   256 		/* For every allocated block */

   257 		if (free_values) {

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

   259 				/* For every element in the block */

   260 				if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i &&

   261 						(q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {

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

   263 				}

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

   265 			}

   266 		}

   267 		if (i != 0) {

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

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

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

   271 		}

   272 	}

   273 	q->data.binaryheap.size = 0;

   274 	q->data.binaryheap.blocks = 1;

   275 }

   276 

   277 static void BinaryHeap_Free(Queue* q, bool free_values)

   278 {

   279 	uint i;

   280 

   281 	q->clear(q, free_values);

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

   283 		if (q->data.binaryheap.elements[i] == NULL) break;

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

   285 	}

   286 	free(q->data.binaryheap.elements);

   287 	if (q->freeq) free(q);

   288 }

   289 

   290 static bool BinaryHeap_Push(Queue* q, void* item, int priority)

   291 {

   292 #ifdef QUEUE_DEBUG

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

   294 #endif

   295 

   296 	if (q->data.binaryheap.size == q->data.binaryheap.max_size) return false;

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

   298 

   299 	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 */

   301 		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]));

   303 		q->data.binaryheap.blocks++;

   304 #ifdef QUEUE_DEBUG

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

   306 #endif

   307 	}

   308 

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

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

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

   312 	q->data.binaryheap.size++;

   313 

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

   315 	// bigger, we switch with the parent

   316 	{

   317 		BinaryHeapNode temp;

   318 		int i;

   319 		int j;

   320 

   321 		i = q->data.binaryheap.size;

   322 		while (i > 1) {

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

   324 			j = i / 2;

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

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

   327 				temp = BIN_HEAP_ARR(j);

   328 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   329 				BIN_HEAP_ARR(i) = temp;

   330 				i = j;

   331 			} else {

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

   333 				break;

   334 			}

   335 		}

   336 	}

   337 

   338 	return true;

   339 }

   340 

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

   342 {

   343 	uint i = 0;

   344 

   345 #ifdef QUEUE_DEBUG

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

   347 #endif

   348 

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

   350 	do {

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

   352 		i++;

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

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

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

   356 

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

   358 	q->data.binaryheap.size--;

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

   360 

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

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

   363 	{

   364 		uint j;

   365 		BinaryHeapNode temp;

   366 		/* Because of the fact that Binary Heap uses array from 1 to n, we need to

   367 		 * increase i by 1

   368 		 */

   369 		i++;

   370 

   371 		for (;;) {

   372 			j = i;

   373 			// Check if we have 2 childs

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

   375 				// Is this child smaller than the parent?

   376 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;

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

   378 				//  This way we get that straight away!

   379 				if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1;

   380 			// Do we have one child?

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

   382 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;

   383 			}

   384 

   385 			// One of our childs is smaller than we are, switch

   386 			if (i != j) {

   387 				temp = BIN_HEAP_ARR(j);

   388 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   389 				BIN_HEAP_ARR(i) = temp;

   390 			} else {

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

   392 				break;

   393 			}

   394 		}

   395 	}

   396 

   397 	return true;

   398 }

   399 

   400 static void* BinaryHeap_Pop(Queue* q)

   401 {

   402 	void* result;

   403 

   404 #ifdef QUEUE_DEBUG

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

   406 #endif

   407 

   408 	if (q->data.binaryheap.size == 0) return NULL;

   409 

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

   411 	result = BIN_HEAP_ARR(1).item;

   412 	// And now we should get rid of this item...

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

   414 

   415 	return result;

   416 }

   417 

   418 void init_BinaryHeap(Queue* q, uint max_size)

   419 {

   420 	assert(q != NULL);

   421 	q->push = BinaryHeap_Push;

   422 	q->pop = BinaryHeap_Pop;

   423 	q->del = BinaryHeap_Delete;

   424 	q->clear = BinaryHeap_Clear;

   425 	q->free = BinaryHeap_Free;

   426 	q->data.binaryheap.max_size = max_size;

   427 	q->data.binaryheap.size = 0;

   428 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   429 	//   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));

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

   432 	q->data.binaryheap.blocks = 1;

   433 	q->freeq = false;

   434 #ifdef QUEUE_DEBUG

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

   436 #endif

   437 }

   438 

   439 Queue* new_BinaryHeap(uint max_size)

   440 {

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

   442 

   443 	init_BinaryHeap(q, max_size);

   444 	q->freeq = true;

   445 	return q;

   446 }

   447 

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

   449 #undef BIN_HEAP_ARR

   450 

   451 /*

   452  * Hash

   453  */

   454 

   455 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets)

   456 {

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

   458 	uint i;

   459 

   460 	assert(h != NULL);

   461 #ifdef HASH_DEBUG

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

   463 #endif

   464 	h->hash = hash;

   465 	h->size = 0;

   466 	h->num_buckets = num_buckets;

   467 	h->buckets = malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));

   468 #ifdef HASH_DEBUG

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

   470 #endif

   471 	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;

   474 }

   475 

   476 Hash* new_Hash(Hash_HashProc* hash, int num_buckets)

   477 {

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

   479 

   480 	init_Hash(h, hash, num_buckets);

   481 	h->freeh = true;

   482 	return h;

   483 }

   484 

   485 void delete_Hash(Hash* h, bool free_values)

   486 {

   487 	uint i;

   488 

   489 	/* Iterate all buckets */

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

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

   492 			HashNode* node;

   493 

   494 			/* Free the first value */

   495 			if (free_values) free(h->buckets[i].value);

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

   497 			while (node != NULL) {

   498 				HashNode* prev = node;

   499 

   500 				node = node->next;

   501 				/* Free the value */

   502 				if (free_values) free(prev->value);

   503 				/* Free the node */

   504 				free(prev);

   505 			}

   506 		}

   507 	}

   508 	free(h->buckets);

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

   510 	 * malloc with buckets */

   511 #ifdef HASH_DEBUG

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

   513 #endif

   514 	if (h->freeh) free(h);

   515 }

   516 

   517 #ifdef HASH_STATS

   518 static void stat_Hash(const Hash* h)

   519 {

   520 	uint used_buckets = 0;

   521 	uint max_collision = 0;

   522 	uint max_usage = 0;

   523 	uint usage[200];

   524 	uint i;

   525 

   526 	for (i = 0; i < lengthof(usage); i++) usage[i] = 0;

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

   528 		uint collision = 0;

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

   530 			const HashNode* node;

   531 

   532 			used_buckets++;

   533 			for (node = &h->buckets[i]; node != NULL; node = node->next) collision++;

   534 			if (collision > max_collision) max_collision = collision;

   535 		}

   536 		if (collision >= lengthof(usage)) collision = lengthof(usage) - 1;

   537 		usage[collision]++;

   538 		if (collision > 0 && usage[collision] >= max_usage) {

   539 			max_usage = usage[collision];

   540 		}

   541 	}

   542 	printf(

   543 		"---\n"

   544 		"Hash size: %d\n"

   545 		"Nodes used: %d\n"

   546 		"Non empty buckets: %d\n"

   547 		"Max collision: %d\n",

   548 		h->num_buckets, h->size, used_buckets, max_collision

   549 	);

   550 	printf("{ ");

   551 	for (i = 0; i <= max_collision; i++) {

   552 		if (usage[i] > 0) {

   553 			printf("%d:%d ", i, usage[i]);

   554 #if 0

   555 			if (i > 0) {

   556 				uint j;

   557 

   558 				for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#');

   559 			}

   560 			printf("\n");

   561 #endif

   562 		}

   563 	}

   564 	printf ("}\n");

   565 }

   566 #endif

   567 

   568 void clear_Hash(Hash* h, bool free_values)

   569 {

   570 	uint i;

   571 

   572 #ifdef HASH_STATS

   573 	if (h->size > 2000) stat_Hash(h);

   574 #endif

   575 

   576 	/* Iterate all buckets */

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

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

   579 			HashNode* node;

   580 

   581 			h->buckets_in_use[i] = false;

   582 			/* Free the first value */

   583 			if (free_values) free(h->buckets[i].value);

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

   585 			while (node != NULL) {

   586 				HashNode* prev = node;

   587 

   588 				node = node->next;

   589 				if (free_values) free(prev->value);

   590 				free(prev);

   591 			}

   592 		}

   593 	}

   594 	h->size = 0;

   595 }

   596 

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

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

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

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

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

   602  * not used for output.

   603  */

   604 static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out)

   605 {

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

   607 	HashNode* result = NULL;

   608 

   609 #ifdef HASH_DEBUG

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

   611 #endif

   612 	/* Check if the bucket is empty */

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

   614 		if (prev_out != NULL) *prev_out = NULL;

   615 		result = NULL;

   616 	/* Check the first node specially */

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

   618 		/* Save the value */

   619 		result = h->buckets + hash;

   620 		if (prev_out != NULL) *prev_out = NULL;

   621 #ifdef HASH_DEBUG

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

   623 #endif

   624 	/* Check all other nodes */

   625 	} else {

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

   627 		HashNode* node;

   628 

   629 		for (node = prev->next; node != NULL; node = node->next) {

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

   631 				/* Found it */

   632 				result = node;

   633 #ifdef HASH_DEBUG

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

   635 #endif

   636 				break;

   637 			}

   638 			prev = node;

   639 		}

   640 		if (prev_out != NULL) *prev_out = prev;

   641 	}

   642 #ifdef HASH_DEBUG

   643 	if (result == NULL) debug("Not found");

   644 #endif

   645 	return result;

   646 }

   647 

   648 void* Hash_Delete(Hash* h, uint key1, uint key2)

   649 {

   650 	void* result;

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

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

   653 

   654 	if (node == NULL) {

   655 		/* not found */

   656 		result = NULL;

   657 	} else if (prev == NULL) {

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

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

   660 		/* Save the value */

   661 		result = node->value;

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

   663 			HashNode* next = node->next;

   664 			/* Copy the second to the first */

   665 			*node = *next;

   666 			/* Free the second */

   667 #ifndef NOFREE

   668 			free(next);

   669 #endif

   670 		} else {

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

   672 			/* Mark it as empty */

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

   674 			h->buckets_in_use[hash] = false;

   675 		}

   676 	} else {

   677 		/* It is in another node */

   678 		/* Save the value */

   679 		result = node->value;

   680 		/* Link previous and next nodes */

   681 		prev->next = node->next;

   682 		/* Free the node */

   683 #ifndef NOFREE

   684 		free(node);

   685 #endif

   686 	}

   687 	if (result != NULL) h->size--;

   688 	return result;

   689 }

   690 

   691 

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

   693 {

   694 	HashNode* prev;

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

   696 

   697 	if (node != NULL) {

   698 		/* Found it */

   699 		void* result = node->value;

   700 

   701 		node->value = value;

   702 		return result;

   703 	}

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

   705 	if (prev == NULL) {

   706 		/* The bucket is still empty */

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

   708 		h->buckets_in_use[hash] = true;

   709 		node = h->buckets + hash;

   710 	} else {

   711 		/* Add it after prev */

   712 		node = malloc(sizeof(*node));

   713 		prev->next = node;

   714 	}

   715 	node->next = NULL;

   716 	node->key1 = key1;

   717 	node->key2 = key2;

   718 	node->value = value;

   719 	h->size++;

   720 	return NULL;

   721 }

   722 

   723 void* Hash_Get(const Hash* h, uint key1, uint key2)

   724 {

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

   726 

   727 #ifdef HASH_DEBUG

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

   729 #endif

   730 	return (node != NULL) ? node->value : NULL;

   731 }

   732 

   733 uint Hash_Size(const Hash* h)

   734 {

   735 	return h->size;

   736 }