All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cursor.c
Go to the documentation of this file.
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: cccbec4a5eaa03fe6118d2bea22da21931e7d07a $
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 #VALUE_PAIR.
37  */
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  */
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  */
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 #VALUE_PAIR at the start of the list.
104  */
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 #VALUE_PAIR at the end of the list.
125  */
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 /** Moves cursor past the last attribute to the end
140  *
141  * Primarily useful for setting up the cursor for freeing attributes added
142  * during the execution of a function, which later errors out, requiring only
143  * the attribute(s) that it added to be freed, and the attributes already
144  * present in the list to remain untouched.
145  *
146  @code {.c}
147  int my_cursor_insert_func(vp_cursor_t *cursor)
148  {
149  fr_cursor_end(cursor);
150 
151  fr_cursor_insert(cursor, fr_pair_alloc_by_num(NULL, 0, PW_MESSAGE_AUTHENTICATOR));
152 
153  if (bad_thing) {
154  fr_cursor_free(cursor);
155  return -1;
156  }
157 
158  return 0;
159  }
160  @endcode
161  *
162  * @param cursor to operate on.
163  */
165 {
166  if (!cursor->first || !*cursor->first) return;
167 
168  /* Already at the end */
169  if (!cursor->current && cursor->last && !cursor->last->next) return;
170 
171  /* Need to start at the start */
172  if (!cursor->current) fr_cursor_first(cursor);
173 
174  /* Wind to the end */
175  while (cursor->next) fr_cursor_next(cursor);
176 
177  /* One more time to move us off the end*/
178  fr_cursor_next(cursor);
179 
180  return;
181 }
182 
183 /** Iterate over a collection of VALUE_PAIRs of a given type in the pairlist
184  *
185  * Find the next attribute of a given type. If no fr_cursor_next_by_* function
186  * has been called on a cursor before, or the previous call returned
187  * NULL, the search will start with the current attribute. Subsequent calls to
188  * fr_cursor_next_by_* functions will start the search from the previously
189  * matched attribute.
190  *
191  * @param cursor to operate on.
192  * @param attr number to match.
193  * @param vendor number to match (0 for none vendor attribute).
194  * @param tag to match. Either a tag number or TAG_ANY to match any tagged or
195  * untagged attribute, TAG_NONE to match attributes without tags.
196  * @return
197  * - The next matching #VALUE_PAIR.
198  * - NULL if no #VALUE_PAIR (s) match.
199  */
200 VALUE_PAIR *fr_cursor_next_by_num(vp_cursor_t *cursor, unsigned int vendor, unsigned int attr, int8_t tag)
201 {
202  VALUE_PAIR *i;
203 
204  if (!cursor->first) return NULL;
205 
206  for (i = !cursor->found ? cursor->current : cursor->found->next;
207  i != NULL;
208  i = i->next) {
209  VERIFY_VP(i);
210  if ((i->da->attr == attr) && (i->da->vendor == vendor) &&
211  (!i->da->flags.has_tag || TAG_EQ(tag, i->tag))) {
212  break;
213  }
214  }
215 
216  return fr_cursor_update(cursor, i);
217 }
218 
219 /** Iterate over attributes of a given DA in the pairlist
220  *
221  * Find the next attribute of a given type. If no fr_cursor_next_by_* function
222  * has been called on a cursor before, or the previous call returned
223  * NULL, the search will start with the current attribute. Subsequent calls to
224  * fr_cursor_next_by_* functions will start the search from the previously
225  * matched attribute.
226  *
227  * @note fr_dict_attr_t pointers are compared, not the attribute numbers and vendors.
228  *
229  * @param cursor to operate on.
230  * @param da to match.
231  * @param tag to match. Either a tag number or TAG_ANY to match any tagged or
232  * untagged attribute, TAG_NONE to match attributes without tags.
233  * @return
234  * - Next matching #VALUE_PAIR.
235  * - NULL if no #VALUE_PAIR (s) match.
236  */
238 {
239  VALUE_PAIR *i;
240 
241  if (!cursor->first) return NULL;
242 
243  for (i = !cursor->found ? cursor->current : cursor->found->next;
244  i != NULL;
245  i = i->next) {
246  VERIFY_VP(i);
247  if ((i->da == da) &&
248  (!i->da->flags.has_tag || TAG_EQ(tag, i->tag))) {
249  break;
250  }
251  }
252 
253  return fr_cursor_update(cursor, i);
254 }
255 
256 /** Advanced the cursor to the next VALUE_PAIR
257  *
258  * @param cursor to operate on.
259  * @return
260  * - Next #VALUE_PAIR.
261  * - NULL if no more #VALUE_PAIR in the collection.
262  */
264 {
265  if (!cursor->first) return NULL;
266 
267  cursor->current = cursor->next;
268  if (cursor->current) {
269  VERIFY_VP(cursor->current);
270 
271  /*
272  * Set this now in case 'current' gets freed before
273  * fr_cursor_next is called again.
274  */
275  cursor->next = cursor->current->next;
276 
277  /*
278  * Next call to fr_cursor_next_by_num will start from the current
279  * position in the list, not the last found instance.
280  */
281  cursor->found = NULL;
282  }
283 
284  return cursor->current;
285 }
286 
287 /** Return the next VALUE_PAIR without advancing the cursor
288  *
289  * @param cursor to operate on.
290  * @return
291  * - Next #VALUE_PAIR.
292  * - NULL if no more #VALUE_PAIR are in the collection.
293  */
295 {
296  return cursor->next;
297 }
298 
299 /** Return the VALUE_PAIR the cursor current points to
300  *
301  * @param cursor to operate on.
302  * @return the #VALUE_PAIR the cursor currently points to.
303  */
305 {
306  if (cursor->current) VERIFY_VP(cursor->current);
307 
308  return cursor->current;
309 }
310 
311 /** Insert a single VALUE_PAIR at the end of the list
312  *
313  * @note Will not advance cursor position to new attribute, but will set cursor
314  * to this attribute, if it's the first one in the list.
315  *
316  * Insert a VALUE_PAIR at the end of the list.
317  *
318  * @param cursor to operate on.
319  * @param vp to insert.
320  */
322 {
323  VALUE_PAIR *i;
324 
325  if (!fr_assert(cursor->first)) return; /* cursor must have been initialised */
326 
327  if (!vp) return;
328 
329  VERIFY_VP(vp);
330 
331  /*
332  * Only allow one VP to by inserted at a time
333  */
334  vp->next = NULL;
335 
336  /*
337  * Cursor was initialised with a pointer to a NULL value_pair
338  */
339  if (!*cursor->first) {
340  *cursor->first = vp;
341  cursor->current = vp;
342 
343  return;
344  }
345 
346  /*
347  * We don't yet know where the last VALUE_PAIR is
348  *
349  * Assume current is closer to the end of the list and
350  * use that if available.
351  */
352  if (!cursor->last) cursor->last = cursor->current ? cursor->current : *cursor->first;
353 
354  VERIFY_VP(cursor->last);
355 
356  /*
357  * Wind last to the end of the list.
358  */
359  if (cursor->last->next) {
360  for (i = cursor->last; i; i = i->next) {
361  VERIFY_VP(i);
362  cursor->last = i;
363  }
364  }
365 
366  /*
367  * Either current was never set, or something iterated to the
368  * end of the attribute list. In both cases the newly inserted
369  * VALUE_PAIR should be set as the current VALUE_PAIR.
370  */
371  if (!cursor->current) cursor->current = vp;
372 
373  /*
374  * Add the VALUE_PAIR to the end of the list
375  */
376  cursor->last->next = vp;
377  cursor->last = vp; /* Wind it forward a little more */
378 
379  /*
380  * If the next pointer was NULL, and the VALUE_PAIR
381  * just added has a next pointer value, set the cursor's next
382  * pointer to the VALUE_PAIR's next pointer.
383  */
384  if (!cursor->next) cursor->next = cursor->current->next;
385 }
386 
387 /** Merges multiple VALUE_PAIR into the cursor
388  *
389  * Add multiple VALUE_PAIR from add to cursor.
390  *
391  * @param cursor to insert VALUE_PAIRs with
392  * @param add one or more VALUE_PAIRs (may be NULL, which results in noop).
393  */
395 {
396  vp_cursor_t from;
397  VALUE_PAIR *vp;
398 
399  if (!add) return;
400 
401  if (!fr_assert(cursor->first)) return; /* cursor must have been initialised */
402 
403  for (vp = fr_cursor_init(&from, &add);
404  vp;
405  vp = fr_cursor_next(&from)) {
406  fr_cursor_insert(cursor, vp);
407  }
408 }
409 
410 /** Remove the current pair
411  *
412  * @todo this is really inefficient and should be fixed...
413  *
414  * The current VP will be set to the one before the VP being removed,
415  * this is so the commonly used check and remove loop (below) works
416  * as expected.
417  @code {.c}
418  for (vp = fr_cursor_init(&cursor, head);
419  vp;
420  vp = fr_cursor_next(&cursor) {
421  if (<condition>) {
422  vp = fr_cursor_remove(&cursor);
423  talloc_free(vp);
424  }
425  }
426  @endcode
427  *
428  * @param cursor to remove the current pair from.
429  * @return
430  * - #VALUE_PAIR we just replaced.
431  * - NULL on error.
432  */
434 {
435  VALUE_PAIR *vp, *before;
436 
437  if (!fr_assert(cursor->first)) return NULL; /* cursor must have been initialised */
438 
439  vp = cursor->current;
440  if (!vp) return NULL;
441 
442  /*
443  * Where VP is head of the list
444  */
445  if (*(cursor->first) == vp) {
446  *(cursor->first) = vp->next;
447  cursor->current = vp->next;
448  cursor->next = vp->next ? vp->next->next : NULL;
449  goto fixup;
450  }
451 
452  /*
453  * Where VP is not head of the list
454  */
455  before = *(cursor->first);
456  if (!before) return NULL;
457 
458  /*
459  * Find the VP immediately preceding the one being removed
460  */
461  while (before->next != vp) before = before->next;
462 
463  cursor->next = before->next = vp->next; /* close the gap */
464  cursor->current = before; /* current jumps back one, but this is usually desirable */
465 
466 fixup:
467  vp->next = NULL; /* limit scope of fr_pair_list_free() */
468 
469  /*
470  * Fixup cursor->found if we removed the VP it was referring to
471  */
472  if (vp == cursor->found) cursor->found = cursor->current;
473 
474  /*
475  * Fixup cursor->last if we removed the VP it was referring to
476  */
477  if (vp == cursor->last) cursor->last = cursor->current;
478  return vp;
479 }
480 
481 /** Replace the current pair
482  *
483  * @todo this is really inefficient and should be fixed...
484  *
485  * @param cursor to replace the current pair in.
486  * @param new #VALUE_PAIR to insert.
487  * @return
488  * - #VALUE_PAIR we just replaced.
489  * - NULL on error.
490  */
492 {
493  VALUE_PAIR *vp, **last;
494 
495  if (!fr_assert(cursor->first)) return NULL; /* cursor must have been initialised */
496 
497  vp = cursor->current;
498  if (!vp) {
499  *cursor->first = new;
500  return NULL;
501  }
502 
503  last = cursor->first;
504  while (*last != vp) {
505  last = &(*last)->next;
506  }
507 
508  fr_cursor_next(cursor); /* Advance the cursor past the one were about to replace */
509 
510  *last = new;
511  new->next = vp->next;
512  vp->next = NULL;
513 
514  return vp;
515 }
516 
517 /** Free the current pair and all pairs after it
518  *
519  * @note Use fr_cursor_remove and talloc_free to free single pairs.
520  *
521  * Will move the cursor back one, then free the current pair and all
522  * VALUE_PAIRs after it.
523  *
524  * Usually used in conjunction with #fr_cursor_end and #fr_cursor_insert.
525  *
526  * @param cursor to free pairs in.
527  */
529 {
530  VALUE_PAIR *vp, *before;
531  bool found = false, last = false;
532 
533  if (!*(cursor->first)) return; /* noop */
534 
535  /*
536  * Fast path if the cursor has been rewound to the start
537  */
538  if (cursor->current == *(cursor->first)) {
539  cursor->current = NULL;
540  cursor->next = NULL;
541  cursor->found = NULL;
542  cursor->last = NULL;
543  fr_pair_list_free(cursor->first);
544  }
545 
546  vp = cursor->current;
547  if (!vp) return;
548 
549  /*
550  * Where VP is not head of the list
551  */
552  before = *(cursor->first);
553  if (!before) return;
554 
555  /*
556  * Find the VP immediately preceding the one being removed
557  */
558  while (before->next != vp) {
559  if (before == cursor->found) found = true;
560  if (before == cursor->last) last = true;
561  before = before->next;
562  }
563 
564  fr_pair_list_free(&before->next);
565 
566  cursor->current = before; /* current jumps back one, but this is usually desirable */
567  cursor->next = NULL; /* we just truncated the list, there is no next... */
568 
569  /*
570  * Fixup found and last pointers
571  */
572  if (!found) cursor->found = cursor->current;
573  if (!last) cursor->last = cursor->current;
574 }
void fr_pair_list_free(VALUE_PAIR **)
Free memory used by a valuepair list.
Definition: pair.c:544
VALUE_PAIR * fr_cursor_next_by_da(vp_cursor_t *cursor, fr_dict_attr_t const *da, int8_t tag)
Iterate over attributes of a given DA in the pairlist.
Definition: cursor.c:237
Dictionary attribute.
Definition: dict.h:77
VALUE_PAIR * fr_cursor_first(vp_cursor_t *cursor)
Rewind cursor to the start of the list.
Definition: cursor.c:105
#define VERIFY_VP(_x)
Definition: pair.h:44
int8_t tag
Tag value used to group valuepairs.
Definition: pair.h:121
void fr_cursor_copy(vp_cursor_t *out, vp_cursor_t *in)
Copy a cursor.
Definition: cursor.c:95
VALUE_PAIR * fr_cursor_next_peek(vp_cursor_t *cursor)
Return the next VALUE_PAIR without advancing the cursor.
Definition: cursor.c:294
VALUE_PAIR * fr_cursor_next(vp_cursor_t *cursor)
Advanced the cursor to the next VALUE_PAIR.
Definition: cursor.c:263
void fr_cursor_insert(vp_cursor_t *cursor, VALUE_PAIR *vp)
Insert a single VALUE_PAIR at the end of the list.
Definition: cursor.c:321
Abstraction to allow iterating over different configurations of VALUE_PAIRs.
Definition: pair.h:144
fr_dict_attr_flags_t flags
Flags.
Definition: dict.h:88
struct value_pair * next
Definition: pair.h:116
VALUE_PAIR ** first
Definition: pair.h:145
void fr_cursor_end(vp_cursor_t *cursor)
Moves cursor past the last attribute to the end.
Definition: cursor.c:164
VALUE_PAIR * fr_cursor_last(vp_cursor_t *cursor)
Wind cursor to the last pair in the list.
Definition: cursor.c:126
VALUE_PAIR * fr_cursor_replace(vp_cursor_t *cursor, VALUE_PAIR *new)
Replace the current pair.
Definition: cursor.c:491
VALUE_PAIR * fr_cursor_init(vp_cursor_t *cursor, VALUE_PAIR *const *const_vp)
Setup a cursor to iterate over attribute pairs.
Definition: cursor.c:60
unsigned int attr
Attribute number.
Definition: dict.h:79
#define TAG_EQ(_x, _y)
Check if tags are equal.
Definition: pair.h:198
void fr_cursor_merge(vp_cursor_t *cursor, VALUE_PAIR *add)
Merges multiple VALUE_PAIR into the cursor.
Definition: cursor.c:394
void fr_cursor_free(vp_cursor_t *cursor)
Free the current pair and all pairs after it.
Definition: cursor.c:528
#define fr_assert(_x)
Definition: libradius.h:505
unsigned int vendor
Vendor that defines this attribute.
Definition: dict.h:78
Stores an attribute, a value and various bits of other data.
Definition: pair.h:112
VALUE_PAIR * found
pairfind marker.
Definition: pair.h:146
VALUE_PAIR * current
The current attribute.
Definition: pair.h:148
VALUE_PAIR * next
Next attribute to process.
Definition: pair.h:149
VALUE_PAIR * fr_cursor_next_by_num(vp_cursor_t *cursor, unsigned int vendor, unsigned int attr, int8_t tag)
Iterate over a collection of VALUE_PAIRs of a given type in the pairlist.
Definition: cursor.c:200
static VALUE_PAIR * fr_cursor_update(vp_cursor_t *cursor, VALUE_PAIR *vp)
Internal function to update cursor state.
Definition: cursor.c:38
VALUE_PAIR * last
Temporary only used for fr_cursor_insert.
Definition: pair.h:147
unsigned int has_tag
Tagged attribute.
Definition: dict.h:46
VALUE_PAIR * fr_cursor_current(vp_cursor_t *cursor)
Return the VALUE_PAIR the cursor current points to.
Definition: cursor.c:304
fr_dict_attr_t const * da
Dictionary attribute defines the attribute.
Definition: pair.h:113
VALUE_PAIR * fr_cursor_remove(vp_cursor_t *cursor)
Remove the current pair.
Definition: cursor.c:433