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  The FreeRADIUS server project
  22  *  Copyright 2005  Alan DeKok <aland@ox.org>
  23  */
  24
  25 static const char rcsid[] = "$Id$";
  26
  27 #include <freeradius-devel/autoconf.h>
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 #include <freeradius-devel/missing.h>
  33 #include <freeradius-devel/libradius.h>
  34
  35 typedef struct lrad_fifo_entry_t {
  36         struct lrad_fifo_entry_t *next;
  37         void                    *data;
  38 } lrad_fifo_entry_t;
  39
  40 struct lrad_fifo_t {
  41         lrad_fifo_entry_t *head, **tail;
  42         lrad_fifo_entry_t *freelist;
  43
  44         int num_elements;
  45         int max_entries;
  46         lrad_fifo_free_t freeNode;
  47 };
  48
  49
  50 lrad_fifo_t *lrad_fifo_create(int max_entries, lrad_fifo_free_t freeNode)
  51 {
  52         lrad_fifo_t *fi;
  53
  54         if ((max_entries < 2) || (max_entries > (1024 * 1024))) return NULL;
  55
  56         fi = malloc(sizeof(*fi));
  57         if (!fi) return NULL;
  58
  59         memset(fi, 0, sizeof(*fi));
  60
  61         fi->max_entries = max_entries;
  62         fi->freeNode = freeNode;
  63
  64         return fi;
  65 }
  66
  67 static void lrad_fifo_free_entries(lrad_fifo_t *fi, lrad_fifo_entry_t *head)
  68 {
  69         lrad_fifo_entry_t *next;
  70
  71         while (head) {
  72                 next = head->next;
  73
  74                 if (fi->freeNode && head->data) fi->freeNode(head->data);
  75                 free(head);
  76
  77                 head = next;
  78         }
  79 }
  80
  81 void lrad_fifo_free(lrad_fifo_t *fi)
  82 {
  83         if (!fi) return;
  84
  85         lrad_fifo_free_entries(fi, fi->head);
  86         lrad_fifo_free_entries(fi, fi->freelist);
  87
  88         free(fi);
  89 }
  90
  91 static lrad_fifo_entry_t *lrad_fifo_alloc_entry(lrad_fifo_t *fi)
  92 {
  93         lrad_fifo_entry_t *entry;
  94
  95         if (fi->freelist) {
  96                 entry = fi->freelist;
  97                 fi->freelist = entry->next;
  98         } else {
  99                 entry = malloc(sizeof(*entry));
 100                 if (!entry) return NULL;
 101         }
 102
 103         memset(entry, 0, sizeof(*entry));
 104         return entry;
 105 }
 106
 107 int lrad_fifo_push(lrad_fifo_t *fi, void *data)
 108 {
 109         lrad_fifo_entry_t *entry;
 110
 111         if (!fi || !data) return 0;
 112
 113         if (fi->num_elements >= fi->max_entries) return 0;
 114
 115         entry = lrad_fifo_alloc_entry(fi);
 116         if (!entry) return 0;
 117         entry->data = data;
 118
 119         if (!fi->head) {
 120                 fi->head = entry;
 121         } else {
 122                 *fi->tail = entry;
 123         }
 124         fi->tail = &(entry->next);
 125
 126         fi->num_elements++;
 127
 128         return 1;
 129 }
 130
 131 static void lrad_fifo_free_entry(lrad_fifo_t *fi, lrad_fifo_entry_t *entry)
 132 {
 133         entry->data = NULL;
 134         entry->next = fi->freelist;
 135         fi->freelist = entry->next;
 136 }
 137
 138
 139 void *lrad_fifo_pop(lrad_fifo_t *fi)
 140 {
 141         void *data;
 142         lrad_fifo_entry_t *entry;
 143
 144         if (!fi || !fi->head) return 0;
 145
 146         entry = fi->head;
 147         fi->head = entry->next;
 148
 149         data = entry->data;
 150         lrad_fifo_free_entry(fi, entry);
 151
 152         fi->num_elements--;
 153
 154         if (!fi->head) {
 155                 fi->tail = NULL;
 156                 fi->num_elements = 0;
 157         }
 158
 159         return data;
 160 }
 161
 162 #ifdef TESTING
 163
 164 /*
 165  *  cc -DTESTING -I .. fifo.c -o fifo
 166  *
 167  *  ./fifo
 168  */
 169
 170 #define MAX 1024
 171 int main(int argc, char **argv)
 172 {
 173         int i, array[MAX];
 174         lrad_fifo_t *fi;
 175
 176         fi = lrad_fifo_create(MAX, NULL);
 177         if (!fi) exit(1);
 178
 179         for (i = 0; i < MAX; i++) {
 180                 array[i] = i;
 181
 182                 if (!lrad_fifo_push(fi, &array[i])) exit(2);
 183         }
 184
 185         for (i = 0; i < MAX; i++) {
 186                 int *p;
 187
 188                 p = lrad_fifo_pop(fi);
 189                 if (!p) {
 190                         fprintf(stderr, "No pop at %d\n", i);
 191                         exit(3);
 192                 }
 193
 194                 if (*p != i) exit(4);
 195         }
 196
 197         exit(0);
 198 }
 199 #endif