1 /*
2 * This program is is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License, version 2 of the
4 * License as published by the Free Software Foundation.
5 *
6 * This program is distributed in the hope that it will be useful,
7 * but WITHOUT ANY WARRANTY; without even the implied warranty of
8 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9 * GNU General Public License for more details.
10 *
11 * You should have received a copy of the GNU General Public License
12 * along with this program; if not, write to the Free Software
13 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
14 */
15
16 /**
17 * $Id: ae88ebe75bd20622450c701a543a8940a89eb268 $
18 *
19 * @file cursor.c
20 * @brief Functions to iterate over collections of VALUE_PAIRs
21 *
22 * @note Do not modify collections of VALUE_PAIRs pointed to be a cursor
23 * with none fr_cursor_* functions, during the lifetime of that cursor.
24 *
25 * @author Arran Cudbard-Bell <a.cudbardb@freeradius.org>
26 * @copyright 2013-2015 Arran Cudbard-Bell <a.cudbardb@freeradius.org>
27 * @copyright 2013-2015 The FreeRADIUS Server Project.
28 */
29
30 #include <freeradius-devel/libradius.h>
31
32 /** Internal function to update cursor state
33 *
34 * @param cursor to operate on.
35 * @param vp to set current and found positions to.
36 * @return value passed in as vp.
37 */
fr_cursor_update(vp_cursor_t * cursor,VALUE_PAIR * vp)38 inline static VALUE_PAIR *fr_cursor_update(vp_cursor_t *cursor, VALUE_PAIR *vp)
39 {
40 if (!vp) {
41 cursor->next = NULL;
42 cursor->current = NULL;
43
44 return NULL;
45 }
46
47 cursor->next = vp->next;
48 cursor->current = vp;
49 cursor->found = vp;
50
51 return vp;
52 }
53
54 /** Setup a cursor to iterate over attribute pairs
55 *
56 * @param cursor Where to initialise the cursor (uses existing structure).
57 * @param const_vp to start from.
58 * @return the attribute pointed to by vp.
59 */
fr_cursor_init(vp_cursor_t * cursor,VALUE_PAIR * const * const_vp)60 VALUE_PAIR *fr_cursor_init(vp_cursor_t *cursor, VALUE_PAIR * const *const_vp)
61 {
62 VALUE_PAIR **vp;
63
64 if (!const_vp || !cursor) {
65 return NULL;
66 }
67
68 memset(cursor, 0, sizeof(*cursor));
69
70 memcpy(&vp, &const_vp, sizeof(vp)); /* stupid const hacks */
71
72 /*
73 * Useful check to see if uninitialised memory is pointed
74 * to by vp
75 */
76 #ifndef NDEBUG
77 if (*vp) VERIFY_VP(*vp);
78 #endif
79 memcpy(&cursor->first, &vp, sizeof(cursor->first));
80 cursor->current = *cursor->first;
81
82 if (cursor->current) {
83 VERIFY_VP(cursor->current);
84 cursor->next = cursor->current->next;
85 }
86
87 return cursor->current;
88 }
89
90 /** Copy a cursor
91 *
92 * @param in Cursor to copy.
93 * @param out Where to copy the cursor to.
94 */
fr_cursor_copy(vp_cursor_t * out,vp_cursor_t * in)95 void fr_cursor_copy(vp_cursor_t *out, vp_cursor_t *in)
96 {
97 memcpy(out, in, sizeof(*out));
98 }
99
100 /** Rewind cursor to the start of the list
101 *
102 * @param cursor to operate on.
103 * @return the VALUE_PAIR at the start of the list.
104 */
fr_cursor_first(vp_cursor_t * cursor)105 VALUE_PAIR *fr_cursor_first(vp_cursor_t *cursor)
106 {
107 if (!cursor->first) return NULL;
108
109 cursor->current = *cursor->first;
110
111 if (cursor->current) {
112 VERIFY_VP(cursor->current);
113 cursor->next = cursor->current->next;
114 if (cursor->next) VERIFY_VP(cursor->next);
115 cursor->found = NULL;
116 }
117
118 return cursor->current;
119 }
120
121 /** Wind cursor to the last pair in the list
122 *
123 * @param cursor to operate on.
124 * @return the VALUE_PAIR at the end of the list.
125 */
fr_cursor_last(vp_cursor_t * cursor)126 VALUE_PAIR *fr_cursor_last(vp_cursor_t *cursor)
127 {
128 if (!cursor->first || !*cursor->first) return NULL;
129
130 /* Need to start at the start */
131 if (!cursor->current) fr_cursor_first(cursor);
132
133 /* Wind to the end */
134 while (cursor->next) fr_cursor_next(cursor);
135
136 return cursor->current;
137 }
138
139 /** Iterate over a collection of VALUE_PAIRs of a given type in the pairlist
140 *
141 * Find the next attribute of a given type. If no fr_cursor_next_by_* function
142 * has been called on a cursor before, or the previous call returned
143 * NULL, the search will start with the current attribute. Subsequent calls to
144 * fr_cursor_next_by_* functions will start the search from the previously
145 * matched attribute.
146 *
147 * @param cursor to operate on.
148 * @param attr number to match.
149 * @param vendor number to match (0 for none vendor attribute).
150 * @param tag to match. Either a tag number or TAG_ANY to match any tagged or
151 * untagged attribute, TAG_NONE to match attributes without tags.
152 * @return the next matching VALUE_PAIR, or NULL if no VALUE_PAIRs match.
153 */
fr_cursor_next_by_num(vp_cursor_t * cursor,unsigned int attr,unsigned int vendor,int8_t tag)154 VALUE_PAIR *fr_cursor_next_by_num(vp_cursor_t *cursor, unsigned int attr, unsigned int vendor, int8_t tag)
155 {
156 VALUE_PAIR *i;
157
158 if (!cursor->first) return NULL;
159
160 for (i = !cursor->found ? cursor->current : cursor->found->next;
161 i != NULL;
162 i = i->next) {
163 VERIFY_VP(i);
164 if ((i->da->attr == attr) && (i->da->vendor == vendor) &&
165 (!i->da->flags.has_tag || TAG_EQ(tag, i->tag))) {
166 break;
167 }
168 }
169
170 return fr_cursor_update(cursor, i);
171 }
172
173 /** Iterate over attributes of a given DA in the pairlist
174 *
175 * Find the next attribute of a given type. If no fr_cursor_next_by_* function
176 * has been called on a cursor before, or the previous call returned
177 * NULL, the search will start with the current attribute. Subsequent calls to
178 * fr_cursor_next_by_* functions will start the search from the previously
179 * matched attribute.
180 *
181 * @note DICT_ATTR pointers are compared, not the attribute numbers and vendors.
182 *
183 * @param cursor to operate on.
184 * @param da to match.
185 * @param tag to match. Either a tag number or TAG_ANY to match any tagged or
186 * untagged attribute, TAG_NONE to match attributes without tags.
187 * @return the next matching VALUE_PAIR, or NULL if no VALUE_PAIRs match.
188 */
fr_cursor_next_by_da(vp_cursor_t * cursor,DICT_ATTR const * da,int8_t tag)189 VALUE_PAIR *fr_cursor_next_by_da(vp_cursor_t *cursor, DICT_ATTR const *da, int8_t tag)
190 {
191 VALUE_PAIR *i;
192
193 if (!cursor->first) return NULL;
194
195 for (i = !cursor->found ? cursor->current : cursor->found->next;
196 i != NULL;
197 i = i->next) {
198 VERIFY_VP(i);
199 if ((i->da == da) &&
200 (!i->da->flags.has_tag || TAG_EQ(tag, i->tag))) {
201 break;
202 }
203 }
204
205 return fr_cursor_update(cursor, i);
206 }
207
208 /** Advanced the cursor to the next VALUE_PAIR
209 *
210 * @param cursor to operate on.
211 * @return the next VALUE_PAIR, or NULL if no more VALUE_PAIRS in the collection.
212 */
fr_cursor_next(vp_cursor_t * cursor)213 VALUE_PAIR *fr_cursor_next(vp_cursor_t *cursor)
214 {
215 if (!cursor->first) return NULL;
216
217 cursor->current = cursor->next;
218 if (cursor->current) {
219 VERIFY_VP(cursor->current);
220
221 /*
222 * Set this now in case 'current' gets freed before
223 * fr_cursor_next is called again.
224 */
225 cursor->next = cursor->current->next;
226
227 /*
228 * Next call to fr_cursor_next_by_num will start from the current
229 * position in the list, not the last found instance.
230 */
231 cursor->found = NULL;
232 }
233
234 return cursor->current;
235 }
236
237 /** Return the next VALUE_PAIR without advancing the cursor
238 *
239 * @param cursor to operate on.
240 * @return the next VALUE_PAIR, or NULL if no more VALUE_PAIRS in the collection.
241 */
fr_cursor_next_peek(vp_cursor_t * cursor)242 VALUE_PAIR *fr_cursor_next_peek(vp_cursor_t *cursor)
243 {
244 return cursor->next;
245 }
246
247 /** Return the VALUE_PAIR the cursor current points to
248 *
249 * @param cursor to operate on.
250 * @return the VALUE_PAIR the cursor currently points to.
251 */
fr_cursor_current(vp_cursor_t * cursor)252 VALUE_PAIR *fr_cursor_current(vp_cursor_t *cursor)
253 {
254 if (cursor->current) VERIFY_VP(cursor->current);
255
256 return cursor->current;
257 }
258
259 /** Insert a single VALUE_PAIR at the end of the list
260 *
261 * @note Will not advance cursor position to new attribute, but will set cursor
262 * to this attribute, if it's the first one in the list.
263 *
264 * Insert a VALUE_PAIR at the end of the list.
265 *
266 * @param cursor to operate on.
267 * @param vp to insert.
268 */
fr_cursor_insert(vp_cursor_t * cursor,VALUE_PAIR * vp)269 void fr_cursor_insert(vp_cursor_t *cursor, VALUE_PAIR *vp)
270 {
271 VALUE_PAIR *i;
272
273 if (!fr_assert(cursor->first)) return; /* cursor must have been initialised */
274
275 if (!vp) return;
276
277 VERIFY_VP(vp);
278
279 /*
280 * Only allow one VP to by inserted at a time
281 */
282 vp->next = NULL;
283
284 /*
285 * Cursor was initialised with a pointer to a NULL value_pair
286 */
287 if (!*cursor->first) {
288 *cursor->first = vp;
289 cursor->current = vp;
290
291 return;
292 }
293
294 /*
295 * We don't yet know where the last VALUE_PAIR is
296 *
297 * Assume current is closer to the end of the list and
298 * use that if available.
299 */
300 if (!cursor->last) cursor->last = cursor->current ? cursor->current : *cursor->first;
301
302 VERIFY_VP(cursor->last);
303
304 /*
305 * Wind last to the end of the list.
306 */
307 if (cursor->last->next) {
308 for (i = cursor->last; i; i = i->next) {
309 VERIFY_VP(i);
310 cursor->last = i;
311 }
312 }
313
314 /*
315 * Either current was never set, or something iterated to the
316 * end of the attribute list. In both cases the newly inserted
317 * VALUE_PAIR should be set as the current VALUE_PAIR.
318 */
319 if (!cursor->current) cursor->current = vp;
320
321 /*
322 * Add the VALUE_PAIR to the end of the list
323 */
324 cursor->last->next = vp;
325 cursor->last = vp; /* Wind it forward a little more */
326
327 /*
328 * If the next pointer was NULL, and the VALUE_PAIR
329 * just added has a next pointer value, set the cursor's next
330 * pointer to the VALUE_PAIR's next pointer.
331 */
332 if (!cursor->next) cursor->next = cursor->current->next;
333 }
334
335 /** Merges multiple VALUE_PAIR into the cursor
336 *
337 * Add multiple VALUE_PAIR from add to cursor.
338 *
339 * @param cursor to insert VALUE_PAIRs with
340 * @param add one or more VALUE_PAIRs (may be NULL, which results in noop).
341 */
fr_cursor_merge(vp_cursor_t * cursor,VALUE_PAIR * add)342 void fr_cursor_merge(vp_cursor_t *cursor, VALUE_PAIR *add)
343 {
344 vp_cursor_t from;
345 VALUE_PAIR *vp;
346
347 if (!add) return;
348
349 if (!fr_assert(cursor->first)) return; /* cursor must have been initialised */
350
351 for (vp = fr_cursor_init(&from, &add);
352 vp;
353 vp = fr_cursor_next(&from)) {
354 fr_cursor_insert(cursor, vp);
355 }
356 }
357
358 /** Remove the current pair
359 *
360 * @todo this is really inefficient and should be fixed...
361 *
362 * The current VP will be set to the one before the VP being removed,
363 * this is so the commonly used check and remove loop (below) works
364 * as expected.
365 @code {.c}
366 for (vp = fr_cursor_init(&cursor, head);
367 vp;
368 vp = fr_cursor_next(&cursor) {
369 if (<condition>) {
370 vp = fr_cursor_remove(&cursor);
371 talloc_free(vp);
372 }
373 }
374 @endcode
375 *
376 * @param cursor to remove the current pair from.
377 * @return NULL on error, else the VALUE_PAIR that was just removed.
378 */
fr_cursor_remove(vp_cursor_t * cursor)379 VALUE_PAIR *fr_cursor_remove(vp_cursor_t *cursor)
380 {
381 VALUE_PAIR *vp, *before;
382
383 if (!fr_assert(cursor->first)) return NULL; /* cursor must have been initialised */
384
385 vp = cursor->current;
386 if (!vp) return NULL;
387
388 /*
389 * Where VP is head of the list
390 */
391 if (*(cursor->first) == vp) {
392 *(cursor->first) = vp->next;
393 cursor->current = vp->next;
394 cursor->next = vp->next ? vp->next->next : NULL;
395 before = NULL;
396 goto fixup;
397 }
398
399 /*
400 * Where VP is not head of the list
401 */
402 before = *(cursor->first);
403 if (!before) return NULL;
404
405 /*
406 * Find the VP immediately preceding the one being removed
407 */
408 while (before->next != vp) before = before->next;
409
410 cursor->next = before->next = vp->next; /* close the gap */
411 cursor->current = before; /* current jumps back one, but this is usually desirable */
412
413 fixup:
414 vp->next = NULL; /* limit scope of fr_pair_list_free() */
415
416 /*
417 * Fixup cursor->found if we removed the VP it was referring to,
418 * and point to the previous one.
419 */
420 if (vp == cursor->found) cursor->found = before;
421
422 /*
423 * Fixup cursor->last if we removed the VP it was referring to
424 */
425 if (vp == cursor->last) cursor->last = cursor->current;
426 return vp;
427 }
428
429 /** Replace the current pair
430 *
431 * @todo this is really inefficient and should be fixed...
432 *
433 * @param cursor to replace the current pair in.
434 * @param new VALUE_PAIR to insert.
435 * @return NULL on error, else the VALUE_PAIR we just replaced.
436 */
fr_cursor_replace(vp_cursor_t * cursor,VALUE_PAIR * new)437 VALUE_PAIR *fr_cursor_replace(vp_cursor_t *cursor, VALUE_PAIR *new)
438 {
439 VALUE_PAIR *vp, **last;
440
441 if (!fr_assert(cursor->first)) return NULL; /* cursor must have been initialised */
442
443 vp = cursor->current;
444 if (!vp) {
445 *cursor->first = new;
446 return NULL;
447 }
448
449 last = cursor->first;
450 while (*last != vp) {
451 last = &(*last)->next;
452 }
453
454 fr_cursor_next(cursor); /* Advance the cursor past the one were about to replace */
455
456 *last = new;
457 new->next = vp->next;
458 vp->next = NULL;
459
460 return vp;
461 }
462