1

#include "stdafx.h"

     2

#include "ttd.h"

     3

#include "queue.h"

     4

     5

static void Stack_Clear(Queue* q, bool free_values)

     6

{

     7

	uint i;

     8

	if (free_values)

     9

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

    10

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

    11

	q->data.stack.size = 0;

    12

}

    13

    14

static void Stack_Free(Queue* q, bool free_values)

    15

{

    16

	q->clear(q, free_values);

    17

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

    18

	if (q->freeq)

    19

		free(q);

    20

}

    21

    22

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

    23

{

    24

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

    25

		return false;

    26

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

    27

	return true;

    28

}

    29

    30

static void* Stack_Pop(Queue* q)

    31

{

    32

	void* result;

    33

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

    34

		return NULL;

    35

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

    36

    37

	return result;

    38

}

    39

    40

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

    41

{

    42

	return false;

    43

}

    44

    45

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

    46

{

    47

	q->push = Stack_Push;

    48

	q->pop = Stack_Pop;

    49

	q->del = Stack_Delete;

    50

	q->clear = Stack_Clear;

    51

	q->free = Stack_Free;

    52

	q->data.stack.max_size = max_size;

    53

	q->data.stack.size = 0;

    54

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

    55

	q->freeq = false;

    56

	return q;

    57

}

    58

    59

Queue* new_Stack(uint max_size)

    60

{

    61

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

    62

	init_stack(q, max_size);

    63

	q->freeq = true;

    64

	return q;

    65

}

    66

    67

/*

    68

 * Fifo

    69

 */

    70

    71

static void Fifo_Clear(Queue* q, bool free_values)

    72

{

    73

	uint head, tail;

    74

	if (free_values) {

    75

		head = q->data.fifo.head;

    76

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

    77

		while (head != tail) {

    78

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

    79

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

    80

		}

    81

	}

    82

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

    83

}

    84

    85

static void Fifo_Free(Queue* q, bool free_values)

    86

{

    87

	q->clear(q, free_values);

    88

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

    89

	if (q->freeq)

    90

		free(q);

    91

}

    92

    93

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

    94

{

    95

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

    96

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

    97

		return false;

    98

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

    99

   100

   101

	q->data.fifo.head = next;

   102

	return true;

   103

}

   104

   105

static void* Fifo_Pop(Queue* q)

   106

{

   107

	void* result;

   108

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

   109

		return NULL;

   110

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

   111

   112

   113

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

   114

	return result;

   115

}

   116

   117

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

   118

{

   119

	return false;

   120

}

   121

   122

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

   123

{

   124

	q->push = Fifo_Push;

   125

	q->pop = Fifo_Pop;

   126

	q->del = Fifo_Delete;

   127

	q->clear = Fifo_Clear;

   128

	q->free = Fifo_Free;

   129

	q->data.fifo.max_size = max_size;

   130

	q->data.fifo.head = 0;

   131

	q->data.fifo.tail = 0;

   132

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

   133

	q->freeq = false;

   134

	return q;

   135

}

   136

   137

Queue* new_Fifo(uint max_size)

   138

{

   139

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

   140

	init_fifo(q, max_size);

   141

	q->freeq = true;

   142

	return q;

   143

}

   144

   145

   146

/*

   147

 * Insertion Sorter

   148

 */

   149

   150

static void InsSort_Clear(Queue* q, bool free_values)

   151

{

   152

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

   153

	InsSortNode* prev;

   154

	while (node != NULL) {

   155

		if (free_values)

   156

			free(node->item);

   157

		prev = node;

   158

		node = node->next;

   159

		free(prev);

   160

   161

	}

   162

	q->data.inssort.first = NULL;

   163

}

   164

   165

static void InsSort_Free(Queue* q, bool free_values)

   166

{

   167

	q->clear(q, free_values);

   168

	if (q->freeq)

   169

		free(q);

   170

}

   171

   172

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

   173

{

   174

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

   175

	if (newnode == NULL) return false;

   176

	newnode->item = item;

   177

	newnode->priority = priority;

   178

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

   179

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

   180

		q->data.inssort.first = newnode;

   181

	} else {

   182

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

   183

		while( node != NULL ) {

   184

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

   185

				newnode->next = node->next;

   186

				node->next = newnode;

   187

				break;

   188

			}

   189

			node = node->next;

   190

		}

   191

	}

   192

	return true;

   193

}

   194

   195

static void* InsSort_Pop(Queue* q)

   196

{

   197

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

   198

	void* result;

   199

	if (node == NULL)

   200

		return NULL;

   201

	result = node->item;

   202

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

   203

	if (q->data.inssort.first)

   204

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

   205

	free(node);

   206

	return result;

   207

}

   208

   209

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

   210

{

   211

	return false;

   212

}

   213

   214

void init_InsSort(Queue* q) {

   215

	q->push = InsSort_Push;

   216

	q->pop = InsSort_Pop;

   217

	q->del = InsSort_Delete;

   218

	q->clear = InsSort_Clear;

   219

	q->free = InsSort_Free;

   220

	q->data.inssort.first = NULL;

   221

	q->freeq = false;

   222

}

   223

   224

Queue* new_InsSort(void)

   225

{

   226

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

   227

	init_InsSort(q);

   228

	q->freeq = true;

   229

	return q;

   230

}

   231

   232

   233

/*

   234

 * Binary Heap

   235

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

   236

 */

   237

   238

#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

   239

#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE-1)

   240

   241

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

   242

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

   243

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

   244

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

   245

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

   246

   247

static void BinaryHeap_Clear(Queue* q, bool free_values)

   248

{

   249

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

   250

	 * memory */

   251

	uint i,j;

   252

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

   253

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

   254

			/* No more allocated blocks */

   255

			break;

   256

		}

   257

		/* For every allocated block */

   258

		if (free_values)

   259

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

   260

				/* For every element in the block */

   261

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

   262

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

   263

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

   264

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

   265

			}

   266

		if (i != 0) {

   267

			/* Leave the first block of memory alone */

   268

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

   269

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

   270

		}

   271

	}

   272

	q->data.binaryheap.size = 0;

   273

	q->data.binaryheap.blocks = 1;

   274

}

   275

   276

static void BinaryHeap_Free(Queue* q, bool free_values)

   277

{

   278

	uint i;

   279

	q->clear(q, free_values);

   280

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

   281

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

   282

			break;

   283

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

   284

	}

   285

	if (q->freeq)

   286

		free(q);

   287

}

   288

   289

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

   290

{

   291

	#ifdef QUEUE_DEBUG

   292

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

   293

	#endif

   294

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

   295

		return false;

   296

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

   297

   298

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

   299

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

   300

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

   301

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

   302

		q->data.binaryheap.blocks++;

   303

#ifdef QUEUE_DEBUG

   304

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

   305

#endif

   306

	}

   307

   308

	// Add the item at the end of the array

   309

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

   310

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

   311

	q->data.binaryheap.size++;

   312

   313

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

   314

	// bigger, we switch with the parent

   315

	{

   316

		int i, j;

   317

		BinaryHeapNode temp;

   318

		i = q->data.binaryheap.size;

   319

		while (i > 1) {

   320

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

   321

			j = i / 2;

   322

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

   323

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

   324

				temp = BIN_HEAP_ARR(j);

   325

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   326

				BIN_HEAP_ARR(i) = temp;

   327

				i = j;

   328

			} else {

   329

				// It is not, we're done!

   330

				break;

   331

			}

   332

		}

   333

	}

   334

   335

	return true;

   336

}

   337

   338

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

   339

{

   340

	#ifdef QUEUE_DEBUG

   341

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

   342

	#endif

   343

	uint i = 0;

   344

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

   345

	do {

   346

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

   347

		i++;

   348

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

   349

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

   350

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

   351

   352

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

   353

	q->data.binaryheap.size--;

   354

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

   355

   356

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

   357

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

   358

	{

   359

		uint j;

   360

		BinaryHeapNode temp;

   361

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

   362

		//   i with 1

   363

		i++;

   364

   365

		for (;;) {

   366

			j = i;

   367

			// Check if we have 2 childs

   368

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

   369

				// Is this child smaller than the parent?

   370

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

   371

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

   372

				//  This way we get that straight away!

   373

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

   374

			// Do we have one child?

   375

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

   376

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

   377

			}

   378

   379

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

   380

			if (i != j) {

   381

				temp = BIN_HEAP_ARR(j);

   382

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   383

				BIN_HEAP_ARR(i) = temp;

   384

			} else {

   385

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

   386

				break;

   387

			}

   388

		}

   389

	}

   390

   391

	return true;

   392

}

   393

   394

static void* BinaryHeap_Pop(Queue* q)

   395

{

   396

	#ifdef QUEUE_DEBUG

   397

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

   398

	#endif

   399

	void* result;

   400

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

   401

		return NULL;

   402

   403

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

   404

	result = BIN_HEAP_ARR(1).item;

   405

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

   406

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

   407

   408

	return result;

   409

}

   410

   411

void init_BinaryHeap(Queue* q, uint max_size)

   412

{

   413

	assert(q);

   414

	q->push = BinaryHeap_Push;

   415

	q->pop = BinaryHeap_Pop;

   416

	q->del = BinaryHeap_Delete;

   417

	q->clear = BinaryHeap_Clear;

   418

	q->free = BinaryHeap_Free;

   419

	q->data.binaryheap.max_size = max_size;

   420

	q->data.binaryheap.size = 0;

   421

	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   422

	//   It autosizes when it runs out of memory

   423

	q->data.binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE*sizeof(BinaryHeapNode)) + 1);

   424

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

   425

	q->data.binaryheap.blocks = 1;

   426

	q->freeq = false;

   427

#ifdef QUEUE_DEBUG

   428

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

   429

#endif

   430

}

   431

   432

Queue* new_BinaryHeap(uint max_size) {

   433

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

   434

	init_BinaryHeap(q, max_size);

   435

	q->freeq = true;

   436

	return q;

   437

}

   438

   439

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

   440

#undef BIN_HEAP_ARR

   441

   442

/*

   443

 * Hash

   444

 */

   445

   446

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

   447

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

   448

	int i;

   449

	assert(h);

   450

	#ifdef HASH_DEBUG

   451

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

   452

	#endif

   453

	h->hash = hash;

   454

	h->size = 0;

   455

	h->num_buckets = num_buckets;

   456

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

   457

	#ifdef HASH_DEBUG

   458

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

   459

	#endif

   460

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

   461

	h->freeh = false;

   462

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

   463

		h->buckets_in_use[i] = false;

   464

}

   465

   466

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

   467

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

   468

	init_Hash(h, hash, num_buckets);

   469

	h->freeh = true;

   470

	return h;

   471

}

   472

   473

void delete_Hash(Hash* h, bool free_values) {

   474

	uint i;

   475

	/* Iterate all buckets */

   476

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

   477

	{

   478

		if (h->buckets_in_use[i]) {

   479

			HashNode* node;

   480

			/* Free the first value */

   481

			if (free_values)

   482

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

   483

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

   484

			while (node != NULL) {

   485

				HashNode* prev = node;

   486

				node = node->next;

   487

				/* Free the value */

   488

				if (free_values)

   489

					free(prev->value);

   490

				/* Free the node */

   491

				free(prev);

   492

			}

   493

		}

   494

	}

   495

	free(h->buckets);

   496

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

   497

	 * malloc with buckets */

   498

	#ifdef HASH_DEBUG

   499

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

   500

	#endif

   501

	if (h->freeh)

   502

		free(h);

   503

}

   504

   505

void clear_Hash(Hash* h, bool free_values)

   506

{

   507

	uint i;

   508

	HashNode* node;

   509

	/* Iterate all buckets */

   510

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

   511

	{