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