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

	uint i;

    10

	if (free_values)

    11

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

    12

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

    13

	q->data.stack.size = 0;

    14

}

    15

    16

static void Stack_Free(Queue* q, bool free_values)

    17

{

    18

	q->clear(q, free_values);

    19

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

    20

	if (q->freeq)

    21

		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)

    27

		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

	void* result;

    35

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

    36

		return NULL;

    37

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

    38

    39

	return result;

    40

}

    41

    42

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

    43

{

    44

	return false;

    45

}

    46

    47

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

    48

{

    49

	q->push = Stack_Push;

    50

	q->pop = Stack_Pop;

    51

	q->del = Stack_Delete;

    52

	q->clear = Stack_Clear;

    53

	q->free = Stack_Free;

    54

	q->data.stack.max_size = max_size;

    55

	q->data.stack.size = 0;

    56

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

    57

	q->freeq = false;

    58

	return q;

    59

}

    60

    61

Queue* new_Stack(uint max_size)

    62

{

    63

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

    64

	init_stack(q, max_size);

    65

	q->freeq = true;

    66

	return q;

    67

}

    68

    69

/*

    70

 * Fifo

    71

 */

    72

    73

static void Fifo_Clear(Queue* q, bool free_values)

    74

{

    75

	uint head, tail;

    76

	if (free_values) {

    77

		head = q->data.fifo.head;

    78

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

    79

		while (head != tail) {

    80

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

    81

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

    82

		}

    83

	}

    84

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

    85

}

    86

    87

static void Fifo_Free(Queue* q, bool free_values)

    88

{

    89

	q->clear(q, free_values);

    90

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

    91

	if (q->freeq)

    92

		free(q);

    93

}

    94

    95

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

    96

{

    97

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

    98

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

    99

		return false;

   100

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

   101

   102

   103

	q->data.fifo.head = next;

   104

	return true;

   105

}

   106

   107

static void* Fifo_Pop(Queue* q)

   108

{

   109

	void* result;

   110

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

   111

		return NULL;

   112

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

   113

   114

   115

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

   116

	return result;

   117

}

   118

   119

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

   120

{

   121

	return false;

   122

}

   123

   124

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

   125

{

   126

	q->push = Fifo_Push;

   127

	q->pop = Fifo_Pop;

   128

	q->del = Fifo_Delete;

   129

	q->clear = Fifo_Clear;

   130

	q->free = Fifo_Free;

   131

	q->data.fifo.max_size = max_size;

   132

	q->data.fifo.head = 0;

   133

	q->data.fifo.tail = 0;

   134

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

   135

	q->freeq = false;

   136

	return q;

   137

}

   138

   139

Queue* new_Fifo(uint max_size)

   140

{

   141

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

   142

	init_fifo(q, max_size);

   143

	q->freeq = true;

   144

	return q;

   145

}

   146

   147

   148

/*

   149

 * Insertion Sorter

   150

 */

   151

   152

static void InsSort_Clear(Queue* q, bool free_values)

   153

{

   154

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

   155

	InsSortNode* prev;

   156

	while (node != NULL) {

   157

		if (free_values)

   158

			free(node->item);

   159

		prev = node;

   160

		node = node->next;

   161

		free(prev);

   162

   163

	}

   164

	q->data.inssort.first = NULL;

   165

}

   166

   167

static void InsSort_Free(Queue* q, bool free_values)

   168

{

   169

	q->clear(q, free_values);

   170

	if (q->freeq)

   171

		free(q);

   172

}

   173

   174

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

   175

{

   176

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

   177

	if (newnode == NULL) return false;

   178

	newnode->item = item;

   179

	newnode->priority = priority;

   180

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

   181

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

   182

		q->data.inssort.first = newnode;

   183

	} else {

   184

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

   185

		while( node != NULL ) {

   186

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

   187

				newnode->next = node->next;

   188

				node->next = newnode;

   189

				break;

   190

			}

   191

			node = node->next;

   192

		}

   193

	}

   194

	return true;

   195

}

   196

   197

static void* InsSort_Pop(Queue* q)

   198

{

   199

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

   200

	void* result;

   201

	if (node == NULL)

   202

		return NULL;

   203

	result = node->item;

   204

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

   205

	if (q->data.inssort.first)

   206

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

   207

	free(node);

   208

	return result;

   209

}

   210

   211

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

   212

{

   213

	return false;

   214

}

   215

   216

void init_InsSort(Queue* q) {

   217

	q->push = InsSort_Push;

   218

	q->pop = InsSort_Pop;

   219

	q->del = InsSort_Delete;

   220

	q->clear = InsSort_Clear;

   221

	q->free = InsSort_Free;

   222

	q->data.inssort.first = NULL;

   223

	q->freeq = false;

   224

}

   225

   226

Queue* new_InsSort(void)

   227

{

   228

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

   229

	init_InsSort(q);

   230

	q->freeq = true;

   231

	return q;

   232

}

   233

   234

   235

/*

   236

 * Binary Heap

   237

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

   238

 */

   239

   240

#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

   241

#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE-1)

   242

   243

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

   244

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

   245

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

   246

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

   247

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

   248

   249

static void BinaryHeap_Clear(Queue* q, bool free_values)

   250

{

   251

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

   252

	 * memory */

   253

	uint i,j;

   254

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

   255

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

   256

			/* No more allocated blocks */

   257

			break;

   258

		}

   259

		/* For every allocated block */

   260

		if (free_values)

   261

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

   262

				/* For every element in the block */

   263

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

   264

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

   265

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

   266

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

   267

			}

   268

		if (i != 0) {

   269

			/* Leave the first block of memory alone */

   270

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

   271

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

   272

		}

   273

	}

   274

	q->data.binaryheap.size = 0;

   275

	q->data.binaryheap.blocks = 1;

   276

}

   277

   278

static void BinaryHeap_Free(Queue* q, bool free_values)

   279

{

   280

	uint i;

   281

	q->clear(q, free_values);

   282

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

   283

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

   284

			break;

   285

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

   286

	}

   287

	if (q->freeq)

   288

		free(q);

   289

}

   290

   291

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

   292

{

   293

	#ifdef QUEUE_DEBUG

   294

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

   295

	#endif

   296

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

   297

		return false;

   298

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

   299

   300

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

   301

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

   302

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

   303

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

   304

		q->data.binaryheap.blocks++;

   305

#ifdef QUEUE_DEBUG

   306

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

   307

#endif

   308

	}

   309

   310

	// Add the item at the end of the array

   311

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

   312

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

   313

	q->data.binaryheap.size++;

   314

   315

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

   316

	// bigger, we switch with the parent

   317

	{

   318

		int i, j;

   319

		BinaryHeapNode temp;

   320

		i = q->data.binaryheap.size;

   321

		while (i > 1) {

   322

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

   323

			j = i / 2;

   324

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

   325

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

   326

				temp = BIN_HEAP_ARR(j);

   327

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   328

				BIN_HEAP_ARR(i) = temp;

   329

				i = j;

   330

			} else {

   331

				// It is not, we're done!

   332

				break;

   333

			}

   334

		}

   335

	}

   336

   337

	return true;

   338

}

   339

   340

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

   341

{

   342

	#ifdef QUEUE_DEBUG

   343

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

   344

	#endif

   345

	uint i = 0;

   346

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

   347

	do {

   348

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

   349

		i++;

   350

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

   351

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

   352

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

   353

   354

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

   355

	q->data.binaryheap.size--;

   356

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

   357

   358

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

   359

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

   360

	{

   361

		uint j;

   362

		BinaryHeapNode temp;

   363

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

   364

		//   i with 1

   365

		i++;

   366

   367

		for (;;) {

   368

			j = i;

   369

			// Check if we have 2 childs

   370

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

   371

				// Is this child smaller than the parent?

   372

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

   373

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

   374

				//  This way we get that straight away!

   375

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

   376

			// Do we have one child?

   377

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

   378

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

   379

			}

   380

   381

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

   382

			if (i != j) {

   383

				temp = BIN_HEAP_ARR(j);

   384

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   385

				BIN_HEAP_ARR(i) = temp;

   386

			} else {

   387

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

   388

				break;

   389

			}

   390

		}

   391

	}

   392

   393

	return true;

   394

}

   395

   396

static void* BinaryHeap_Pop(Queue* q)

   397

{

   398

	#ifdef QUEUE_DEBUG

   399

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

   400

	#endif

   401

	void* result;

   402

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

   403

		return NULL;

   404

   405

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

   406

	result = BIN_HEAP_ARR(1).item;

   407

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

   408

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

   409

   410

	return result;

   411

}

   412

   413

void init_BinaryHeap(Queue* q, uint max_size)

   414

{

   415

	assert(q);

   416

	q->push = BinaryHeap_Push;

   417

	q->pop = BinaryHeap_Pop;

   418

	q->del = BinaryHeap_Delete;

   419

	q->clear = BinaryHeap_Clear;

   420

	q->free = BinaryHeap_Free;

   421

	q->data.binaryheap.max_size = max_size;

   422

	q->data.binaryheap.size = 0;

   423

	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   424

	//   It autosizes when it runs out of memory

   425

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

   426

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

   427

	q->data.binaryheap.blocks = 1;

   428

	q->freeq = false;

   429

#ifdef QUEUE_DEBUG

   430

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

   431

#endif

   432

}

   433

   434

Queue* new_BinaryHeap(uint max_size) {

   435

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

   436

	init_BinaryHeap(q, max_size);

   437

	q->freeq = true;

   438

	return q;

   439

}

   440

   441

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

   442

#undef BIN_HEAP_ARR

   443

   444

/*

   445

 * Hash

   446

 */

   447

   448

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

   449

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

   450

	uint i;

   451

	assert(h);

   452

	#ifdef HASH_DEBUG

   453

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

   454

	#endif

   455

	h->hash = hash;

   456

	h->size = 0;

   457

	h->num_buckets = num_buckets;

   458

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

   459

	#ifdef HASH_DEBUG

   460

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

   461

	#endif

   462

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

   463

	h->freeh = false;

   464

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

   465

		h->buckets_in_use[i] = false;

   466

}

   467

   468

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

   469

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

   470

	init_Hash(h, hash, num_buckets);

   471

	h->freeh = true;

   472

	return h;

   473

}

   474

   475

void delete_Hash(Hash* h, bool free_values) {

   476

	uint i;

   477

	/* Iterate all buckets */

   478

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

   479

	{

   480

		if (h->buckets_in_use[i]) {

   481

			HashNode* node;

   482

			/* Free the first value */

   483

			if (free_values)

   484

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

   485

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

   486

			while (node != NULL) {

   487

				HashNode* prev = node;

   488

				node = node->next;

   489

				/* Free the value */

   490

				if (free_values)

   491

					free(prev->value);

   492

				/* Free the node */

   493

				free(prev);

   494

			}

   495

		}

   496

	}

   497

	free(h->buckets);

   498

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

   499

	 * malloc with buckets */

   500

	#ifdef HASH_DEBUG

   501

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

   502

	#endif

   503

	if (h->freeh)

   504

		free(h);

   505

}

   506

   507

void stat_Hash(Hash* h)

   508

{

   509

	uint used_buckets = 0;

   510

	uint max_collision = 0;