cfengine  3.15.4
About: CFEngine is a configuration management system for configuring and maintaining Unix-like computers (using an own high level policy language). Community version.
  Fossies Dox: cfengine-3.15.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

sequence.c
Go to the documentation of this file.
1 /*
2  Copyright 2020 Northern.tech AS
3 
4  This file is part of CFEngine 3 - written and maintained by Northern.tech AS.
5 
6  This program is free software; you can redistribute it and/or modify it
7  under the terms of the GNU General Public License as published by the
8  Free Software Foundation; version 3.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program; if not, write to the Free Software
17  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
18 
19  To the extent this program is licensed as part of the Enterprise
20  versions of CFEngine, the applicable Commercial Open Source License
21  (COSL) may apply to this file if you as a licensee so wish it. See
22  included file COSL.txt.
23 */
24 
25 #include <platform.h>
26 #include <sequence.h>
27 #include <alloc.h>
28 
29 static const size_t EXPAND_FACTOR = 2;
30 
31 Seq *SeqNew(size_t initialCapacity, void (ItemDestroy) (void *item))
32 {
33  Seq *seq = xmalloc(sizeof(Seq));
34 
35  if (initialCapacity <= 0)
36  {
37  initialCapacity = 1;
38  }
39 
40  seq->capacity = initialCapacity;
41  seq->length = 0;
42  seq->data = xcalloc(sizeof(void *), initialCapacity);
43  seq->ItemDestroy = ItemDestroy;
44 
45  return seq;
46 }
47 
48 static void DestroyRange(Seq *seq, size_t start, size_t end)
49 {
50  assert(seq != NULL);
51  if (seq->ItemDestroy)
52  {
53  for (size_t i = start; i <= end; i++)
54  {
55  seq->ItemDestroy(seq->data[i]);
56  }
57  }
58 }
59 
60 void SeqDestroy(Seq *seq)
61 {
62  if (seq != NULL)
63  {
64  if (seq->length > 0)
65  {
66  DestroyRange(seq, 0, seq->length - 1);
67  }
68  SeqSoftDestroy(seq);
69  }
70 }
71 
72 void SeqSoftDestroy(Seq *seq)
73 {
74  if (seq != NULL)
75  {
76  free(seq->data);
77  free(seq);
78  }
79 }
80 
81 static void ExpandIfNeccessary(Seq *seq)
82 {
83  assert(seq != NULL);
84  assert(seq->length <= seq->capacity);
85 
86  if (seq->length == seq->capacity)
87  {
88  seq->capacity *= EXPAND_FACTOR;
89  seq->data = xrealloc(seq->data, sizeof(void *) * seq->capacity);
90  }
91 }
92 
93 void SeqSet(Seq *seq, size_t index, void *item)
94 {
95  assert(seq != NULL);
96  assert(index < SeqLength(seq));
97  if (seq->ItemDestroy)
98  {
99  seq->ItemDestroy(seq->data[index]);
100  }
101  seq->data[index] = item;
102 }
103 
104 void SeqAppend(Seq *seq, void *item)
105 {
106  assert(seq != NULL);
107  ExpandIfNeccessary(seq);
108 
109  seq->data[seq->length] = item;
110  ++(seq->length);
111 }
112 
113 void SeqAppendOnce(Seq *seq, void *item, SeqItemComparator Compare)
114 {
115  assert(seq != NULL);
116  if (SeqLookup(seq, item, Compare) == NULL)
117  {
118  SeqAppend(seq, item);
119  }
120  else
121  {
122  /* swallow the item anyway */
123  if (seq->ItemDestroy != NULL)
124  {
125  seq->ItemDestroy(item);
126  }
127  }
128 }
129 
130 void SeqAppendSeq(Seq *seq, const Seq *items)
131 {
132  for (size_t i = 0; i < SeqLength(items); i++)
133  {
134  SeqAppend(seq, SeqAt(items, i));
135  }
136 }
137 
138 void SeqRemoveRange(Seq *seq, size_t start, size_t end)
139 {
140  assert(seq != NULL);
141  assert(end < seq->length);
142  assert(start <= end);
143 
144  DestroyRange(seq, start, end);
145 
146  size_t rest_len = seq->length - end - 1;
147 
148  if (rest_len > 0)
149  {
150  memmove(seq->data + start, seq->data + end + 1, sizeof(void *) * rest_len);
151  }
152 
153  seq->length -= end - start + 1;
154 }
155 
156 void SeqRemove(Seq *seq, size_t index)
157 {
158  SeqRemoveRange(seq, index, index);
159 }
160 
161 void *SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare)
162 {
163  assert(seq != NULL);
164  for (size_t i = 0; i < seq->length; i++)
165  {
166  if (Compare(key, seq->data[i], NULL) == 0)
167  {
168  return seq->data[i];
169  }
170  }
171 
172  return NULL;
173 }
174 
175 void *SeqBinaryLookup(Seq *seq, const void *key, SeqItemComparator Compare)
176 {
177  assert(seq != NULL);
178  ssize_t index = SeqBinaryIndexOf(seq, key, Compare);
179  if (index == -1)
180  {
181  return NULL;
182  }
183  else
184  {
185  return seq->data[index];
186  }
187 }
188 
189 ssize_t SeqIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
190 {
191  assert(seq != NULL);
192  for (size_t i = 0; i < seq->length; i++)
193  {
194  if (Compare(key, seq->data[i], NULL) == 0)
195  {
196  return i;
197  }
198  }
199 
200  return -1;
201 }
202 
203 ssize_t SeqBinaryIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
204 {
205  assert(seq != NULL);
206  if (seq->length == 0)
207  {
208  return -1;
209  }
210 
211  size_t low = 0;
212  size_t high = seq->length;
213 
214  while (low < high)
215  {
216  // Invariant: low <= middle < high
217  size_t middle = low + ((high - low) >> 1); // ">> 1" is division by 2.
218  int result = Compare(key, seq->data[middle], NULL);
219  if (result == 0)
220  {
221  return middle;
222  }
223  if (result > 0)
224  {
225  low = middle + 1;
226  }
227  else
228  {
229  high = middle;
230  }
231  }
232 
233  // Not found.
234  return -1;
235 }
236 
237 static void Swap(void **l, void **r)
238 {
239  void *t = *l;
240 
241  *l = *r;
242  *r = t;
243 }
244 
245 // adopted from http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C
246 static void QuickSortRecursive(void **data, int n, SeqItemComparator Compare, void *user_data, size_t maxterm)
247 {
248  if (n < 2)
249  {
250  return;
251  }
252 
253  void *pivot = data[n / 2];
254  void **l = data;
255  void **r = data + n - 1;
256 
257  while (l <= r)
258  {
259  while (Compare(*l, pivot, user_data) < 0)
260  {
261  ++l;
262  }
263  while (Compare(*r, pivot, user_data) > 0)
264  {
265  --r;
266  }
267  if (l <= r)
268  {
269  Swap(l, r);
270  ++l;
271  --r;
272  }
273  }
274 
275  QuickSortRecursive(data, r - data + 1, Compare, user_data, maxterm + 1);
276  QuickSortRecursive(l, data + n - l, Compare, user_data, maxterm + 1);
277 }
278 
279 void SeqSort(Seq *seq, SeqItemComparator Compare, void *user_data)
280 {
281  assert(seq != NULL);
282  QuickSortRecursive(seq->data, seq->length, Compare, user_data, 0);
283 }
284 
285 Seq *SeqSoftSort(const Seq *seq, SeqItemComparator compare, void *user_data)
286 {
287  size_t length = SeqLength(seq);
288  if (length == 0)
289  {
290  return SeqNew(0, NULL);
291  }
292 
293  Seq *sorted_seq = SeqGetRange(seq, 0, length - 1);
294  SeqSort(sorted_seq, compare, user_data);
295  return sorted_seq;
296 }
297 
298 void SeqSoftRemoveRange(Seq *seq, size_t start, size_t end)
299 {
300  assert(seq != NULL);
301  assert(end < seq->length);
302  assert(start <= end);
303 
304  size_t rest_len = seq->length - end - 1;
305 
306  if (rest_len > 0)
307  {
308  memmove(seq->data + start, seq->data + end + 1, sizeof(void *) * rest_len);
309  }
310 
311  seq->length -= end - start + 1;
312 }
313 
314 void SeqClear(Seq *seq)
315 {
316  if (SeqLength(seq) > 0)
317  {
318  SeqRemoveRange(seq, 0, SeqLength(seq) - 1);
319  }
320 }
321 
322 void SeqSoftRemove(Seq *seq, size_t index)
323 {
324  SeqSoftRemoveRange(seq, index, index);
325 }
326 
327 void SeqReverse(Seq *seq)
328 {
329  assert(seq != NULL);
330  for (size_t i = 0; i < (seq->length / 2); i++)
331  {
332  Swap(&seq->data[i], &seq->data[seq->length - 1 - i]);
333  }
334 }
335 
336 Seq *SeqSplit(Seq *seq, size_t index)
337 {
338  assert(seq != NULL);
339  size_t length = SeqLength(seq);
340  assert(index <= length); // index > length is invalid
341  if (index >= length)
342  {
343  // index == length is valid, return empty sequence
344  // anything higher is error, but we will handle it anyway
345  return SeqNew(1, seq->ItemDestroy);
346  }
347 
348  Seq *ret = SeqGetRange(seq, index, length - 1);
349  assert(ret != NULL); // Our indices should be valid
350  SeqSoftRemoveRange(seq, index, length - 1);
351  return ret;
352 }
353 
354 size_t SeqLength(const Seq *seq)
355 {
356  assert(seq != NULL);
357  return seq->length;
358 }
359 
360 void SeqShuffle(Seq *seq, unsigned int seed)
361 {
362  assert(seq != NULL);
363  if (SeqLength(seq) == 0)
364  {
365  return;
366  }
367 
368  /* Store current random number state for being reset at the end of function */
369  int rand_state = rand();
370 
371  srand(seed);
372  for (size_t i = SeqLength(seq) - 1; i > 0; i--)
373  {
374  size_t j = rand() % (i + 1);
375 
376  Swap(seq->data + i, seq->data + j);
377  }
378 
379  /* Restore previous random number state */
380  srand(rand_state);
381 }
382 
383 Seq *SeqGetRange(const Seq *seq, size_t start, size_t end)
384 {
385  assert(seq != NULL);
386 
387  if ((start > end) || (start >= seq->length) || (end >= seq->length))
388  {
389  return NULL;
390  }
391 
392  Seq *sub = SeqNew(end - start + 1, seq->ItemDestroy);
393 
394  for (size_t i = start; i <= end; i++)
395  {
396  assert(i < SeqLength(seq));
397  SeqAppend(sub, SeqAt(seq, i));
398  }
399 
400  return sub;
401 }
402 
403 void *const *SeqGetData(const Seq *seq)
404 {
405  assert(seq != NULL);
406  return seq->data;
407 }
408 
409 void SeqRemoveNulls(Seq *seq)
410 {
411  assert(seq != NULL);
412  int length = SeqLength(seq);
413  int from = 0;
414  int to = 0;
415  while (from < length)
416  {
417  if (seq->data[from] == NULL)
418  {
419  ++from; // Skip NULL elements
420  }
421  else
422  {
423  // Copy elements in place, DON'T use SeqSet, which will free()
424  seq->data[to] = seq->data[from];
425  ++from;
426  ++to;
427  }
428  }
429  seq->length = to;
430 }
431 
432 Seq *SeqFromArgv(int argc, const char *const *const argv)
433 {
434  assert(argc > 0);
435  assert(argv != NULL);
436  assert(argv[0] != NULL);
437 
438  Seq *args = SeqNew(argc, NULL);
439  for (int i = 0; i < argc; ++i)
440  {
441  SeqAppend(args, (void *)argv[i]); // Discards const
442  }
443  return args;
444 }
void * xmalloc(size_t size)
Definition: alloc-mini.c:46
void * xcalloc(size_t nmemb, size_t size)
Definition: alloc-mini.c:51
void * xrealloc(void *ptr, size_t size)
Definition: alloc.c:51
void free(void *)
#define NULL
Definition: getopt1.c:56
void * SeqBinaryLookup(Seq *seq, const void *key, SeqItemComparator Compare)
Performs a binary search looking for the item matching the given key. It is the programmer's responsi...
Definition: sequence.c:175
void SeqRemove(Seq *seq, size_t index)
Remove a single item in the sequence.
Definition: sequence.c:156
void SeqSoftRemoveRange(Seq *seq, size_t start, size_t end)
Remove an inclusive range of item handles in the Sequence. A single item may be removed by specifying...
Definition: sequence.c:298
void SeqAppendOnce(Seq *seq, void *item, SeqItemComparator Compare)
Append a new item to the Sequence if it's not already present in the Sequence.
Definition: sequence.c:113
static void DestroyRange(Seq *seq, size_t start, size_t end)
Definition: sequence.c:48
Seq * SeqSoftSort(const Seq *seq, SeqItemComparator compare, void *user_data)
Returns a soft copy of the sequence sorted according to the given item comparator function.
Definition: sequence.c:285
void SeqSoftRemove(Seq *seq, size_t index)
Remove a single item handle from the sequence.
Definition: sequence.c:322
void SeqRemoveRange(Seq *seq, size_t start, size_t end)
Remove an inclusive range of items in the Sequence. A single item may be removed by specifying start ...
Definition: sequence.c:138
Seq * SeqGetRange(const Seq *seq, size_t start, size_t end)
Get soft copy of sequence according to specified range.
Definition: sequence.c:383
static void ExpandIfNeccessary(Seq *seq)
Definition: sequence.c:81
size_t SeqLength(const Seq *seq)
Length of the sequence.
Definition: sequence.c:354
Seq * SeqFromArgv(int argc, const char *const *const argv)
Definition: sequence.c:432
void SeqRemoveNulls(Seq *seq)
Definition: sequence.c:409
ssize_t SeqBinaryIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
Performs a binary search looking for the item matching the given key. It is the programmer's responsi...
Definition: sequence.c:203
Seq * SeqNew(size_t initialCapacity, void(ItemDestroy)(void *item))
Definition: sequence.c:31
static void Swap(void **l, void **r)
Definition: sequence.c:237
static const size_t EXPAND_FACTOR
Definition: sequence.c:29
ssize_t SeqIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
Linearly searches through the sequence and returns the index of the first matching object,...
Definition: sequence.c:189
void SeqSet(Seq *seq, size_t index, void *item)
Definition: sequence.c:93
void *const * SeqGetData(const Seq *seq)
Get the data segment of the sequence.
Definition: sequence.c:403
Seq * SeqSplit(Seq *seq, size_t index)
Split a sequence in two at a given index.
Definition: sequence.c:336
void SeqShuffle(Seq *seq, unsigned int seed)
Shuffle the sequence by randomly switching positions of the pointers.
Definition: sequence.c:360
static void QuickSortRecursive(void **data, int n, SeqItemComparator Compare, void *user_data, size_t maxterm)
Definition: sequence.c:246
void SeqSoftDestroy(Seq *seq)
Destroy an existing Sequence without destroying its items.
Definition: sequence.c:72
void SeqReverse(Seq *seq)
Reverses the order of the sequence.
Definition: sequence.c:327
void SeqClear(Seq *seq)
Remove all elements in sequence.
Definition: sequence.c:314
void * SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare)
Linearly searches through the sequence and return the first item considered equal to the specified ke...
Definition: sequence.c:161
void SeqSort(Seq *seq, SeqItemComparator Compare, void *user_data)
Sort a Sequence according to the given item comparator function.
Definition: sequence.c:279
void SeqDestroy(Seq *seq)
Destroy an existing Sequence.
Definition: sequence.c:60
void SeqAppendSeq(Seq *seq, const Seq *items)
Append a sequence to this sequence. Only copies pointers.
Definition: sequence.c:130
void SeqAppend(Seq *seq, void *item)
Append a new item to the Sequence.
Definition: sequence.c:104
static void * SeqAt(const Seq *seq, int i)
Definition: sequence.h:57
int(* SeqItemComparator)(const void *, const void *, void *user_data)
Function to compare two items in a Sequence.
Definition: sequence.h:100
Sequence data-structure.
Definition: sequence.h:50
size_t length
Definition: sequence.h:52
void(* ItemDestroy)(void *item)
Definition: sequence.h:54
size_t capacity
Definition: sequence.h:53
void ** data
Definition: sequence.h:51