author | truelight |
Thu, 24 Mar 2005 14:43:40 +0000 | |
changeset 1540 | 6eef12dab5bf |
parent 1093 | 4fdc46eaf423 |
child 1661 | f3799f2c84fa |
permissions | -rw-r--r-- |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
1 |
#ifndef QUEUE_H |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
2 |
#define QUEUE_H |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
3 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
4 |
//#define NOFREE |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
5 |
//#define QUEUE_DEBUG |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
6 |
//#define HASH_DEBUG |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
7 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
8 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
9 |
typedef struct Queue Queue; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
10 |
typedef bool Queue_PushProc(Queue* q, void* item, int priority); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
11 |
typedef void* Queue_PopProc(Queue* q); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
12 |
typedef bool Queue_DeleteProc(Queue* q, void* item, int priority); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
13 |
typedef void Queue_ClearProc(Queue* q, bool free_values); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
14 |
typedef void Queue_FreeProc(Queue* q, bool free_values); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
15 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
16 |
typedef struct InsSortNode InsSortNode; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
17 |
struct InsSortNode { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
18 |
void* item; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
19 |
int priority; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
20 |
InsSortNode* next; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
21 |
}; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
22 |
typedef struct BinaryHeapNode BinaryHeapNode; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
23 |
struct BinaryHeapNode { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
24 |
void* item; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
25 |
int priority; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
26 |
}; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
27 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
28 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
29 |
struct Queue{ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
30 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
31 |
* Pushes an element into the queue, at the appropriate place for the queue. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
32 |
* Requires the queue pointer to be of an appropriate type, of course. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
33 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
34 |
Queue_PushProc* push; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
35 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
36 |
* Pops the first element from the queue. What exactly is the first element, |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
37 |
* is defined by the exact type of queue. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
38 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
39 |
Queue_PopProc* pop; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
40 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
41 |
* Deletes the item from the queue. priority should be specified if |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
42 |
* known, which speeds up the deleting for some queue's. Should be -1 |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
43 |
* if not known. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
44 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
45 |
Queue_DeleteProc* del; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
46 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
47 |
/* Clears the queue, by removing all values from it. It's state is |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
48 |
* effectively reset. If free_items is true, each of the items cleared |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
49 |
* in this way are free()'d. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
50 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
51 |
Queue_ClearProc* clear; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
52 |
/* Frees the queue, by reclaiming all memory allocated by it. After |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
53 |
* this it is no longer usable. If free_items is true, any remaining |
201
c40d343115f8
(svn r202) -Codechange: I missed some files with trailing spaces.. this should be
truelight
parents:
110
diff
changeset
|
54 |
* items are free()'d too. |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
55 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
56 |
Queue_FreeProc* free; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
57 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
58 |
union { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
59 |
struct { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
60 |
uint max_size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
61 |
uint size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
62 |
void** elements; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
63 |
} stack; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
64 |
struct { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
65 |
uint max_size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
66 |
uint head; /* The index where the last element should be inserted */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
67 |
uint tail; /* The index where the next element should be read */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
68 |
void** elements; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
69 |
} fifo; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
70 |
struct { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
71 |
InsSortNode* first; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
72 |
} inssort; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
73 |
struct { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
74 |
uint max_size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
75 |
uint size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
76 |
uint blocks; /* The amount of blocks for which space is reserved in elements */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
77 |
BinaryHeapNode** elements; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
78 |
} binaryheap; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
79 |
} data; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
80 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
81 |
/* If true, this struct will be free'd when the |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
82 |
* Queue is deleted. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
83 |
bool freeq; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
84 |
}; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
85 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
86 |
/* Initializes a stack and allocates internal memory. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
87 |
void init_Stack(Queue* q, uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
88 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
89 |
/* Allocate a new stack with a maximum of max_size elements. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
90 |
Queue* new_Stack(uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
91 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
92 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
93 |
* Fifo |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
94 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
95 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
96 |
/* Initializes a fifo and allocates internal memory for maximum of max_size |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
97 |
* elements */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
98 |
void init_Fifo(Queue* q, uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
99 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
100 |
/* Allocate a new fifo and initializes it with a maximum of max_size elements. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
101 |
Queue* new_Fifo(uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
102 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
103 |
Queue* new_Fifo_in_buffer(uint max_size, void* buffer); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
104 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
105 |
int build_Fifo(void* buffer, uint size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
106 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
107 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
108 |
* Insertion Sorter |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
109 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
110 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
111 |
/* Initializes a inssort and allocates internal memory. There is no maximum |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
112 |
* size */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
113 |
void init_InsSort(Queue* q); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
114 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
115 |
/* Allocate a new fifo and initializes it. There is no maximum size */ |
1093
4fdc46eaf423
(svn r1594) Convert all undefined parameter lists to (void) and add the appropriate warning flags in the Makefile
tron
parents:
201
diff
changeset
|
116 |
Queue* new_InsSort(void); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
117 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
118 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
119 |
* Binary Heap |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
120 |
* For information, see: |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
121 |
* http://www.policyalmanac.org/games/binaryHeaps.htm |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
122 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
123 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
124 |
/* The amount of elements that will be malloc'd at a time */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
125 |
#define BINARY_HEAP_BLOCKSIZE_BITS 10 |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
126 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
127 |
/* Initializes a binary heap and allocates internal memory for maximum of |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
128 |
* max_size elements */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
129 |
void init_BinaryHeap(Queue* q, uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
130 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
131 |
/* Allocate a new binary heap and initializes it with a maximum of max_size |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
132 |
* elements. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
133 |
Queue* new_BinaryHeap(uint max_size); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
134 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
135 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
136 |
* Hash |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
137 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
138 |
typedef struct HashNode HashNode; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
139 |
struct HashNode { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
140 |
uint key1; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
141 |
uint key2; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
142 |
void* value; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
143 |
HashNode* next; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
144 |
}; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
145 |
/* Generates a hash code from the given key pair. You should make sure that |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
146 |
* the resulting range is clearly defined. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
147 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
148 |
typedef uint Hash_HashProc(uint key1, uint key2); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
149 |
typedef struct Hash { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
150 |
/* The hash function used */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
151 |
Hash_HashProc* hash; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
152 |
/* The amount of items in the hash */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
153 |
uint size; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
154 |
/* The number of buckets allocated */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
155 |
uint num_buckets; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
156 |
/* A pointer to an array of num_buckets buckets. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
157 |
HashNode* buckets; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
158 |
/* A pointer to an array of numbuckets booleans, which will be true if |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
159 |
* there are any Nodes in the bucket */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
160 |
bool* buckets_in_use; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
161 |
/* If true, buckets will be freed in delete_hash */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
162 |
bool freeb; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
163 |
/* If true, the pointer to this struct will be freed in delete_hash */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
164 |
bool freeh; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
165 |
} Hash; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
166 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
167 |
/* Call these function to manipulate a hash */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
168 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
169 |
/* Deletes the value with the specified key pair from the hash and returns |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
170 |
* that value. Returns NULL when the value was not present. The value returned |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
171 |
* is _not_ free()'d! */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
172 |
void* Hash_Delete(Hash* h, uint key1, uint key2); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
173 |
/* Sets the value associated with the given key pair to the given value. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
174 |
* Returns the old value if the value was replaced, NULL when it was not yet present. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
175 |
void* Hash_Set(Hash* h, uint key1, uint key2, void* value); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
176 |
/* Gets the value associated with the given key pair, or NULL when it is not |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
177 |
* present. */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
178 |
void* Hash_Get(Hash* h, uint key1, uint key2); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
179 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
180 |
/* Call these function to create/destroy a hash */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
181 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
182 |
/* Builds a new hash, with num_buckets buckets. Make sure that hash() always |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
183 |
* returns a hash less than num_buckets! Call delete_hash after use */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
184 |
Hash* new_Hash(Hash_HashProc* hash, int num_buckets); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
185 |
/* Builds a new hash in an existing struct. Make sure that hash() always |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
186 |
* returns a hash less than num_buckets! Call delete_hash after use */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
187 |
void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
188 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
189 |
* Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
190 |
* & friends. If free is true, it will call free() on all the values that |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
191 |
* are left in the hash. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
192 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
193 |
void delete_Hash(Hash* h, bool free_values); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
194 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
195 |
* Cleans the hash, but keeps the memory allocated |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
196 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
197 |
void clear_Hash(Hash* h, bool free_values); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
198 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
199 |
* Gets the current size of the Hash |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
200 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
201 |
uint Hash_Size(Hash* h); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
202 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
107
diff
changeset
|
203 |
#endif /* QUEUE_H */ |