1 #include "sorted_array.h"
2
3 #include <errno.h>
4 #include <stdlib.h>
5 #include <string.h>
6 #include "log.h"
7
8 struct sorted_array {
9 void *array;
10 /* Actual number of elements in @array */
11 unsigned int count;
12 /* Total allocated slots in @array */
13 unsigned int len;
14 /* Size of each array element */
15 size_t size;
16 /* Comparison function for element insertion */
17 sarray_cmp cmp;
18
19 unsigned int refcount;
20 };
21
22 struct sorted_array *
sarray_create(size_t elem_size,sarray_cmp cmp)23 sarray_create(size_t elem_size, sarray_cmp cmp)
24 {
25 struct sorted_array *result;
26
27 result = malloc(sizeof(struct sorted_array));
28 if (result == NULL)
29 return NULL;
30
31 result->array = calloc(8, elem_size);
32 if (result->array == NULL) {
33 free(result);
34 return NULL;
35 }
36 result->count = 0;
37 result->len = 8;
38 result->size = elem_size;
39 result->cmp = cmp;
40 result->refcount = 1;
41
42 return result;
43 }
44
45 void
sarray_get(struct sorted_array * sarray)46 sarray_get(struct sorted_array *sarray)
47 {
48 sarray->refcount++;
49 }
50
51 void
sarray_put(struct sorted_array * sarray)52 sarray_put(struct sorted_array *sarray)
53 {
54 sarray->refcount--;
55 if (sarray->refcount == 0) {
56 free(sarray->array);
57 free(sarray);
58 }
59 }
60
61 /* Does not check boundaries. */
62 static void *
get_nth_element(struct sorted_array * sarray,unsigned int index)63 get_nth_element(struct sorted_array *sarray, unsigned int index)
64 {
65 return ((char *)sarray->array) + index * sarray->size;
66 }
67
68 /**
69 * Returns success only if @new can be added to @array.
70 * (Meaning, returns success if @new is larger than all of the elements in
71 * @array.)
72 */
73 static int
compare(struct sorted_array * sarray,void * new)74 compare(struct sorted_array *sarray, void *new)
75 {
76 enum sarray_comparison cmp;
77
78 if (sarray->count == 0)
79 return 0;
80
81 cmp = sarray->cmp(get_nth_element(sarray, sarray->count - 1), new);
82 switch (cmp) {
83 case SACMP_EQUAL:
84 return -EEQUAL;
85 case SACMP_CHILD:
86 return -ECHILD2;
87 case SACMP_PARENT:
88 return -EPARENT;
89 case SACMP_LEFT:
90 return -ELEFT;
91 case SACMP_RIGHT:
92 return 0;
93 case SACMP_ADJACENT_LEFT:
94 return -EADJLEFT;
95 case SACMP_ADJACENT_RIGHT:
96 return -EADJRIGHT;
97 case SACMP_INTERSECTION:
98 return -EINTERSECTION;
99 }
100
101 pr_crit("Unknown comparison value: %u", cmp);
102 }
103
104 int
sarray_add(struct sorted_array * sarray,void * element)105 sarray_add(struct sorted_array *sarray, void *element)
106 {
107 int error;
108 void *tmp;
109
110 error = compare(sarray, element);
111 if (error)
112 return error;
113
114 if (sarray->count >= sarray->len) {
115 tmp = realloc(sarray->array, 2 * sarray->len * sarray->size);
116 if (tmp == NULL)
117 return pr_enomem();
118 sarray->array = tmp;
119 sarray->len *= 2;
120 }
121
122 memcpy(get_nth_element(sarray, sarray->count), element, sarray->size);
123 sarray->count++;
124 return 0;
125 }
126
127 bool
sarray_empty(struct sorted_array * sarray)128 sarray_empty(struct sorted_array *sarray)
129 {
130 return (sarray == NULL) || (sarray->count == 0);
131 }
132
133 bool
sarray_contains(struct sorted_array * sarray,void * elem)134 sarray_contains(struct sorted_array *sarray, void *elem)
135 {
136 unsigned int left, mid, right;
137 enum sarray_comparison cmp;
138
139 if (sarray == NULL || sarray->count == 0)
140 return false;
141
142 left = 0;
143 right = sarray->count - 1;
144
145 while (left <= right) {
146 mid = left + (right - left) / 2;
147 cmp = sarray->cmp(get_nth_element(sarray, mid), elem);
148 switch (cmp) {
149 case SACMP_LEFT:
150 case SACMP_ADJACENT_LEFT:
151 if (mid == 0) /* Prevents underflow */
152 return false;
153 right = mid - 1;
154 continue;
155 case SACMP_RIGHT:
156 case SACMP_ADJACENT_RIGHT:
157 if (mid == sarray->count - 1)
158 return false;
159 left = mid + 1;
160 continue;
161 case SACMP_EQUAL:
162 case SACMP_CHILD:
163 return true;
164 case SACMP_PARENT:
165 case SACMP_INTERSECTION:
166 return false;
167 }
168
169 pr_crit("Unknown comparison value: %u", cmp);
170 }
171
172 return false;
173 }
174
175 int
sarray_foreach(struct sorted_array * sarray,sarray_foreach_cb cb,void * arg)176 sarray_foreach(struct sorted_array *sarray, sarray_foreach_cb cb, void *arg)
177 {
178 unsigned int index;
179 int error;
180
181 for (index = 0; index < sarray->count; index++) {
182 error = cb(get_nth_element(sarray, index), arg);
183 if (error)
184 return error;
185 }
186
187 return 0;
188 }
189
sarray_err2str(int error)190 char const *sarray_err2str(int error)
191 {
192 switch (abs(error)) {
193 case EEQUAL:
194 return "Resource equals an already existing resource";
195 case ECHILD2:
196 return "Resource is a subset of an already existing resource";
197 case EPARENT:
198 return "Resource is a superset of an already existing resource";
199 case ELEFT:
200 return "Resource sequence is not properly sorted";
201 case EADJLEFT:
202 case EADJRIGHT:
203 return "Resource is adjacent to an existing resource (they are supposed to be aggregated)";
204 case EINTERSECTION:
205 return "Resource intersects with an already existing resource";
206 }
207
208 return strerror(error);
209 }
210