1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
/*
Copyright (C) CFEngine AS
This file is part of CFEngine 3 - written and maintained by CFEngine 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.
*/
#ifndef CFENGINE_SEQUENCE_H
#define CFENGINE_SEQUENCE_H
#include <platform.h>
/**
@brief Sequence data-structure.
This is an array-list loosely modeled on GSequence. It is a managed array of void pointers and can be used to store
arbitrary data. The array list will auto-expand by a factor of EXPAND_FACTOR (e.g. 2) when necessary, but not contract.
Because sequence is content agnostic, it does not support the usual copy semantics found in other CFEngine structures,
such as RList. Thus, appending an item to a Sequence may imply a transfer of ownership. Clients that require copy semantics
should therefore make sure that elements are copied before they are appended. Some Sequence operations may remove some or
all of the elements held. In order to do so safely, it's incumbent upon the client to supply the necessary item
destructor to the Sequence constructor. If the item destructor argument is NULL, Sequence will not attempt to free
the item memory held.
*/
typedef struct
{
void **data;
size_t length;
size_t capacity;
void (*ItemDestroy) (void *item);
} Seq;
#define SeqAt(seq, i) seq->data[i]
/**
@brief Length of the sequence.
@note On NULL sequence return size 0.
@param seq [in] sequence.
@return Sequence length.
*/
size_t SeqLength(const Seq *seq);
/**
@brief Create a new Sequence
@param [in] initial_capacity Size of initial buffer to allocate for item pointers.
@param [in] ItemDestroy Optional item destructor to clean up memory when needed.
@return A pointer to the created Sequence
*/
Seq *SeqNew(size_t initial_capacity, void (*ItemDestroy) ());
/**
@brief Destroy an existing Sequence
@param [in] seq The Sequence to destroy.
*/
void SeqDestroy(Seq *seq);
/**
@brief Destroy an existing Sequence without destroying its items.
@param [in] seq The Sequence to destroy.
*/
void SeqSoftDestroy(Seq *seq);
/**
@brief
Function to compare two items in a Sequence.
@retval -1 if the first argument is smaller than the second
@retval 0 if the arguments are equal
@retval 1 if the first argument is bigger than the second
*/
typedef int (*SeqItemComparator) (const void *, const void *, void *user_data);
void SeqSet(Seq *set, size_t index, void *item);
/**
@brief Append a new item to the Sequence
@param seq [in] The Sequence to append to.
@param item [in] The item to append. Note that this item may be passed to the item destructor specified in the constructor.
*/
void SeqAppend(Seq *seq, void *item);
/**
* @brief Append a sequence to this sequence. Only copies pointers.
* @param seq Sequence to append to
* @param items Sequence to copy pointers from.
*/
void SeqAppendSeq(Seq *seq, const Seq *items);
/**
@brief Linearly searches through the sequence and return the first item considered equal to the specified key.
@param seq [in] The Sequence to search.
@param key [in] The item to compare against.
@param compare [in] Comparator function to use. An item matches if the function returns 0.
@returns A pointer to the found item, or NULL if not found.
*/
void *SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare);
/**
* @brief Performs a binary search looking for the item matching the given key.
* It is the programmer's responsibility to make sure that the sequence is already sorted.
* @param seq [in] The Sequence to search.
* @param key [in] The item to compare against.
* @param compare [in] Comparator function to use (return value has strcmp semantics).
* @returns A pointer to the found item, or NULL if not found.
*/
void *SeqBinaryLookup(Seq *seq, const void *key, SeqItemComparator Compare);
/**
@brief Linearly searches through the sequence and returns the index of the first matching object, or -1 if it doesn't exist.
*/
ssize_t SeqIndexOf(Seq *seq, const void *key, SeqItemComparator Compare);
/**
* @brief Performs a binary search looking for the item matching the given key.
* It is the programmer's responsibility to make sure that the sequence is already sorted.
* @param seq [in] The Sequence to search.
* @param key [in] The item to compare against.
* @param compare [in] Comparator function to use (return value has strcmp semantics).
* @returns The index of the item, or -1 if it is not found.
*/
ssize_t SeqBinaryIndexOf(Seq *seq, const void *key, SeqItemComparator Compare);
/**
@brief Remove an inclusive range of items in the Sequence. A single item may be removed by specifiying start = end.
@param seq [in] The Sequence to remove from.
@param start [in] Index of the first element to remove
@param end [in] Index of the last element to remove.
*/
void SeqRemoveRange(Seq *seq, size_t start, size_t end);
/**
@brief Remove a single item in the sequence
*/
void SeqRemove(Seq *seq, size_t index);
/**
@brief Sort a Sequence according to the given item comparator function
@param compare [in] The comparator function used for sorting.
@param user_data [in] Pointer passed to the comparator function
*/
void SeqSort(Seq *seq, SeqItemComparator compare, void *user_data);
/**
@brief Returns a soft copy of the sequence sorted according to the given item comparator function.
@param compare [in] The comparator function used for sorting.
@param user_data [in] Pointer passed to the comparator function
*/
Seq *SeqSoftSort(const Seq *seq, SeqItemComparator compare, void *user_data);
/**
@brief Remove an inclusive range of item handles in the Sequence. A single item may be removed by specifiying start = end.
@param seq [in] The Sequence to remove from.
@param start [in] Index of the first element to remove
@param end [in] Index of the last element to remove.
*/
void SeqSoftRemoveRange(Seq *seq, size_t start, size_t end);
/**
@brief Remove a single item handle from the sequence
*/
void SeqSoftRemove(Seq *seq, size_t index);
/**
@brief Reverses the order of the sequence
*/
void SeqReverse(Seq *seq);
/**
* @brief Shuffle the sequence by randomly switching positions of the pointers
* @param seq
* @param seed Seed value for the PRNG
*/
void SeqShuffle(Seq *seq, unsigned int seed);
/**
* @brief Remove all elements in sequence
* @param seq
*/
void SeqClear(Seq *seq);
/**
@brief Get soft copy of sequence according to specified range
@param [in] seq Sequence select from
@param [in] start Start index of sub sequence.
@param [in] end End index which will be included into.
@return A pointer to sub sequence, NULL on error.
*/
Seq *SeqGetRange(const Seq *seq, size_t start, size_t end);
#endif
|
