/src/core/libntech/libutils/sequence.c

Source (jump to first uncovered line)
/*
  Copyright 2023 Northern.tech AS

  This file is part of CFEngine 3 - written and maintained by Northern.tech AS.

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.

  To the extent this program is licensed as part of the Enterprise
  versions of CFEngine, the applicable Commercial Open Source License
  (COSL) may apply to this file if you as a licensee so wish it. See
  included file COSL.txt.
*/

#include <platform.h>
#include <sequence.h>
#include <alloc.h>

static const size_t EXPAND_FACTOR = 2;

Seq *SeqNew(size_t initialCapacity, void (ItemDestroy) (void *item))
{
    Seq *seq = xmalloc(sizeof(Seq));

    if (initialCapacity <= 0)
    {
        initialCapacity = 1;
    }

    seq->capacity = initialCapacity;
    seq->length = 0;
    seq->data = xcalloc(sizeof(void *), initialCapacity);
    seq->ItemDestroy = ItemDestroy;

    return seq;
}

static void DestroyRange(Seq *seq, size_t start, size_t end)
{
    assert(seq != NULL);
    if (seq->ItemDestroy)
    {
        for (size_t i = start; i <= end; i++)
        {
            seq->ItemDestroy(seq->data[i]);
        }
    }
}

void SeqDestroy(Seq *seq)
{
    if (seq != NULL)
    {
        if (seq->length > 0)
        {
            DestroyRange(seq, 0, seq->length - 1);
        }
        SeqSoftDestroy(seq);
    }
}

void SeqSoftDestroy(Seq *seq)
{
    if (seq != NULL)
    {
        free(seq->data);
        free(seq);
    }
}

static void ExpandIfNeccessary(Seq *seq)
{
    assert(seq != NULL);
    assert(seq->length <= seq->capacity);

    if (seq->length == seq->capacity)
    {
        seq->capacity *= EXPAND_FACTOR;
        seq->data = xrealloc(seq->data, sizeof(void *) * seq->capacity);
    }
}

int StrCmpWrapper(const void *s1, const void *s2, void *user_data)
{
    UNUSED(user_data);
    return strcmp(s1, s2);
}

void SeqSet(Seq *seq, size_t index, void *item)
{
    assert(seq != NULL);
    assert(index < SeqLength(seq));
    if (seq->ItemDestroy)
    {
        seq->ItemDestroy(seq->data[index]);
    }
    seq->data[index] = item;
}

void SeqSoftSet(Seq *seq, size_t index, void *item)
{
    assert(seq != NULL);
    assert(index < SeqLength(seq));
    seq->data[index] = item;
}

void SeqAppend(Seq *seq, void *item)
{
    assert(seq != NULL);
    ExpandIfNeccessary(seq);

    seq->data[seq->length] = item;
    ++(seq->length);
}

void SeqAppendOnce(Seq *seq, void *item, SeqItemComparator Compare)
{
    assert(seq != NULL);
    if (SeqLookup(seq, item, Compare) == NULL)
    {
        SeqAppend(seq, item);
    }
    else
    {
        /* swallow the item anyway */
        if (seq->ItemDestroy != NULL)
        {
            seq->ItemDestroy(item);
        }
    }
}

void SeqAppendSeq(Seq *seq, const Seq *items)
{
    for (size_t i = 0; i < SeqLength(items); i++)
    {
        SeqAppend(seq, SeqAt(items, i));
    }
}

void SeqRemoveRange(Seq *seq, size_t start, size_t end)
{
    assert(seq != NULL);
    assert(end < seq->length);
    assert(start <= end);

    DestroyRange(seq, start, end);

    size_t rest_len = seq->length - end - 1;

    if (rest_len > 0)
    {
        memmove(seq->data + start, seq->data + end + 1, sizeof(void *) * rest_len);
    }

    seq->length -= end - start + 1;
}

void SeqRemove(Seq *seq, size_t index)
{
    SeqRemoveRange(seq, index, index);
}

void *SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare)
{
    assert(seq != NULL);
    for (size_t i = 0; i < seq->length; i++)
    {
        if (Compare(key, seq->data[i], NULL) == 0)
        {
            return seq->data[i];
        }
    }

    return NULL;
}

void *SeqBinaryLookup(Seq *seq, const void *key, SeqItemComparator Compare)
{
    assert(seq != NULL);
    ssize_t index = SeqBinaryIndexOf(seq, key, Compare);
    if (index == -1)
    {
        return NULL;
    }
    else
    {
        return seq->data[index];
    }
}

ssize_t SeqIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
{
    assert(seq != NULL);
    for (size_t i = 0; i < seq->length; i++)
    {
        if (Compare(key, seq->data[i], NULL) == 0)
        {
            return i;
        }
    }

    return -1;
}

ssize_t SeqBinaryIndexOf(Seq *seq, const void *key, SeqItemComparator Compare)
{
    assert(seq != NULL);
    if (seq->length == 0)
    {
        return -1;
    }

    size_t low = 0;
    size_t high = seq->length;

    while (low < high)
    {
        // Invariant: low <= middle < high
        size_t middle = low + ((high - low) >> 1); // ">> 1" is division by 2.
        int result = Compare(key, seq->data[middle], NULL);
        if (result == 0)
        {
            return middle;
        }
        if (result > 0)
        {
            low = middle + 1;
        }
        else
        {
            high = middle;
        }
    }

    // Not found.
    return -1;
}

static void Swap(void **l, void **r)
{
    void *t = *l;

    *l = *r;
    *r = t;
}

// adopted from http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C
static void QuickSortRecursive(void **data, int n, SeqItemComparator Compare, void *user_data, size_t maxterm)
{
    if (n < 2)
    {
        return;
    }

    void *pivot = data[n / 2];
    void **l = data;
    void **r = data + n - 1;

    while (l <= r)
    {
        while (Compare(*l, pivot, user_data) < 0)
        {
            ++l;
        }
        while (Compare(*r, pivot, user_data) > 0)
        {
            --r;
        }
        if (l <= r)
        {
            Swap(l, r);
            ++l;
            --r;
        }
    }

    QuickSortRecursive(data, r - data + 1, Compare, user_data, maxterm + 1);
    QuickSortRecursive(l, data + n - l, Compare, user_data, maxterm + 1);
}

void SeqSort(Seq *seq, SeqItemComparator Compare, void *user_data)
{
    assert(seq != NULL);
    QuickSortRecursive(seq->data, seq->length, Compare, user_data, 0);
}

Seq *SeqSoftSort(const Seq *seq, SeqItemComparator compare, void *user_data)
{
    size_t length = SeqLength(seq);
    if (length == 0)
    {
        return SeqNew(0, NULL);
    }

    Seq *sorted_seq = SeqGetRange(seq, 0, length - 1);
    SeqSort(sorted_seq, compare, user_data);
    return sorted_seq;
}

void SeqSoftRemoveRange(Seq *seq, size_t start, size_t end)
{
    assert(seq != NULL);
    assert(end < seq->length);
    assert(start <= end);

    size_t rest_len = seq->length - end - 1;

    if (rest_len > 0)
    {
        memmove(seq->data + start, seq->data + end + 1, sizeof(void *) * rest_len);
    }

    seq->length -= end - start + 1;
}

void SeqClear(Seq *seq)
{
    if (SeqLength(seq) > 0)
    {
        SeqRemoveRange(seq, 0, SeqLength(seq) - 1);
    }
}

void SeqSoftRemove(Seq *seq, size_t index)
{
    SeqSoftRemoveRange(seq, index, index);
}

void SeqReverse(Seq *seq)
{
    assert(seq != NULL);
    for (size_t i = 0; i < (seq->length / 2); i++)
    {
        Swap(&seq->data[i], &seq->data[seq->length - 1 - i]);
    }
}

Seq *SeqSplit(Seq *seq, size_t index)
{
    assert(seq != NULL);
    size_t length = SeqLength(seq);
    assert(index <= length); // index > length is invalid
    if (index >= length)
    {
        // index == length is valid, return empty sequence
        // anything higher is error, but we will handle it anyway
        return SeqNew(1, seq->ItemDestroy);
    }

    Seq *ret = SeqGetRange(seq, index, length - 1);
    assert(ret != NULL); // Our indices should be valid
    SeqSoftRemoveRange(seq, index, length - 1);
    return ret;
}

size_t SeqLength(const Seq *seq)
{
    assert(seq != NULL);
    return seq->length;
}

void SeqShuffle(Seq *seq, unsigned int seed)
{
    assert(seq != NULL);
    if (SeqLength(seq) == 0)
    {
        return;
    }

    /* Store current random number state for being reset at the end of function */
    int rand_state = rand();

    srand(seed);
    for (size_t i = SeqLength(seq) - 1; i > 0; i--)
    {
        size_t j = rand() % (i + 1);

        Swap(seq->data + i, seq->data + j);
    }

    /* Restore previous random number state */
    srand(rand_state);
}

Seq *SeqGetRange(const Seq *seq, size_t start, size_t end)
{
    assert(seq != NULL);

    if ((start > end) || (start >= seq->length) || (end >= seq->length))
    {
        return NULL;
    }

    Seq *sub = SeqNew(end - start + 1, seq->ItemDestroy);

    for (size_t i = start; i <= end; i++)
    {
        assert(i < SeqLength(seq));
        SeqAppend(sub, SeqAt(seq, i));
    }

    return sub;
}

void *const *SeqGetData(const Seq *seq)
{
    assert(seq != NULL);
    return seq->data;
}

void SeqRemoveNulls(Seq *seq)
{
    assert(seq != NULL);
    int length = SeqLength(seq);
    int from = 0;
    int to = 0;
    while (from < length)
    {
        if (seq->data[from] == NULL)
        {
            ++from; // Skip NULL elements
        }
        else
        {
            // Copy elements in place, DON'T use SeqSet, which will free()
            seq->data[to] = seq->data[from];
            ++from;
            ++to;
        }
    }
    seq->length = to;
}

Seq *SeqFromArgv(int argc, const char *const *const argv)
{
    assert(argc > 0);
    assert(argv != NULL);
    assert(argv[0] != NULL);

    Seq *args = SeqNew(argc, NULL);
    for (int i = 0; i < argc; ++i)
    {
        SeqAppend(args, (void *)argv[i]); // Discards const
    }
    return args;
}

Coverage Report

Created: 2023-12-12 06:10

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