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