← Back to branch summary

~ubuntu-branches/debian/squeeze/openttd/squeeze

« back to all changes in this revision

Viewing changes to src/queue.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jordi Mallach, Matthijs Kooijman, Jordi Mallach
  • Date: 2009-04-15 18:22:10 UTC
  • mfrom: (1.1.6 upstream) (2.1.3 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090415182210-22ktb8kdbp2tf3bm
[ Matthijs Kooijman ]
* New upstream release.
* Remove Debian specific desktop file, upstream provides one now. 
* Add debian/watch file.

[ Jordi Mallach ]
* Bump Standards-Version to 3.8.1, with no changes required.
* Move to debhelper compat 7. Bump Build-Depends accordingly.
* Use dh_prep.
* Add "set -e" to config script.
* Remove a few extra doc files that get installed by upstream Makefile.
* Add more complete copyright information.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/queue.cpp
1
 
/* $Id: queue.cpp 11691 2007-12-25 09:48:53Z rubidium $ */
 
1
/* $Id: queue.cpp 15718 2009-03-15 00:32:18Z rubidium $ */
2
2
 
3
 
/** @file queue.cpp */
 
3
/** @file queue.cpp Implementation of the Queue/Hash. */
4
4
 
5
5
#include "stdafx.h"
6
 
#include "openttd.h"
7
6
#include "queue.h"
8
7
#include "core/alloc_func.hpp"
9
8
 
12
11
 * Insertion Sorter
13
12
 */
14
13
 
15
 
static void InsSort_Clear(Queue* q, bool free_values)
 
14
static void InsSort_Clear(Queue *q, bool free_values)
16
15
{
17
 
        InsSortNode* node = q->data.inssort.first;
18
 
        InsSortNode* prev;
 
16
        InsSortNode *node = q->data.inssort.first;
 
17
        InsSortNode *prev;
19
18
 
20
19
        while (node != NULL) {
21
20
                if (free_values) free(node->item);
26
25
        q->data.inssort.first = NULL;
27
26
}
28
27
 
29
 
static void InsSort_Free(Queue* q, bool free_values)
 
28
static void InsSort_Free(Queue *q, bool free_values)
30
29
{
31
30
        q->clear(q, free_values);
32
31
}
33
32
 
34
 
static bool InsSort_Push(Queue* q, void* item, int priority)
 
33
static bool InsSort_Push(Queue *q, void *item, int priority)
35
34
{
36
 
        InsSortNode* newnode = MallocT<InsSortNode>(1);
 
35
        InsSortNode *newnode = MallocT<InsSortNode>(1);
37
36
 
38
 
        if (newnode == NULL) return false;
39
37
        newnode->item = item;
40
38
        newnode->priority = priority;
41
39
        if (q->data.inssort.first == NULL ||
43
41
                newnode->next = q->data.inssort.first;
44
42
                q->data.inssort.first = newnode;
45
43
        } else {
46
 
                InsSortNode* node = q->data.inssort.first;
 
44
                InsSortNode *node = q->data.inssort.first;
47
45
                while (node != NULL) {
48
46
                        if (node->next == NULL || node->next->priority >= priority) {
49
47
                                newnode->next = node->next;
56
54
        return true;
57
55
}
58
56
 
59
 
static void* InsSort_Pop(Queue* q)
 
57
static void *InsSort_Pop(Queue *q)
60
58
{
61
 
        InsSortNode* node = q->data.inssort.first;
62
 
        void* result;
 
59
        InsSortNode *node = q->data.inssort.first;
 
60
        void *result;
63
61
 
64
62
        if (node == NULL) return NULL;
65
63
        result = node->item;
69
67
        return result;
70
68
}
71
69
 
72
 
static bool InsSort_Delete(Queue* q, void* item, int priority)
 
70
static bool InsSort_Delete(Queue *q, void *item, int priority)
73
71
{
74
72
        return false;
75
73
}
76
74
 
77
 
void init_InsSort(Queue* q)
 
75
void init_InsSort(Queue *q)
78
76
{
79
77
        q->push = InsSort_Push;
80
78
        q->pop = InsSort_Pop;
99
97
 *  q->data.binaryheap.elements[i - 1] every time, we use this define. */
100
98
#define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK]
101
99
 
102
 
static void BinaryHeap_Clear(Queue* q, bool free_values)
 
100
static void BinaryHeap_Clear(Queue *q, bool free_values)
103
101
{
104
102
        /* Free all items if needed and free all but the first blocks of memory */
105
103
        uint i;
131
129
        q->data.binaryheap.blocks = 1;
132
130
}
133
131
 
134
 
static void BinaryHeap_Free(Queue* q, bool free_values)
 
132
static void BinaryHeap_Free(Queue *q, bool free_values)
135
133
{
136
134
        uint i;
137
135
 
143
141
        free(q->data.binaryheap.elements);
144
142
}
145
143
 
146
 
static bool BinaryHeap_Push(Queue* q, void* item, int priority)
 
144
static bool BinaryHeap_Push(Queue *q, void *item, int priority)
147
145
{
148
146
#ifdef QUEUE_DEBUG
149
147
        printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size);
194
192
        return true;
195
193
}
196
194
 
197
 
static bool BinaryHeap_Delete(Queue* q, void* item, int priority)
 
195
static bool BinaryHeap_Delete(Queue *q, void *item, int priority)
198
196
{
199
197
        uint i = 0;
200
198
 
253
251
        return true;
254
252
}
255
253
 
256
 
static void* BinaryHeap_Pop(Queue* q)
 
254
static void *BinaryHeap_Pop(Queue *q)
257
255
{
258
 
        void* result;
 
256
        void *result;
259
257
 
260
258
#ifdef QUEUE_DEBUG
261
259
        printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size);
271
269
        return result;
272
270
}
273
271
 
274
 
void init_BinaryHeap(Queue* q, uint max_size)
 
272
void init_BinaryHeap(Queue *q, uint max_size)
275
273
{
276
274
        assert(q != NULL);
277
275
        q->push = BinaryHeap_Push;
291
289
#endif
292
290
}
293
291
 
294
 
// Because we don't want anyone else to bother with our defines
 
292
/* Because we don't want anyone else to bother with our defines */
295
293
#undef BIN_HEAP_ARR
296
294
 
297
295
/*
298
296
 * Hash
299
297
 */
300
298
 
301
 
void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets)
 
299
void init_Hash(Hash *h, Hash_HashProc *hash, uint num_buckets)
302
300
{
303
301
        /* Allocate space for the Hash, the buckets and the bucket flags */
304
302
        uint i;
319
317
}
320
318
 
321
319
 
322
 
void delete_Hash(Hash* h, bool free_values)
 
320
void delete_Hash(Hash *h, bool free_values)
323
321
{
324
322
        uint i;
325
323
 
326
324
        /* Iterate all buckets */
327
325
        for (i = 0; i < h->num_buckets; i++) {
328
326
                if (h->buckets_in_use[i]) {
329
 
                        HashNode* node;
 
327
                        HashNode *node;
330
328
 
331
329
                        /* Free the first value */
332
330
                        if (free_values) free(h->buckets[i].value);
333
331
                        node = h->buckets[i].next;
334
332
                        while (node != NULL) {
335
 
                                HashNode* prev = node;
 
333
                                HashNode *prev = node;
336
334
 
337
335
                                node = node->next;
338
336
                                /* Free the value */
351
349
}
352
350
 
353
351
#ifdef HASH_STATS
354
 
static void stat_Hash(const Hash* h)
 
352
static void stat_Hash(const Hash *h)
355
353
{
356
354
        uint used_buckets = 0;
357
355
        uint max_collision = 0;
363
361
        for (i = 0; i < h->num_buckets; i++) {
364
362
                uint collision = 0;
365
363
                if (h->buckets_in_use[i]) {
366
 
                        const HashNode* node;
 
364
                        const HashNode *node;
367
365
 
368
366
                        used_buckets++;
369
367
                        for (node = &h->buckets[i]; node != NULL; node = node->next) collision++;
401
399
}
402
400
#endif
403
401
 
404
 
void clear_Hash(Hash* h, bool free_values)
 
402
void clear_Hash(Hash *h, bool free_values)
405
403
{
406
404
        uint i;
407
405
 
412
410
        /* Iterate all buckets */
413
411
        for (i = 0; i < h->num_buckets; i++) {
414
412
                if (h->buckets_in_use[i]) {
415
 
                        HashNode* node;
 
413
                        HashNode *node;
416
414
 
417
415
                        h->buckets_in_use[i] = false;
418
416
                        /* Free the first value */
419
417
                        if (free_values) free(h->buckets[i].value);
420
418
                        node = h->buckets[i].next;
421
419
                        while (node != NULL) {
422
 
                                HashNode* prev = node;
 
420
                                HashNode *prev = node;
423
421
 
424
422
                                node = node->next;
425
423
                                if (free_values) free(prev->value);
437
435
 * bucket, or NULL if it is empty. prev can also be NULL, in which case it is
438
436
 * not used for output.
439
437
 */
440
 
static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out)
 
438
static HashNode *Hash_FindNode(const Hash *h, uint key1, uint key2, HashNode** prev_out)
441
439
{
442
440
        uint hash = h->hash(key1, key2);
443
 
        HashNode* result = NULL;
 
441
        HashNode *result = NULL;
444
442
 
445
443
#ifdef HASH_DEBUG
446
444
        debug("Looking for %u, %u", key1, key2);
459
457
#endif
460
458
        /* Check all other nodes */
461
459
        } else {
462
 
                HashNode* prev = h->buckets + hash;
463
 
                HashNode* node;
 
460
                HashNode *prev = h->buckets + hash;
 
461
                HashNode *node;
464
462
 
465
463
                for (node = prev->next; node != NULL; node = node->next) {
466
464
                        if (node->key1 == key1 && node->key2 == key2) {
481
479
        return result;
482
480
}
483
481
 
484
 
void* Hash_Delete(Hash* h, uint key1, uint key2)
 
482
void *Hash_Delete(Hash *h, uint key1, uint key2)
485
483
{
486
 
        void* result;
487
 
        HashNode* prev; // Used as output var for below function call
488
 
        HashNode* node = Hash_FindNode(h, key1, key2, &prev);
 
484
        void *result;
 
485
        HashNode *prev; // Used as output var for below function call
 
486
        HashNode *node = Hash_FindNode(h, key1, key2, &prev);
489
487
 
490
488
        if (node == NULL) {
491
489
                /* not found */
496
494
                /* Save the value */
497
495
                result = node->value;
498
496
                if (node->next != NULL) {
499
 
                        HashNode* next = node->next;
 
497
                        HashNode *next = node->next;
500
498
                        /* Copy the second to the first */
501
499
                        *node = *next;
502
500
                        /* Free the second */
504
502
                        free(next);
505
503
#endif
506
504
                } else {
507
 
                        /* This was the last in this bucket */
508
 
                        /* Mark it as empty */
 
505
                        /* This was the last in this bucket
 
506
                         * Mark it as empty */
509
507
                        uint hash = h->hash(key1, key2);
510
508
                        h->buckets_in_use[hash] = false;
511
509
                }
512
510
        } else {
513
 
                /* It is in another node */
514
 
                /* Save the value */
 
511
                /* It is in another node
 
512
                 * Save the value */
515
513
                result = node->value;
516
514
                /* Link previous and next nodes */
517
515
                prev->next = node->next;
525
523
}
526
524
 
527
525
 
528
 
void* Hash_Set(Hash* h, uint key1, uint key2, void* value)
 
526
void *Hash_Set(Hash *h, uint key1, uint key2, void *value)
529
527
{
530
 
        HashNode* prev;
531
 
        HashNode* node = Hash_FindNode(h, key1, key2, &prev);
 
528
        HashNode *prev;
 
529
        HashNode *node = Hash_FindNode(h, key1, key2, &prev);
532
530
 
533
531
        if (node != NULL) {
534
532
                /* Found it */
535
 
                void* result = node->value;
 
533
                void *result = node->value;
536
534
 
537
535
                node->value = value;
538
536
                return result;
556
554
        return NULL;
557
555
}
558
556
 
559
 
void* Hash_Get(const Hash* h, uint key1, uint key2)
 
557
void *Hash_Get(const Hash *h, uint key1, uint key2)
560
558
{
561
 
        HashNode* node = Hash_FindNode(h, key1, key2, NULL);
 
559
        HashNode *node = Hash_FindNode(h, key1, key2, NULL);
562
560
 
563
561
#ifdef HASH_DEBUG
564
562
        debug("Found node: %p", node);
566
564
        return (node != NULL) ? node->value : NULL;
567
565
}
568
566
 
569
 
uint Hash_Size(const Hash* h)
 
567
uint Hash_Size(const Hash *h)
570
568
{
571
569
        return h->size;
572
570
}