1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "queue.h"

     7

     8

static void Stack_Clear(Queue* q, bool free_values)

     9

{

    10

	if (free_values) {

    11

		uint i;

    12

    13

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

    14

	}

    15

	q->data.stack.size = 0;

    16

}

    17

    18

static void Stack_Free(Queue* q, bool free_values)

    19

{

    20

	q->clear(q, free_values);

    21

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

    22

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

    23

}

    24

    25

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

    26

{

    27

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

    28

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

    29

	return true;

    30

}

    31

    32

static void* Stack_Pop(Queue* q)

    33

{

    34

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

    35

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

    36

}

    37

    38

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

    39

{

    40

	return false;

    41

}

    42

    43

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

    44

{

    45

	q->push = Stack_Push;

    46

	q->pop = Stack_Pop;

    47

	q->del = Stack_Delete;

    48

	q->clear = Stack_Clear;

    49

	q->free = Stack_Free;

    50

	q->data.stack.max_size = max_size;

    51

	q->data.stack.size = 0;

    53

	q->freeq = false;

    54

	return q;

    55

}

    56

    57

Queue* new_Stack(uint max_size)

    58

{

    61

    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

	if (free_values) {

    74

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

    75

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

    76

    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 = 0;

    83

	q->data.fifo.tail = 0;

    84

}

    85

    86

static void Fifo_Free(Queue* q, bool free_values)

    87

{

    88

	q->clear(q, free_values);

    89

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

    90

	if (q->freeq) 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

    97

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

    98

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

    99

   100

	q->data.fifo.head = next;

   101

	return true;

   102

}

   103

   104

static void* Fifo_Pop(Queue* q)

   105

{

   106

	void* result;

   107

   108

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

   109

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

   110

   111

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

   112

	return result;

   113

}

   114

   115

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

   116

{

   117

	return false;

   118

}

   119

   120

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

   121

{

   122

	q->push = Fifo_Push;

   123

	q->pop = Fifo_Pop;

   124

	q->del = Fifo_Delete;

   125

	q->clear = Fifo_Clear;

   126

	q->free = Fifo_Free;

   127

	q->data.fifo.max_size = max_size;

   128

	q->data.fifo.head = 0;

   129

	q->data.fifo.tail = 0;

   131

	q->freeq = false;

   132

	return q;

   133

}

   134

   135

Queue* new_Fifo(uint max_size)

   136

{

   139

   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

   155

	while (node != NULL) {

   156

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

   157

		prev = node;

   158

		node = node->next;

   159

		free(prev);

   160

	}

   161

	q->data.inssort.first = NULL;

   162

}

   163

   164

static void InsSort_Free(Queue* q, bool free_values)

   165

{

   166

	q->clear(q, free_values);

   167

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

   168

}

   169

   170

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

   171

{

   174

   175

	if (newnode == NULL) return false;

   176

	newnode->item = item;

   177

	newnode->priority = priority;

   178

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

   179

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

   180

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

   181

		q->data.inssort.first = newnode;

   182

	} else {

   183

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

   184

		while (node != NULL) {

   185

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

   186

				newnode->next = node->next;

   187

				node->next = newnode;

   188

				break;

   189

			}

   190

			node = node->next;

   191

		}

   192

	}

   193

	return true;

   194

}

   195

   196

static void* InsSort_Pop(Queue* q)

   197

{

   198

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

   199

	void* result;

   200

   201

	if (node == NULL) return NULL;

   202

	result = node->item;

   203

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

   204

	assert(q->data.inssort.first == NULL || 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

{

   216

	q->push = InsSort_Push;

   217

	q->pop = InsSort_Pop;

   218

	q->del = InsSort_Delete;

   219

	q->clear = InsSort_Clear;

   220

	q->free = InsSort_Free;

   221

	q->data.inssort.first = NULL;

   222

	q->freeq = false;

   223

}

   224

   225

Queue* new_InsSort(void)

   226

{

   229

   230

	init_InsSort(q);

   231

	q->freeq = true;

   232

	return q;

   233

}

   234

   235

   236

/*

   237

 * Binary Heap

   238

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

   239

 */

   240

   241

#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

   242

#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)

   243

   244

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

   245

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

   246

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

   247

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

   248

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

   249

   250

static void BinaryHeap_Clear(Queue* q, bool free_values)

   251

{

   252

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

   253

	uint i;

   254

	uint j;

   255

   256

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

   257

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

   258

			/* No more allocated blocks */

   259

			break;

   260

		}

   261

		/* For every allocated block */

   262

		if (free_values) {

   263

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

   264

				/* For every element in the block */

   265

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

   266

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

   267

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

   268

				}

   269

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

   270

			}

   271

		}

   272

		if (i != 0) {

   273

			/* Leave the first block of memory alone */

   274

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

   275

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

   276

		}

   277

	}

   278

	q->data.binaryheap.size = 0;

   279

	q->data.binaryheap.blocks = 1;

   280

}

   281

   282

static void BinaryHeap_Free(Queue* q, bool free_values)

   283

{

   284

	uint i;

   285

   286

	q->clear(q, free_values);

   287

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

   288

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

   289

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

   290

	}

   291

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

   292

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

   293

}

   294

   295

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

   296

{

   297

#ifdef QUEUE_DEBUG

   298

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

   299

#endif

   300

   301

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

   302

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

   303

   304

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

   306

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

   308

		q->data.binaryheap.blocks++;

   309

#ifdef QUEUE_DEBUG

   310

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

   311

#endif

   312

	}

   313

   314

	// Add the item at the end of the array

   315

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

   316

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

   317

	q->data.binaryheap.size++;

   318

   319

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

   320

	// bigger, we switch with the parent

   321

	{

   322

		BinaryHeapNode temp;

   323

		int i;

   324

		int j;

   325

   326

		i = q->data.binaryheap.size;

   327

		while (i > 1) {

   328

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

   329

			j = i / 2;

   330

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

   331

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

   332

				temp = BIN_HEAP_ARR(j);

   333

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   334

				BIN_HEAP_ARR(i) = temp;

   335

				i = j;

   336

			} else {

   337

				// It is not, we're done!

   338

				break;

   339

			}

   340

		}

   341

	}

   342

   343

	return true;

   344

}

   345

   346

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

   347

{

   348

	uint i = 0;

   349

   350

#ifdef QUEUE_DEBUG

   351

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

   352

#endif

   353

   354

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

   355

	do {

   356

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

   357

		i++;

   358

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

   359

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

   360

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

   361

   362

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

   363

	q->data.binaryheap.size--;

   364

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

   365

   366

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

   367

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

   368

	{

   369

		uint j;

   370

		BinaryHeapNode temp;

   371

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

   372

		 * increase i by 1

   373

		 */

   374

		i++;

   375

   376

		for (;;) {

   377

			j = i;

   378

			// Check if we have 2 childs

   379

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

   380

				// Is this child smaller than the parent?

   381

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

   382

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

   383

				//  This way we get that straight away!

   384

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

   385

			// Do we have one child?

   386

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

   387

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

   388

			}

   389

   390

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

   391

			if (i != j) {

   392

				temp = BIN_HEAP_ARR(j);

   393

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   394

				BIN_HEAP_ARR(i) = temp;

   395

			} else {

   396

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

   397

				break;

   398

			}

   399

		}

   400

	}

   401

   402

	return true;

   403

}

   404

   405

static void* BinaryHeap_Pop(Queue* q)

   406

{

   407

	void* result;

   408

   409

#ifdef QUEUE_DEBUG

   410

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

   411

#endif

   412

   413

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

   414

   415

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

   416

	result = BIN_HEAP_ARR(1).item;

   417

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

   418

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

   419

   420

	return result;

   421

}

   422

   423

void init_BinaryHeap(Queue* q, uint max_size)

   424

{

   425

	assert(q != NULL);

   426

	q->push = BinaryHeap_Push;

   427

	q->pop = BinaryHeap_Pop;

   428

	q->del = BinaryHeap_Delete;

   429

	q->clear = BinaryHeap_Clear;

   430

	q->free = BinaryHeap_Free;

   431

	q->data.binaryheap.max_size = max_size;

   432

	q->data.binaryheap.size = 0;

   433

	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   434

	//   It autosizes when it runs out of memory

   437

	q->data.binaryheap.blocks = 1;

   438

	q->freeq = false;

   439

#ifdef QUEUE_DEBUG

   440

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

   441

#endif

   442

}

   443

   444

Queue* new_BinaryHeap(uint max_size)

   445

{

   448

   449

	init_BinaryHeap(q, max_size);

   450

	q->freeq = true;

   451

	return q;

   452

}

   453

   454

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

   455

#undef BIN_HEAP_ARR

   456

   457

/*

   458

 * Hash

   459

 */

   460

   461

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

   462

{

   463

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

   464

	uint i;

   465

   466

	assert(h != NULL);

   467

#ifdef HASH_DEBUG

   468

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

   469

#endif

   470

	h->hash = hash;

   471

	h->size = 0;

   472

	h->num_buckets = num_buckets;

   474

#ifdef HASH_DEBUG

   475

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

   476

#endif

   477

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

   478

	h->freeh = false;

   479

	for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;

   480

}

   481

   482

Hash* new_Hash(Hash_HashProc* hash, int num_buckets)

   483

{

   486

   487

	init_Hash(h, hash, num_buckets);

   488

	h->freeh = true;

   489

	return h;

   490

}

   491

   492

void delete_Hash(Hash* h, bool free_values)

   493

{

   494

	uint i;

   495

   496

	/* Iterate all buckets */

   497

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

   498

		if (h->buckets_in_use[i]) {

   499

			HashNode* node;

   500