1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
/** @file common.h
*
* @brief common data structure
*
* @author Hanjie Wu (hanjiew)
* @bug No functional bugs
*/
#ifndef _COMMON_H_
#define _COMMON_H_
#include <stdlib.h>
/**
* a queue node
*/
typedef struct queue_s {
struct queue_s* next;
struct queue_s* prev;
} queue_t;
/**
* @brief insert a node to the head of a queue
* @param queue queue
* @param t the node
*/
void queue_insert_head(queue_t** queue, queue_t* t);
/**
* @brief insert a node to the tail of a queue
* @param queue queue
* @param t the node
*/
void queue_insert_tail(queue_t** queue, queue_t* t);
/**
* @brief remove a node from the head of a queue
* @param queue queue
* @return the node removed
*/
queue_t* queue_remove_head(queue_t** queue);
/**
* @brief remove a node from the tail of a queue
* @param queue queue
* @return the node removed
*/
queue_t* queue_remove_tail(queue_t** queue);
/**
* @brief detach a node from the a queue
* @param queue queue
* @param t the node to be detached
*/
void queue_detach(queue_t** queue, queue_t* t);
/** get the enclose object of a queue node */
#define queue_data(queue, type, member) \
(type*)((char*)queue - offsetof(type, member))
/**
* a rbtree node
*/
typedef struct rb_s {
int key;
int color;
struct rb_s* parent;
struct rb_s* left;
struct rb_s* right;
} rb_t;
/** this color can have childs of any color */
#define RB_BLACK 0
/** this color can only have childs of the color mentioned above */
#define RB_RED 1
/** used to represent NULL in rbtrees */
extern rb_t rb_nil;
/**
* @brief find a node with key
* @param root rbtree root
* @param key key to find
* @return rb_nil if not found, else the node
*/
rb_t* rb_find(rb_t* root, int key);
/**
* @brief insert a node to rbtree
* @param root rbtree root
* @param node the node to insert
*/
void rb_insert(rb_t** root, rb_t* node);
/**
* @brief delete a node from rbtree
* @param root rbtree root
* @param node the node to delete
*/
void rb_delete(rb_t** root, rb_t* node);
/**
* @brief find the node with minimum key in rbtree
* @param root rbtree root
* @return rb_nil if rbtree is empty, otherwise the node
*/
rb_t* rb_min(rb_t* root);
/**
* @brief find the node with the samllest key which is greater than node's key
* @param root rbtree root
* @param node the node to compare
* @return rb_nil if no such node exist, otherwise the node
*/
rb_t* rb_next(rb_t* node);
/** get the enclose object of a rbtree node */
#define rb_data(rb, type, member) (type*)((char*)rb - offsetof(type, member))
/**
* a vector
*/
typedef struct vector_s {
int current;
int size;
int elem_size;
char* array;
} vector_t;
/**
* @brief initializa a vector
* @param v the vector
* @param elem_size size of element
* @param init_size initial size of vector
* @return -1 on failure, 0 on success
*/
int vector_init(vector_t* v, int elem_size, int init_size);
/**
* @brief get the size of a vector
* @param v the vector
* @return size
*/
int vector_size(vector_t* v);
/**
* @brief push an element to the back of v
* @param v vector
* @param elem element
* @return -1 on failure, 0 on success
*/
int vector_push(vector_t* v, void* elem);
/**
* @brief remove an element from the back of v
* @param v vector
*/
void vector_pop(vector_t* v);
/**
* @brief remove an element at index index
* @param v vector
* @param index index
*/
void vector_remove(vector_t* v, int index);
/**
* @brief return a pointer to the element at index in v
* @param v vector
* @param index index
* @return the element
*/
void* vector_at(vector_t* v, int index);
/**
* @brief free a vector's resource
* @param v vector
*/
void vector_free(vector_t* v);
/**
* a node in heap
*/
typedef struct heap_node_s {
int key;
void* value;
} heap_node_t;
/**
* a minimum heap
*/
typedef vector_t heap_t;
/**
* heap is only used for timer and we choose this size because 8 is a common
* number in computer science and no other size make more sense than this one
*/
#define INITIAL_HEAP_SIZE (8)
/**
* @brief initializa a heap
* @param heap the heap
* @return -1 on failure, 0 on success
*/
int heap_init(heap_t* heap);
/**
* @brief insert a node into heap
* @param heap the heap
* @param node the node
* @return -1 on failure, 0 on success
*/
int heap_insert(heap_t* heap, heap_node_t* node);
/**
* @brief peak the top of a heap
* @param heap the heap
* @return top node of the heap or NULL if heap is empty
*/
heap_node_t* heap_peak(heap_t* heap);
/**
* @brief remove the top node from heap
* @param heap the heap
*/
void heap_pop(heap_t* heap);
#endif
|
