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.h
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 #ifndef CFENGINE_SEQUENCE_H
26 #define CFENGINE_SEQUENCE_H
27 
28 #include <stddef.h> // size_t
29 #include <sys/types.h> // ssize_t
30 #include <assert.h> // assert()
31 #include <stdio.h> // FILE
32 
33 /**
34  @brief Sequence data-structure.
35 
36  This is an array-list loosely modeled on GSequence. It is a managed array of
37  void pointers and can be used to store arbitrary data. The array list will
38  auto-expand by a factor of EXPAND_FACTOR (e.g. 2) when necessary, but not
39  contract. Because sequence is content agnostic, it does not support the
40  usual copy semantics found in other CFEngine structures, such as
41  RList. Thus, appending an item to a Sequence may imply a transfer of
42  ownership. Clients that require copy semantics should therefore make sure
43  that elements are copied before they are appended. Some Sequence operations
44  may remove some or all of the elements held. In order to do so safely, it's
45  incumbent upon the client to supply the necessary item destructor to the
46  Sequence constructor. If the item destructor argument is NULL, Sequence will
47  not attempt to free the item memory held.
48 */
49 typedef struct
50 {
51  void **data;
52  size_t length;
53  size_t capacity;
54  void (*ItemDestroy) (void *item);
55 } Seq;
56 
57 static inline void *SeqAt(const Seq *seq, int i)
58 {
59  assert(seq != NULL);
60  assert(i < seq->length);
61  return seq->data[i];
62 }
63 
64 /**
65  @brief Length of the sequence.
66  @note On NULL sequence return size 0.
67  @param seq [in] sequence.
68  @return Sequence length.
69  */
70 size_t SeqLength(const Seq *seq);
71 
72 /**
73  @brief Create a new Sequence
74  @param [in] initial_capacity Size of initial buffer to allocate for item pointers.
75  @param [in] ItemDestroy Optional item destructor to clean up memory when needed.
76  @return A pointer to the created Sequence
77  */
78 Seq *SeqNew(size_t initial_capacity, void (*ItemDestroy) ());
79 
80 /**
81  @brief Destroy an existing Sequence
82  @param [in] seq The Sequence to destroy.
83  */
84 void SeqDestroy(Seq *seq);
85 
86 /**
87  @brief Destroy an existing Sequence without destroying its items.
88  @param [in] seq The Sequence to destroy.
89  */
90 void SeqSoftDestroy(Seq *seq);
91 
92 /**
93  @brief
94  Function to compare two items in a Sequence.
95 
96  @retval -1 if the first argument is smaller than the second
97  @retval 0 if the arguments are equal
98  @retval 1 if the first argument is bigger than the second
99  */
100 typedef int (*SeqItemComparator) (const void *, const void *, void *user_data);
101 
102 void SeqSet(Seq *set, size_t index, void *item);
103 
104 /**
105  @brief Append a new item to the Sequence
106  @param seq [in] The Sequence to append to.
107  @param item [in] The item to append. Note that this item may be passed to the item destructor specified in the constructor.
108  */
109 void SeqAppend(Seq *seq, void *item);
110 
111 /**
112  @brief Append a new item to the Sequence if it's not already present in the Sequence.
113  @note This calls SeqLookup() and thus linearly searches through the sequence.
114  @param seq [in] The Sequence to append to.
115  @param item [in] The item to append. Note that this item will be passed to the item destructor specified in the constructor.
116  Either immediately if the same item (according to Compare()) is found in the Sequence or once the Sequence
117  is destroyed with SeqDestroy().
118  */
119 void SeqAppendOnce(Seq *seq, void *item, SeqItemComparator Compare);
120 
121 /**
122  * @brief Append a sequence to this sequence. Only copies pointers.
123  * @param seq Sequence to append to
124  * @param items Sequence to copy pointers from.
125  */
126 void SeqAppendSeq(Seq *seq, const Seq *items);
127 
128 /**
129  @brief Linearly searches through the sequence and return the first item considered equal to the specified key.
130  @param seq [in] The Sequence to search.
131  @param key [in] The item to compare against.
132  @param compare [in] Comparator function to use. An item matches if the function returns 0.
133  @returns A pointer to the found item, or NULL if not found.
134  */
135 void *SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare);
136 
137 /**
138  * @brief Performs a binary search looking for the item matching the given key.
139  * It is the programmer's responsibility to make sure that the sequence is already sorted.
140  * @param seq [in] The Sequence to search.
141  * @param key [in] The item to compare against.
142  * @param compare [in] Comparator function to use (return value has strcmp semantics).
143  * @returns A pointer to the found item, or NULL if not found.
144  */
145 void *SeqBinaryLookup(Seq *seq, const void *key, SeqItemComparator Compare);
146 
147 /**
148  @brief Linearly searches through the sequence and returns the index of the first matching object, or -1 if it doesn't exist.
149  */
150 ssize_t SeqIndexOf(Seq *seq, const void *key, SeqItemComparator Compare);
151 
152 /**
153  * @brief Performs a binary search looking for the item matching the given key.
154  * It is the programmer's responsibility to make sure that the sequence is already sorted.
155  * @param seq [in] The Sequence to search.
156  * @param key [in] The item to compare against.
157  * @param compare [in] Comparator function to use (return value has strcmp semantics).
158  * @returns The index of the item, or -1 if it is not found.
159  */
160 ssize_t SeqBinaryIndexOf(Seq *seq, const void *key, SeqItemComparator Compare);
161 
162 /**
163  @brief Remove an inclusive range of items in the Sequence. A single item may be removed by specifying start = end.
164  @param seq [in] The Sequence to remove from.
165  @param start [in] Index of the first element to remove
166  @param end [in] Index of the last element to remove.
167  */
168 void SeqRemoveRange(Seq *seq, size_t start, size_t end);
169 
170 /**
171  @brief Remove a single item in the sequence
172  */
173 void SeqRemove(Seq *seq, size_t index);
174 
175 /**
176  @brief Sort a Sequence according to the given item comparator function
177  @param compare [in] The comparator function used for sorting.
178  @param user_data [in] Pointer passed to the comparator function
179  */
180 void SeqSort(Seq *seq, SeqItemComparator compare, void *user_data);
181 
182 /**
183  @brief Returns a soft copy of the sequence sorted according to the given item comparator function.
184  @param compare [in] The comparator function used for sorting.
185  @param user_data [in] Pointer passed to the comparator function
186  */
187 Seq *SeqSoftSort(const Seq *seq, SeqItemComparator compare, void *user_data);
188 
189 /**
190  @brief Remove an inclusive range of item handles in the Sequence. A single item may be removed by specifying start = end.
191  @param seq [in] The Sequence to remove from.
192  @param start [in] Index of the first element to remove
193  @param end [in] Index of the last element to remove.
194  */
195 void SeqSoftRemoveRange(Seq *seq, size_t start, size_t end);
196 
197 /**
198  @brief Remove a single item handle from the sequence
199  */
200 void SeqSoftRemove(Seq *seq, size_t index);
201 
202 /**
203  @brief Reverses the order of the sequence
204  */
205 void SeqReverse(Seq *seq);
206 
207 /**
208  @brief Split a sequence in two at a given index.
209 
210  Elements before the split are kept in original sequence,
211  elements after the split are moved to a new sequence,
212  which is returned. The original, the new, and the modified sequence
213  may all be empty.
214 
215  Items in sequence are not reallocated, they are moved and the new
216  sequnce has the same destroy function as the original.
217 
218  @param original [in] The Sequence to split in two (will be modified)
219  @param index [in] Index of split, or how many elements to keep in original
220  @return New sequence containing the elements removed from original
221  */
222 Seq *SeqSplit(Seq *original, size_t index);
223 
224 /**
225  * @brief Shuffle the sequence by randomly switching positions of the pointers
226  * @param seq
227  * @param seed Seed value for the PRNG
228  */
229 void SeqShuffle(Seq *seq, unsigned int seed);
230 
231 /**
232  * @brief Remove all elements in sequence
233  * @param seq
234  */
235 void SeqClear(Seq *seq);
236 
237 /**
238  @brief Get soft copy of sequence according to specified range
239  @param [in] seq Sequence select from
240  @param [in] start Start index of sub sequence.
241  @param [in] end End index which will be included into.
242  @return A pointer to sub sequence, NULL on error.
243  */
244 Seq *SeqGetRange(const Seq *seq, size_t start, size_t end);
245 
246 /**
247  * @brief Get the data segment of the sequence
248  * @param [in] seq Sequence to get the data segment of
249  * @return An array of pointers to data stored in the sequence
250  * @warning The returned array is not guaranteed to be %NULL-terminated unless %NULL was appended to
251  * the sequence.
252  */
253 void *const *SeqGetData(const Seq *seq);
254 
255 void SeqRemoveNulls(Seq *seq);
256 
257 Seq *SeqFromArgv(int argc, const char *const *argv);
258 
259 #endif
#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
static void * SeqAt(const Seq *seq, int i)
Definition: sequence.h:57
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
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
Seq * SeqNew(size_t initial_capacity, void(*ItemDestroy)())
Create a new Sequence.
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
size_t SeqLength(const Seq *seq)
Length of the sequence.
Definition: sequence.c:354
void SeqSort(Seq *seq, SeqItemComparator compare, void *user_data)
Sort a Sequence according to the given item comparator function.
Definition: sequence.c:279
void SeqRemoveNulls(Seq *seq)
Definition: sequence.c:409
Seq * SeqFromArgv(int argc, const char *const *argv)
Definition: sequence.c:432
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 * SeqSplit(Seq *original, size_t index)
Split a sequence in two at a given index.
Definition: sequence.c:336
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 *const * SeqGetData(const Seq *seq)
Get the data segment of the sequence.
Definition: sequence.c:403
void SeqShuffle(Seq *seq, unsigned int seed)
Shuffle the sequence by randomly switching positions of the pointers.
Definition: sequence.c:360
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 SeqDestroy(Seq *seq)
Destroy an existing Sequence.
Definition: sequence.c:60
void SeqSet(Seq *set, size_t index, void *item)
Definition: sequence.c:93
int(* SeqItemComparator)(const void *, const void *, void *user_data)
Function to compare two items in a Sequence.
Definition: sequence.h:100
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
Sequence data-structure.
Definition: sequence.h:50
size_t length
Definition: sequence.h:52
size_t capacity
Definition: sequence.h:53
void ** data
Definition: sequence.h:51