aboutsummaryrefslogtreecommitdiffstats
path: root/structure.h
blob: 04db5a5bcebab93a5638967a9708790ff02db5da (plain)
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
/*
 * structure.h
 * decleration of different data structures and corresponding functions
 *   - stack
 *   - queue
 *   - linked list (llist)
 *   - heap
 *
 * Erik Liodden
 */

#ifndef STRUCTURE_H
#define STRUCTURE_H

/*
 * Stack
 */

struct stack {
	void *elems;
	size_t elem_size;
	int log_length;
	int alloc_length;
	void (*freefn)(void *);
};

void stack_init(struct stack *s, size_t elem_size, void (*freefn)(void *));
void stack_dispose(struct stack *s);
void stack_push(struct stack *s, void *elem_addr);
void stack_pop(struct stack *s, void *elem_addr);
void stack_peek(struct stack *s, void *elem_addr);
void stack_get(struct stack *s, void *elem_addr, int loc);
void stack_replace(struct stack *s, void *elem_addr, int loc);
int stack_length(struct stack *s);

/*
 * Queue
 */

struct queue {
	void *elems;
	size_t elem_size;
	int head;
	int tail;
	int log_length;
	int alloc_length;
	void (*freefn)(void *);
};

void queue_init(struct queue *q, size_t elem_size, void (*freefn)(void *));
void queue_dispose(struct queue *q);
void queue_enqueue(struct queue *q, void *elem_addr);
void queue_peek(struct queue *q, void *elem_addr);
void queue_dequeue(struct queue *q, void *elem_addr);
int queue_length(struct queue *q);

/*
 * Circular doubly linked list
 *
 * this is an implementation of a circular doubly linked list with a sentinal
 * node for a (potentially) cleaner implementation.
 *
 * the llist struct is the actual list and includes a functionpointer on how to
 * free nodes. the llist_node is the node in the llist and includes a pointer to
 * the data assosiated with the node as well as a freefn to free the data if
 * necessary.
 */

struct llist {
	struct llist_node *nil;
	void (*freefn)(void *);
};

struct llist_node {
	struct llist_node *prev;
	struct llist_node *next;
	void *elem;
	size_t elem_size;
	void (*freefn)(void *);
};

void llist_init(struct llist *l);
struct llist_node *llist_create_node(size_t elem_size, void (*freefn)(void *));
void llist_node_set_elem(struct llist_node *node, void *elem_addr);
void llist_insert_after(struct llist_node *node, struct llist_node *new_node);
void llist_insert_before(struct llist_node *node, struct llist_node *new_node);
void llist_insert_end(struct llist *l, struct llist_node *node);
void llist_insert_beginning(struct llist *l, struct llist_node *node);
void llist_destroy_node(struct llist_node *node);
void llist_remove_node(struct llist_node *node);
void llist_get_elem(struct llist_node *node, void *elem_addr);
void llist_dispose(struct llist *l);

/*
 * heap
 *
 * this is a max-heap
 */

struct heap {
	void *elems;
	size_t elem_size;
	int log_length;
	int alloc_length;
	void (*freefn)(void *);
	int (*compar)(const void *, const void *);
};

void heap_init(struct heap *h, size_t elem_size, void (*freefn)(void *),
		int (*compar)(const void *, const void *));
void heap_dispose(struct heap *h);
void heap_max_heapify(struct heap *h, int pos);
void heap_build_max_heap(struct heap *h);
void heap_maximum(struct heap *h, void *elem_addr);
void heap_extract_max(struct heap *h, void *elem_addr);
void heap_increase_key(struct heap *h, int pos, void *key);
void heap_max_heap_insert(struct heap *h, void *key);
int heap_length(struct heap *h);

#endif /* STRUCTURE_H */