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