1

/* $Id$ */

     2

     3

/** @file queue.cpp Implementation of the Queue/Hash. */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "queue.h"

     8

#include "core/alloc_func.hpp"

     9

    10

    11

/*

    12

 * Insertion Sorter

    13

 */

    14

    15

static void InsSort_Clear(Queue* q, bool free_values)

    16

{

    17

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

    18

	InsSortNode* prev;

    19

    20

	while (node != NULL) {

    21

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

    22

		prev = node;

    23

		node = node->next;

    24

		free(prev);

    25

	}

    26

	q->data.inssort.first = NULL;

    27

}

    28

    29

static void InsSort_Free(Queue* q, bool free_values)

    30

{

    31

	q->clear(q, free_values);

    32

}

    33

    34

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

    35

{

    36

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

    37

    38

	if (newnode == NULL) return false;

    39

	newnode->item = item;

    40

	newnode->priority = priority;

    41

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

    42

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

    43

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

    44

		q->data.inssort.first = newnode;

    45

	} else {

    46

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

    47

		while (node != NULL) {

    48

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

    49

				newnode->next = node->next;

    50

				node->next = newnode;

    51

				break;

    52

			}

    53

			node = node->next;

    54

		}

    55

	}

    56

	return true;

    57

}

    58

    59

static void* InsSort_Pop(Queue* q)

    60

{

    61

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

    62

	void* result;

    63

    64

	if (node == NULL) return NULL;

    65

	result = node->item;

    66

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

    67

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

    68

	free(node);

    69

	return result;

    70

}

    71

    72

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

    73

{

    74

	return false;

    75

}

    76

    77

void init_InsSort(Queue* q)

    78

{

    79

	q->push = InsSort_Push;

    80

	q->pop = InsSort_Pop;

    81

	q->del = InsSort_Delete;

    82

	q->clear = InsSort_Clear;

    83

	q->free = InsSort_Free;

    84

	q->data.inssort.first = NULL;

    85

}

    86

    87

    88

/*

    89

 * Binary Heap

    90

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

    91

 */

    92

    93

#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)

    94

#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)

    95

    96

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

    97

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

    98

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

    99

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

   100

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

   101

   102

static void BinaryHeap_Clear(Queue* q, bool free_values)

   103

{

   104

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

   105

	uint i;

   106

	uint j;

   107

   108

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

   109

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

   110

			/* No more allocated blocks */

   111

			break;

   112

		}

   113

		/* For every allocated block */

   114

		if (free_values) {

   115

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

   116

				/* For every element in the block */

   117

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

   118

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

   119

					break; // We're past the last element

   120

				}

   121

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

   122

			}

   123

		}

   124

		if (i != 0) {

   125

			/* Leave the first block of memory alone */

   126

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

   127

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

   128

		}

   129

	}

   130

	q->data.binaryheap.size = 0;

   131

	q->data.binaryheap.blocks = 1;

   132

}

   133

   134

static void BinaryHeap_Free(Queue* q, bool free_values)

   135

{

   136

	uint i;

   137

   138

	q->clear(q, free_values);

   139

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

   140

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

   141

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

   142

	}

   143

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

   144

}

   145

   146

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

   147

{

   148

#ifdef QUEUE_DEBUG

   149

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

   150

#endif

   151

   152

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

   153

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

   154

   155

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

   156

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

   157

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

   158

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

   159

		q->data.binaryheap.blocks++;

   160

#ifdef QUEUE_DEBUG

   161

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

   162

#endif

   163

	}

   164

   165

	/* Add the item at the end of the array */

   166

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

   167

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

   168

	q->data.binaryheap.size++;

   169

   170

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

   171

	 * bigger, we switch with the parent */

   172

	{

   173

		BinaryHeapNode temp;

   174

		int i;

   175

		int j;

   176

   177

		i = q->data.binaryheap.size;

   178

		while (i > 1) {

   179

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

   180

			j = i / 2;

   181

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

   182

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

   183

				temp = BIN_HEAP_ARR(j);

   184

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   185

				BIN_HEAP_ARR(i) = temp;

   186

				i = j;

   187

			} else {

   188

				/* It is not, we're done! */

   189

				break;

   190

			}

   191

		}

   192

	}

   193

   194

	return true;

   195

}

   196

   197

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

   198

{

   199

	uint i = 0;

   200

   201

#ifdef QUEUE_DEBUG

   202

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

   203

#endif

   204

   205

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

   206

	do {

   207

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

   208

		i++;

   209

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

   210

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

   211

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

   212

   213

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

   214

	q->data.binaryheap.size--;

   215

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

   216

   217

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

   218

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

   219

	{

   220

		uint j;

   221

		BinaryHeapNode temp;

   222

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

   223

		 * increase i by 1

   224

		 */

   225

		i++;

   226

   227

		for (;;) {

   228

			j = i;

   229

			/* Check if we have 2 childs */

   230

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

   231

				/* Is this child smaller than the parent? */

   232

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

   233

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

   234

				 *  This way we get that straight away! */

   235

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

   236

			/* Do we have one child? */

   237

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

   238

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

   239

			}

   240

   241

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

   242

			if (i != j) {

   243

				temp = BIN_HEAP_ARR(j);

   244

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   245

				BIN_HEAP_ARR(i) = temp;

   246

			} else {

   247

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

   248

				break;

   249

			}

   250

		}

   251

	}

   252

   253

	return true;

   254

}

   255

   256

static void* BinaryHeap_Pop(Queue* q)

   257

{

   258

	void* result;

   259

   260

#ifdef QUEUE_DEBUG

   261

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

   262

#endif

   263

   264

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

   265

   266

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

   267

	result = BIN_HEAP_ARR(1).item;

   268

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

   269

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

   270

   271

	return result;

   272

}

   273

   274

void init_BinaryHeap(Queue* q, uint max_size)

   275

{

   276

	assert(q != NULL);

   277

	q->push = BinaryHeap_Push;

   278

	q->pop = BinaryHeap_Pop;

   279

	q->del = BinaryHeap_Delete;

   280

	q->clear = BinaryHeap_Clear;

   281

	q->free = BinaryHeap_Free;

   282

	q->data.binaryheap.max_size = max_size;

   283

	q->data.binaryheap.size = 0;

   284

	/* We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   285

	 *   It autosizes when it runs out of memory */

   286

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

   287

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

   288

	q->data.binaryheap.blocks = 1;

   289

#ifdef QUEUE_DEBUG

   290

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

   291

#endif

   292

}

   293

   294

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

   295

#undef BIN_HEAP_ARR

   296

   297

/*

   298

 * Hash

   299

 */

   300

   301

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

   302

{

   303

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

   304

	uint i;

   305

   306

	assert(h != NULL);

   307

#ifdef HASH_DEBUG

   308

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

   309

#endif

   310

	h->hash = hash;

   311

	h->size = 0;

   312

	h->num_buckets = num_buckets;

   313

	h->buckets = (HashNode*)MallocT<byte>(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));

   314

#ifdef HASH_DEBUG

   315

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

   316

#endif

   317

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

   318

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

   319

}

   320

   321

   322

void delete_Hash(Hash* h, bool free_values)

   323

{

   324

	uint i;

   325

   326

	/* Iterate all buckets */

   327

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

   328

		if (h->buckets_in_use[i]) {

   329

			HashNode* node;

   330

   331

			/* Free the first value */

   332

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

   333

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

   334

			while (node != NULL) {

   335

				HashNode* prev = node;

   336

   337

				node = node->next;

   338

				/* Free the value */

   339

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

   340

				/* Free the node */

   341

				free(prev);

   342

			}

   343

		}

   344

	}

   345

	free(h->buckets);

   346

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

   347

	 * malloc with buckets */

   348

#ifdef HASH_DEBUG

   349

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

   350

#endif

   351

}

   352

   353

#ifdef HASH_STATS

   354

static void stat_Hash(const Hash* h)

   355

{

   356

	uint used_buckets = 0;

   357

	uint max_collision = 0;

   358

	uint max_usage = 0;

   359

	uint usage[200];

   360

	uint i;

   361

   362

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

   363

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

   364

		uint collision = 0;

   365

		if (h->buckets_in_use[i]) {

   366

			const HashNode* node;

   367

   368

			used_buckets++;

   369

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

   370

			if (collision > max_collision) max_collision = collision;

   371

		}

   372

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

   373

		usage[collision]++;

   374

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

   375

			max_usage = usage[collision];

   376

		}

   377

	}

   378

	printf(

   379

		"---\n"

   380

		"Hash size: %d\n"

   381

		"Nodes used: %d\n"

   382

		"Non empty buckets: %d\n"

   383

		"Max collision: %d\n",

   384

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

   385

	);

   386

	printf("{ ");

   387

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

   388

		if (usage[i] > 0) {

   389

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

   390

#if 0

   391

			if (i > 0) {

   392

				uint j;

   393

   394

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

   395

			}

   396

			printf("\n");

   397

#endif

   398

		}

   399

	}

   400

	printf ("}\n");

   401

}

   402

#endif

   403

   404

void clear_Hash(Hash* h, bool free_values)

   405

{

   406

	uint i;

   407

   408

#ifdef HASH_STATS

   409

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

   410

#endif

   411

   412

	/* Iterate all buckets */

   413

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

   414

		if (h->buckets_in_use[i]) {

   415

			HashNode* node;

   416

   417

			h->buckets_in_use[i] = false;

   418

			/* Free the first value */

   419

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

   420

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

   421

			while (node != NULL) {

   422

				HashNode* prev = node;

   423

   424

				node = node->next;

   425

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

   426

				free(prev);

   427

			}

   428

		}

   429

	}

   430

	h->size = 0;

   431

}

   432

   433

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

   434

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

   435

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

   436

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

   437

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

   438

 * not used for output.

   439

 */

   440

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

   441

{

   442

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

   443

	HashNode* result = NULL;

   444

   445

#ifdef HASH_DEBUG

   446

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

   447

#endif

   448

	/* Check if the bucket is empty */

   449

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

   450

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

   451

		result = NULL;

   452

	/* Check the first node specially */

   453

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

   454

		/* Save the value */

   455

		result = h->buckets + hash;

   456

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

   457

#ifdef HASH_DEBUG

   458

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

   459

#endif

   460

	/* Check all other nodes */

   461

	} else {

   462

		HashNode* prev = h->buckets + hash;

   463

		HashNode* node;

   464

   465

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

   466

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

   467

				/* Found it */

   468

				result = node;

   469

#ifdef HASH_DEBUG

   470

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

   471

#endif

   472

				break;

   473

			}

   474

			prev = node;

   475

		}

   476

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

   477

	}

   478

#ifdef HASH_DEBUG

   479

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

   480

#endif

   481

	return result;

   482

}

   483

   484

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

   485

{

   486

	void* result;

   487

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

   488

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

   489

   490

	if (node == NULL) {

   491

		/* not found */

   492

		result = NULL;

   493

	} else if (prev == NULL) {

   494

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

   495

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

   496

		/* Save the value */