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

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

   288

	if (q->freeq)

   289

		free(q);

   290

}

   291

   292

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

   293

{

   294

	#ifdef QUEUE_DEBUG

   295

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

   296

	#endif

   297

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

   298

		return false;

   299

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

   300

   301

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

   302

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

   303

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

   304

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

   305

		q->data.binaryheap.blocks++;

   306

#ifdef QUEUE_DEBUG

   307

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

   308

#endif

   309

	}

   310

   311

	// Add the item at the end of the array

   312

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

   313

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

   314

	q->data.binaryheap.size++;

   315

   316

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

   317

	// bigger, we switch with the parent

   318

	{

   319

		int i, j;

   320

		BinaryHeapNode temp;

   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

	#ifdef QUEUE_DEBUG

   344

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

   345

	#endif

   346

	uint i = 0;

   347

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

   348

	do {

   349

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

   350

		i++;

   351

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

   352

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

   353

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

   354

   355

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

   356

	q->data.binaryheap.size--;

   357

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

   358

   359

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

   360

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

   361

	{

   362

		uint j;

   363

		BinaryHeapNode temp;

   364

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

   365

		//   i with 1

   366

		i++;

   367

   368

		for (;;) {

   369

			j = i;

   370

			// Check if we have 2 childs

   371

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

   372

				// Is this child smaller than the parent?

   373

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

   374

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

   375

				//  This way we get that straight away!

   376

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

   377

			// Do we have one child?

   378

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

   379

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

   380

			}

   381

   382

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

   383

			if (i != j) {

   384

				temp = BIN_HEAP_ARR(j);

   385

				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);

   386

				BIN_HEAP_ARR(i) = temp;

   387

			} else {

   388

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

   389

				break;

   390

			}

   391

		}

   392

	}

   393

   394

	return true;

   395

}

   396

   397

static void* BinaryHeap_Pop(Queue* q)

   398

{

   399

	#ifdef QUEUE_DEBUG

   400

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

   401

	#endif

   402

	void* result;

   403

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

   404

		return NULL;

   405

   406

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

   407

	result = BIN_HEAP_ARR(1).item;

   408

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

   409

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

   410

   411

	return result;

   412

}

   413

   414

void init_BinaryHeap(Queue* q, uint max_size)

   415

{

   416

	assert(q);

   417

	q->push = BinaryHeap_Push;

   418

	q->pop = BinaryHeap_Pop;

   419

	q->del = BinaryHeap_Delete;

   420

	q->clear = BinaryHeap_Clear;

   421

	q->free = BinaryHeap_Free;

   422

	q->data.binaryheap.max_size = max_size;

   423

	q->data.binaryheap.size = 0;

   424

	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE

   425

	//   It autosizes when it runs out of memory

   426

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

   427

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

   428

	q->data.binaryheap.blocks = 1;

   429

	q->freeq = false;

   430

#ifdef QUEUE_DEBUG

   431

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

   432

#endif

   433

}

   434

   435

Queue* new_BinaryHeap(uint max_size) {

   436

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

   437

	init_BinaryHeap(q, max_size);

   438

	q->freeq = true;

   439

	return q;

   440

}

   441

   442

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

   443

#undef BIN_HEAP_ARR

   444

   445

/*

   446

 * Hash

   447

 */

   448

   449

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

   450

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

   451

	uint i;

   452

	assert(h);

   453

	#ifdef HASH_DEBUG

   454

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

   455

	#endif

   456

	h->hash = hash;

   457

	h->size = 0;

   458

	h->num_buckets = num_buckets;

   459

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

   460

	#ifdef HASH_DEBUG

   461

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

   462

	#endif

   463

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

   464

	h->freeh = false;

   465

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

   466

		h->buckets_in_use[i] = false;

   467

}

   468

   469

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

   470

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

   471

	init_Hash(h, hash, num_buckets);

   472

	h->freeh = true;

   473

	return h;

   474

}

   475

   476

void delete_Hash(Hash* h, bool free_values) {

   477

	uint i;

   478

	/* Iterate all buckets */

   479

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

   480

	{

   481

		if (h->buckets_in_use[i]) {

   482

			HashNode* node;

   483

			/* Free the first value */

   484

			if (free_values)

   485

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

   486

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

   487

			while (node != NULL) {

   488

				HashNode* prev = node;

   489

				node = node->next;

   490

				/* Free the value */

   491

				if (free_values)

   492

					free(prev->value);

   493

				/* Free the node */

   494

				free(prev);

   495

			}

   496

		}

   497

	}

   498

	free(h->buckets);

   499

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

   500

	 * malloc with buckets */

   501

	#ifdef HASH_DEBUG

   502

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

   503

	#endif

   504

	if (h->freeh)

   505

		free(h);

   506

}

   507

   508

#ifdef HASH_STATS

   509

static void stat_Hash(Hash* h)

   510

{