src/lib/cursor.c

   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$
  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  */
  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  */
  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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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                 goto fixup;
 396         }
 397
 398         /*
 399          *      Where VP is not head of the list
 400          */
 401         before = *(cursor->first);
 402         if (!before) return NULL;
 403
 404         /*
 405          *      Find the VP immediately preceding the one being removed
 406          */
 407         while (before->next != vp) before = before->next;
 408
 409         cursor->next = before->next = vp->next; /* close the gap */
 410         cursor->current = before;               /* current jumps back one, but this is usually desirable */
 411
 412 fixup:
 413         vp->next = NULL;                        /* limit scope of fr_pair_list_free() */
 414
 415         /*
 416          *      Fixup cursor->found if we removed the VP it was referring to
 417          */
 418         if (vp == cursor->found) cursor->found = cursor->current;
 419
 420         /*
 421          *      Fixup cursor->last if we removed the VP it was referring to
 422          */
 423         if (vp == cursor->last) cursor->last = cursor->current;
 424         return vp;
 425 }
 426
 427 /** Replace the current pair
 428  *
 429  * @todo this is really inefficient and should be fixed...
 430  *
 431  * @param cursor to replace the current pair in.
 432  * @param new VALUE_PAIR to insert.
 433  * @return NULL on error, else the VALUE_PAIR we just replaced.
 434  */
 435 VALUE_PAIR *fr_cursor_replace(vp_cursor_t *cursor, VALUE_PAIR *new)
 436 {
 437         VALUE_PAIR *vp, **last;
 438
 439         if (!fr_assert(cursor->first)) return NULL;     /* cursor must have been initialised */
 440
 441         vp = cursor->current;
 442         if (!vp) {
 443                 *cursor->first = new;
 444                 return NULL;
 445         }
 446
 447         last = cursor->first;
 448         while (*last != vp) {
 449             last = &(*last)->next;
 450         }
 451
 452         fr_cursor_next(cursor);   /* Advance the cursor past the one were about to replace */
 453
 454         *last = new;
 455         new->next = vp->next;
 456         vp->next = NULL;
 457
 458         return vp;
 459 }