/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.

  This program is free software; you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the
  Free Software Foundation; version 3.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA

  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-06-07 07:02

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