1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "queue.h"

     6

#include "helpers.hpp"

     7

     8

     9

/*

    10

 * Insertion Sorter

    11

 */

    12

    13

static void InsSort_Clear(Queue* q, bool free_values)

    14

{

    15

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

    16

	InsSortNode* prev;

    17

    18

	while (node != NULL) {

    19

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

    20

		prev = node;

    21

		node = node->next;

    22

		free(prev);

    23

	}

    24

	q->data.inssort.first = NULL;

    25

}

    26

    27

static void InsSort_Free(Queue* q, bool free_values)

    28

{

    29

	q->clear(q, free_values);

    30

}

    31

    32

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

    33

{

    34

	InsSortNode* newnode = MallocT<InsSortNode>(1);

    35

    36

	if (newnode == NULL) return false;

    37

	newnode->item = item;

    38

	newnode->priority = priority;

    39

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

    40

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

    41

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

    42

		q->data.inssort.first = newnode;

    43

	} else {

    44

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

    45

		while (node != NULL) {

    46

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

    47

				newnode->next = node->next;

    48

				node->next = newnode;

    49

				break;

    50

			}

    51

			node = node->next;

    52

		}

    53

	}

    54

	return true;

    55

}

    56

    57

static void* InsSort_Pop(Queue* q)

    58

{

    59

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

    60

	void* result;

    61

    62

	if (node == NULL) return NULL;

    63

	result = node->item;

    64

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

    65

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

    66

	free(node);

    67

	return result;

    68

}

    69

    70

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

    71

{

    72

	return false;

    73

}

    74

    75

void init_InsSort(Queue* q)

    76

{

    77

	q->push = InsSort_Push;

    78

	q->pop = InsSort_Pop;

    79

	q->del = InsSort_Delete;

    80

	q->clear = InsSort_Clear;

    81

	q->free = InsSort_Free;

    82

	q->data.inssort.first = NULL;

    83

}

    84

    85

    86

/*

    87

 * Binary Heap

    88

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

    89

 */

    90

    91

#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

    92

#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)

    93

    94

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

    95

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

    96

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

    97

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

    98

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

    99

   100

static void BinaryHeap_Clear(Queue* q, bool free_values)

   101

{

   102

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

   103

	uint i;

   104

	uint j;

   105

   106

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

   107

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

   108

			/* No more allocated blocks */

   109

			break;

   110

		}

   111

		/* For every allocated block */

   112

		if (free_values) {

   113

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

   114

				/* For every element in the block */

   115

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

   116

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

   117

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

   118

				}

   119

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

   120

			}

   121

		}

   122

		if (i != 0) {

   123

			/* Leave the first block of memory alone */

   124

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

   125

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

   126

		}

   127

	}

   128

	q->data.binaryheap.size = 0;

   129

	q->data.binaryheap.blocks = 1;

   130

}

   131

   132

static void BinaryHeap_Free(Queue* q, bool free_values)

   133

{

   134

	uint i;

   135

   136

	q->clear(q, free_values);

   137

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

   138

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

   139

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

   140

	}

   141

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

   142

}

   143

   144

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

   145

{

   146

#ifdef QUEUE_DEBUG

   147

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

   148

#endif

   149

   150

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

   151

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

   152

   153

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

   154

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

   155

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

   156

		q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);

   157

		q->data.binaryheap.blocks++;

   158

#ifdef QUEUE_DEBUG

   159

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

   160

#endif

   161

	}

   162

   163

	// Add the item at the end of the array

   164

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

   165

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

   166

	q->data.binaryheap.size++;

   167

   168

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

   169

	// bigger, we switch with the parent

   170

	{

   171

		BinaryHeapNode temp;

   172

		int i;

   173

		int j;

   174

   175

		i = q->data.binaryheap.size;

   176

		while (i > 1) {

   177

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

   178

			j = i / 2;

   179

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

   180

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

   181

				temp = BIN_HEAP_ARR(j);

   182

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   183

				BIN_HEAP_ARR(i) = temp;

   184

				i = j;

   185

			} else {

   186

				// It is not, we're done!

   187

				break;

   188

			}

   189

		}

   190

	}

   191

   192

	return true;

   193

}

   194

   195

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

   196

{

   197

	uint i = 0;

   198

   199

#ifdef QUEUE_DEBUG

   200

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

   201

#endif

   202

   203

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

   204

	do {

   205

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

   206

		i++;

   207

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

   208

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

   209

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

   210

   211

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

   212

	q->data.binaryheap.size--;

   213

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

   214

   215

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

   216

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

   217

	{

   218

		uint j;

   219

		BinaryHeapNode temp;

   220

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

   221

		 * increase i by 1

   222

		 */

   223

		i++;

   224

   225

		for (;;) {

   226

			j = i;

   227

			// Check if we have 2 childs

   228

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

   229

				// Is this child smaller than the parent?

   230

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

   231

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

   232

				//  This way we get that straight away!

   233

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

   234

			// Do we have one child?

   235

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

   236

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

   237

			}

   238

   239

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

   240

			if (i != j) {

   241

				temp = BIN_HEAP_ARR(j);

   242

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   243

				BIN_HEAP_ARR(i) = temp;

   244

			} else {

   245

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

   246

				break;

   247

			}

   248

		}

   249

	}

   250

   251

	return true;

   252

}

   253

   254

static void* BinaryHeap_Pop(Queue* q)

   255

{

   256

	void* result;

   257

   258

#ifdef QUEUE_DEBUG

   259

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

   260

#endif

   261

   262

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

   263

   264

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

   265

	result = BIN_HEAP_ARR(1).item;

   266

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

   267

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

   268

   269

	return result;

   270

}

   271

   272

void init_BinaryHeap(Queue* q, uint max_size)

   273

{

   274

	assert(q != NULL);

   275

	q->push = BinaryHeap_Push;

   276

	q->pop = BinaryHeap_Pop;

   277

	q->del = BinaryHeap_Delete;

   278

	q->clear = BinaryHeap_Clear;

   279

	q->free = BinaryHeap_Free;

   280

	q->data.binaryheap.max_size = max_size;

   281

	q->data.binaryheap.size = 0;

   282

	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   283

	//   It autosizes when it runs out of memory

   284

	q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);

   285

	q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);

   286

	q->data.binaryheap.blocks = 1;

   287

#ifdef QUEUE_DEBUG

   288

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

   289

#endif

   290

}

   291

   292

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

   293

#undef BIN_HEAP_ARR

   294

   295

/*

   296

 * Hash

   297

 */

   298

   299

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

   300

{

   301

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

   302

	uint i;

   303

   304

	assert(h != NULL);

   305

#ifdef HASH_DEBUG

   306

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

   307

#endif

   308

	h->hash = hash;

   309

	h->size = 0;

   310

	h->num_buckets = num_buckets;

   311

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

   312

#ifdef HASH_DEBUG

   313

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

   314

#endif

   315

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

   316

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

   317

}

   318

   319

   320

void delete_Hash(Hash* h, bool free_values)

   321

{

   322

	uint i;

   323

   324

	/* Iterate all buckets */

   325

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

   326

		if (h->buckets_in_use[i]) {

   327

			HashNode* node;

   328

   329

			/* Free the first value */

   330

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

   331

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

   332

			while (node != NULL) {

   333

				HashNode* prev = node;

   334

   335

				node = node->next;

   336

				/* Free the value */

   337

				if (free_values) free(prev->value);

   338

				/* Free the node */

   339

				free(prev);

   340

			}

   341

		}

   342

	}

   343

	free(h->buckets);

   344

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

   345

	 * malloc with buckets */

   346

#ifdef HASH_DEBUG

   347

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

   348

#endif

   349

}

   350

   351

#ifdef HASH_STATS

   352

static void stat_Hash(const Hash* h)

   353

{

   354

	uint used_buckets = 0;

   355

	uint max_collision = 0;

   356

	uint max_usage = 0;

   357

	uint usage[200];

   358

	uint i;

   359

   360

	for (i = 0; i < lengthof(usage); i++) usage[i] = 0;

   361

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

   362

		uint collision = 0;

   363

		if (h->buckets_in_use[i]) {

   364

			const HashNode* node;

   365

   366

			used_buckets++;

   367

			for (node = &h->buckets[i]; node != NULL; node = node->next) collision++;

   368

			if (collision > max_collision) max_collision = collision;

   369

		}

   370

		if (collision >= lengthof(usage)) collision = lengthof(usage) - 1;

   371

		usage[collision]++;

   372

		if (collision > 0 && usage[collision] >= max_usage) {

   373

			max_usage = usage[collision];

   374

		}

   375

	}

   376

	printf(

   377

		"---\n"

   378

		"Hash size: %d\n"

   379

		"Nodes used: %d\n"

   380

		"Non empty buckets: %d\n"

   381

		"Max collision: %d\n",

   382

		h->num_buckets, h->size, used_buckets, max_collision

   383

	);

   384

	printf("{ ");

   385

	for (i = 0; i <= max_collision; i++) {

   386

		if (usage[i] > 0) {

   387

			printf("%d:%d ", i, usage[i]);

   388

#if 0

   389

			if (i > 0) {

   390

				uint j;

   391

   392

				for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#');

   393

			}

   394

			printf("\n");

   395

#endif

   396

		}

   397

	}

   398

	printf ("}\n");

   399

}

   400

#endif

   401

   402

void clear_Hash(Hash* h, bool free_values)

   403

{

   404

	uint i;

   405

   406

#ifdef HASH_STATS

   407

	if (h->size > 2000) stat_Hash(h);

   408

#endif

   409

   410

	/* Iterate all buckets */

   411

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

   412

		if (h->buckets_in_use[i]) {

   413

			HashNode* node;

   414

   415

			h->buckets_in_use[i] = false;

   416

			/* Free the first value */

   417

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

   418

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

   419

			while (node != NULL) {

   420

				HashNode* prev = node;

   421

   422

				node = node->next;

   423

				if (free_values) free(prev->value);

   424

				free(prev);

   425

			}

   426

		}

   427

	}

   428

	h->size = 0;

   429

}

   430

   431

/* Finds the node that that saves this key pair. If it is not

   432

 * found, returns NULL. If it is found, *prev is set to the

   433

 * node before the one found, or if the node found was the first in the bucket

   434

 * to NULL. If it is not found, *prev is set to the last HashNode in the

   435

 * bucket, or NULL if it is empty. prev can also be NULL, in which case it is

   436

 * not used for output.

   437

 */

   438

static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out)

   439

{

   440

	uint hash = h->hash(key1, key2);

   441

	HashNode* result = NULL;

   442

   443

#ifdef HASH_DEBUG

   444

	debug("Looking for %u, %u", key1, key2);

   445

#endif

   446

	/* Check if the bucket is empty */

   447

	if (!h->buckets_in_use[hash]) {

   448

		if (prev_out != NULL) *prev_out = NULL;

   449

		result = NULL;

   450

	/* Check the first node specially */

   451

	} else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) {

   452

		/* Save the value */

   453

		result = h->buckets + hash;

   454

		if (prev_out != NULL) *prev_out = NULL;

   455

#ifdef HASH_DEBUG

   456

		debug("Found in first node: %p", result);

   457

#endif

   458

	/* Check all other nodes */

   459

	} else {

   460

		HashNode* prev = h->buckets + hash;

   461

		HashNode* node;

   462

   463

		for (node = prev->next; node != NULL; node = node->next) {

   464

			if (node->key1 == key1 && node->key2 == key2) {

   465

				/* Found it */

   466

				result = node;

   467

#ifdef HASH_DEBUG

   468

				debug("Found in other node: %p", result);

   469

#endif

   470

				break;

   471

			}

   472

			prev = node;

   473

		}

   474

		if (prev_out != NULL) *prev_out = prev;

   475

	}

   476

#ifdef HASH_DEBUG

   477

	if (result == NULL) debug("Not found");

   478

#endif

   479

	return result;

   480

}

   481

   482

void* Hash_Delete(Hash* h, uint key1, uint key2)

   483

{

   484

	void* result;

   485

	HashNode* prev; /* Used as output var for below function call */

   486

	HashNode* node = Hash_FindNode(h, key1, key2, &prev);

   487

   488

	if (node == NULL) {

   489

		/* not found */

   490

		result = NULL;

   491

	} else if (prev == NULL) {

   492

		/* It is in the first node, we can't free that one, so we free

   493

		 * the next one instead (if there is any)*/

   494

		/* Save the value */

   495

		result = node->value;

   496

		if (node->next != NULL) {

   497

			HashNode* next = node->next;

   498

			/* Copy the second to the first */

   499

			*node = *next;