src/lib/fifo.c

   1 /*
   2  * fifo.c       Non-thread-safe fifo (FIFO) implementation, based
   3  *              on hash tables.
   4  *
   5  * Version:     $Id$
   6  *
   7  *   This library is free software; you can redistribute it and/or
   8  *   modify it under the terms of the GNU Lesser General Public
   9  *   License as published by the Free Software Foundation; either
  10  *   version 2.1 of the License, or (at your option) any later version.
  11  *
  12  *   This library is distributed in the hope that it will be useful,
  13  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15  *   Lesser General Public License for more details.
  16  *
  17  *   You should have received a copy of the GNU Lesser General Public
  18  *   License along with this library; if not, write to the Free Software
  19  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  20  *
  21  *  Copyright 2005,2006  The FreeRADIUS server project
  22  *  Copyright 2005  Alan DeKok <aland@ox.org>
  23  */
  24
  25 #include <freeradius-devel/ident.h>
  26 RCSID("$Id$")
  27
  28 #include <freeradius-devel/autoconf.h>
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33 #include <freeradius-devel/missing.h>
  34 #include <freeradius-devel/libradius.h>
  35
  36 typedef struct lrad_fifo_entry_t {
  37         struct lrad_fifo_entry_t *next;
  38         void                    *data;
  39 } lrad_fifo_entry_t;
  40
  41 struct lrad_fifo_t {
  42         lrad_fifo_entry_t *head, **tail;
  43         lrad_fifo_entry_t *freelist;
  44
  45         int num_elements;
  46         int max_entries;
  47         lrad_fifo_free_t freeNode;
  48 };
  49
  50
  51 lrad_fifo_t *lrad_fifo_create(int max_entries, lrad_fifo_free_t freeNode)
  52 {
  53         lrad_fifo_t *fi;
  54
  55         if ((max_entries < 2) || (max_entries > (1024 * 1024))) return NULL;
  56
  57         fi = malloc(sizeof(*fi));
  58         if (!fi) return NULL;
  59
  60         memset(fi, 0, sizeof(*fi));
  61
  62         fi->max_entries = max_entries;
  63         fi->freeNode = freeNode;
  64
  65         return fi;
  66 }
  67
  68 static void lrad_fifo_free_entries(lrad_fifo_t *fi, lrad_fifo_entry_t *head)
  69 {
  70         lrad_fifo_entry_t *next;
  71
  72         while (head) {
  73                 next = head->next;
  74
  75                 if (fi->freeNode && head->data) fi->freeNode(head->data);
  76                 free(head);
  77
  78                 head = next;
  79         }
  80 }
  81
  82 void lrad_fifo_free(lrad_fifo_t *fi)
  83 {
  84         if (!fi) return;
  85
  86         lrad_fifo_free_entries(fi, fi->head);
  87         lrad_fifo_free_entries(fi, fi->freelist);
  88
  89         free(fi);
  90 }
  91
  92 static lrad_fifo_entry_t *lrad_fifo_alloc_entry(lrad_fifo_t *fi)
  93 {
  94         lrad_fifo_entry_t *entry;
  95
  96         if (fi->freelist) {
  97                 entry = fi->freelist;
  98                 fi->freelist = entry->next;
  99         } else {
 100                 entry = malloc(sizeof(*entry));
 101                 if (!entry) return NULL;
 102         }
 103
 104         memset(entry, 0, sizeof(*entry));
 105         return entry;
 106 }
 107
 108 int lrad_fifo_push(lrad_fifo_t *fi, void *data)
 109 {
 110         lrad_fifo_entry_t *entry;
 111
 112         if (!fi || !data) return 0;
 113
 114         if (fi->num_elements >= fi->max_entries) return 0;
 115
 116         entry = lrad_fifo_alloc_entry(fi);
 117         if (!entry) return 0;
 118         entry->data = data;
 119
 120         if (!fi->head) {
 121                 fi->head = entry;
 122         } else {
 123                 *fi->tail = entry;
 124         }
 125         fi->tail = &(entry->next);
 126
 127         fi->num_elements++;
 128
 129         return 1;
 130 }
 131
 132 static void lrad_fifo_free_entry(lrad_fifo_t *fi, lrad_fifo_entry_t *entry)
 133 {
 134         entry->data = NULL;
 135         entry->next = fi->freelist;
 136         fi->freelist = entry->next;
 137 }
 138
 139
 140 void *lrad_fifo_pop(lrad_fifo_t *fi)
 141 {
 142         void *data;
 143         lrad_fifo_entry_t *entry;
 144
 145         if (!fi || !fi->head) return 0;
 146
 147         entry = fi->head;
 148         fi->head = entry->next;
 149
 150         data = entry->data;
 151         lrad_fifo_free_entry(fi, entry);
 152
 153         fi->num_elements--;
 154
 155         if (!fi->head) {
 156                 fi->tail = NULL;
 157                 fi->num_elements = 0;
 158         }
 159
 160         return data;
 161 }
 162
 163 #ifdef TESTING
 164
 165 /*
 166  *  cc -DTESTING -I .. fifo.c -o fifo
 167  *
 168  *  ./fifo
 169  */
 170
 171 #define MAX 1024
 172 int main(int argc, char **argv)
 173 {
 174         int i, array[MAX];
 175         lrad_fifo_t *fi;
 176
 177         fi = lrad_fifo_create(MAX, NULL);
 178         if (!fi) exit(1);
 179
 180         for (i = 0; i < MAX; i++) {
 181                 array[i] = i;
 182
 183                 if (!lrad_fifo_push(fi, &array[i])) exit(2);
 184         }
 185
 186         for (i = 0; i < MAX; i++) {
 187                 int *p;
 188
 189                 p = lrad_fifo_pop(fi);
 190                 if (!p) {
 191                         fprintf(stderr, "No pop at %d\n", i);
 192                         exit(3);
 193                 }
 194
 195                 if (*p != i) exit(4);
 196         }
 197
 198         exit(0);
 199 }
 200 #endif