Mercurial > data_structures

view src/pqueue.c @ 9:abdba37f67a2

find changesets by author, revision, files, or words in the commit message
Red-black tree in progress. Linked list needs iterators redone, also in progress. Sleepy.
author Eris Caffee <discordia@eldalin.com>
date Fri, 28 Sep 2012 03:08:25 -0500
parents b49d814f20a4
children
line source
1 #include <stdlib.h>
2
3 #include "pqueue.h"
4
5 struct pqueue
6 {
7 void ** data;
8 size_t max;
9 size_t size;
10 bool (*comp)(void const * const a, void const * const b);
11 };
12
13 ////////////////////////////////////////////////////////////////////////////////
14 // comp should return true if *a comp *b.
15 // So, for a min priority queue, comp will be defined to return true if *a < *b,
16 // whereas for a max priority queue comp will be defined to return true if *a > *b,
17
18 struct pqueue *
19 pqueue_new(size_t max, bool (*comp)(void const * const a, void const * const b))
20 {
21 if ( (0 == max) || (NULL == comp) )
22 return NULL;
23
24 struct pqueue * pq = malloc(sizeof(struct pqueue));
25 if (NULL == pq)
26 return NULL;
27
28 pq->max = max;
29 pq->size = 0;
30 pq->comp = comp;
31
32 // Allocate space for max+1 since we are going to waste the first element in order to use a one based array.
33 pq->data = malloc((1 + pq->max) * sizeof(void *));
34 if (NULL == pq->data)
35 {
36 free(pq);
37 return NULL;
38 }
39
40 return pq;
41 }
42
43
44 ////////////////////////////////////////////////////////////////////////////////
45 void
46 pqueue_delete(struct pqueue * pq)
47 {
48 if (NULL != pq)
49 {
50 free(pq->data);
51 free(pq);
52 }
53 }
54
55 ////////////////////////////////////////////////////////////////////////////////
56 void *
57 pqueue_push(struct pqueue * pq, void * elem)
58 {
59 if ( (NULL == pq) || (NULL == elem) )
60 return NULL;
61
62 if (pq->size == pq->max)
63 return NULL;
64
65 pq->size++;
66 pq->data[pq->size] = elem;
67
68 // sift up
69 void * temp;
70 size_t i, parent;
71 for (i = pq->size, parent = i/2;
72 (i > 1) && (! pq->comp(pq->data[parent], pq->data[i]));
73 i = parent, parent = i/2)
74 {
75 temp = pq->data[i];
76 pq->data[i] = pq->data[parent];
77 pq->data[parent] = temp;
78 }
79
80 return elem;
81 }
82
83
84 ////////////////////////////////////////////////////////////////////////////////
85 void *
86 pqueue_pop(struct pqueue * pq)
87 {
88 if ( (NULL == pq) || (0 == pq->size) )
89 return NULL;
90
91 void * val = pq->data[1];
92
93 pq->data[1] = pq->data[pq->size];
94 pq->size--;
95
96 // sift down
97 void * temp;
98 size_t i, child;
99 for (i = 1; (child = 2*i) <= pq->size; i = child)
100 {
101 if ( (child+1 <= pq->size) && (pq->comp(pq->data[child+1], pq->data[child])) )
102 child++;
103 if (pq->comp(pq->data[child], pq->data[i]))
104 {
105 temp = pq->data[i];
106 pq->data[i] = pq->data[child];
107 pq->data[child] = temp;
108 }
109 else
110 break;
111 }
112
113 return val;
114 }
115
116
117 ////////////////////////////////////////////////////////////////////////////////
118 void *
119 pqueue_peek(struct pqueue * pq)
120 {
121 if ( (NULL == pq) || (0 == pq->size) )
122 return NULL;
123
124 return pq->data[1];
125 }
126
127 ////////////////////////////////////////////////////////////////////////////////
128 size_t
129 pqueue_size(struct pqueue * pq)
130 {
131 if (NULL == pq)
132 return 0;
133
134 return pq->size;
135 }