fifo.c

Go to the documentation of this file.

/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/** Non-thread-safe fifo (FIFO) implementation
 *
 * @file src/lib/util/fifo.c
 *
 * @copyright 2005,2006 The FreeRADIUS server project
 * @copyright 2005 Alan DeKok (aland@freeradius.org)
 */
RCSID("$Id: 3c967c14f10148ad89679fcadadb49fb8f212808 $")
 
#include <string.h>
 
#include <freeradius-devel/util/fifo.h>
 
struct fr_fifo_s {
        unsigned int    num;            //!< How many elements exist in the fifo.
        unsigned int    first, last;    //!< Head and tail indexes for the fifo.
        unsigned int    max;            //!< How many elements were created in the fifo.
        fr_fifo_free_t  free_node;      //!< Function to call to free nodes when the fifo is freed.
 
        char const      *type;          //!< Type of elements.
 
        void *data[1];
};
 
/** Free a fifo and optionally, any data still enqueued
 *
 * @param[in] fi        to free.
 * @return 0
 */
static int _fifo_free(fr_fifo_t *fi)
{
        unsigned int i;
 
        if (fi->free_node) {
                for (i = 0 ; i < fi->num; i++) {
                        unsigned int element;
 
                        element = i + fi->first;
                        if (element > fi->max) {
                                element -= fi->max;
                        }
 
                        fi->free_node(fi->data[element]);
                        fi->data[element] = NULL;
                }
        }
 
        memset(fi, 0, sizeof(*fi));
 
        return 0;
}
 
/** Create a fifo queue
 *
 * The first element enqueued will be the first to be dequeued.
 *
 * @note The created fifo does not provide any thread synchronisation functionality
 *      such as mutexes.  If multiple threads are enqueueing and dequeueing data
 *      the callers must synchronise their access.
 *
 * @param[in] ctx       to allocate fifo array in.
 * @param[in] type      Talloc type of elements (may be NULL).
 * @param[in] max       The maximum number of elements allowed.
 * @param[in] free_node Function to use to free node data if the fifo is freed.
 * @return
 *      - A new fifo queue.
 *      - NULL on error.
 */
fr_fifo_t *_fr_fifo_create(TALLOC_CTX *ctx, char const *type, int max, fr_fifo_free_t free_node)
{
        fr_fifo_t *fi;
 
        if ((max < 2) || (max > (1024 * 1024))) return NULL;
 
        fi = talloc_zero_size(ctx, (sizeof(*fi) + (sizeof(fi->data[0])*max)));
        if (!fi) return NULL;
        talloc_set_type(fi, fr_fifo_t);
        talloc_set_destructor(fi, _fifo_free);
 
        fi->max = max;
        fi->type = type;
        fi->free_node = free_node;
 
        return fi;
}
 
/** Push data onto the fifo
 *
 * @param[in] fi        FIFO to push data onto.
 * @param[in] data      to push.
 * @return
 *      - 0 on success.
 *      - -1 on error.
 */
int fr_fifo_push(fr_fifo_t *fi, void *data)
{
        if (!fi || !data) return -1;
 
        if (fi->num >= fi->max) return -1;
 
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
        if (fi->type) _talloc_get_type_abort(data, fi->type, __location__);
#endif
 
        fi->data[fi->last++] = data;
        if (fi->last >= fi->max) fi->last = 0;
        fi->num++;
 
        return 0;
}
 
/** Pop data off of the fifo
 *
 * @param[in] fi        FIFO to pop data from.
 * @return
 *      - The data popped.
 *      - NULL if the queue is empty.
 */
void *fr_fifo_pop(fr_fifo_t *fi)
{
        void *data;
 
        if (!fi || (fi->num == 0)) return NULL;
 
        data = fi->data[fi->first++];
 
        if (fi->first >= fi->max) {
                fi->first = 0;
        }
        fi->num--;
 
        return data;
}
 
/** Examine the next element that would be popped
 *
 * @param[in] fi        FIFO to peek at.
 * @return
 *      - The data at the head of the queue
 *      - NULL if the queue is empty.
 */
void *fr_fifo_peek(fr_fifo_t *fi)
{
        if (!fi || (fi->num == 0)) return NULL;
 
        return fi->data[fi->first];
}
 
/** Return the number of elements in the fifo queue
 *
 * @param[in] fi        FIFO to count elements in.
 * @return the number of elements
 */
unsigned int fr_fifo_num_elements(fr_fifo_t *fi)
{
        if (!fi) return 0;
 
        return fi->num;
}
 
#ifdef TESTING
 
/*
 *  cc -DTESTING -I .. fifo.c -o fifo
 *
 *  ./fifo
 */
 
#define MAX 1024
int main(int argc, char **argv)
{
        int i, j, array[MAX];
        fr_fifo_t *fi;
 
        fi = fr_fifo_create(NULL, MAX, NULL);
        if (!fi) fr_exit(1);
 
        for (j = 0; j < 5; j++) {
#define SPLIT (MAX/3)
#define COUNT ((j * SPLIT) + i)
                for (i = 0; i < SPLIT; i++) {
                        array[COUNT % MAX] = COUNT;
 
                        if (fr_fifo_push(fi, &array[COUNT % MAX]) < 0) {
                                fprintf(stderr, "%d %d\tfailed pushing %d\n",
                                        j, i, COUNT);
                                fr_exit(2);
                        }
 
                        if (fr_fifo_num_elements(fi) != (i + 1)) {
                                fprintf(stderr, "%d %d\tgot size %d expected %d\n",
                                        j, i, i + 1, fr_fifo_num_elements(fi));
                                fr_exit(1);
                        }
                }
 
                if (fr_fifo_num_elements(fi) != SPLIT) {
                        fprintf(stderr, "HALF %d %d\n",
                                fr_fifo_num_elements(fi), SPLIT);
                        fr_exit(1);
                }
 
                for (i = 0; i < SPLIT; i++) {
                        int *p;
 
                        p = fr_fifo_pop(fi);
                        if (!p) {
                                fprintf(stderr, "No pop at %d\n", i);
                                fr_exit(3);
                        }
 
                        if (*p != COUNT) {
                                fprintf(stderr, "%d %d\tgot %d expected %d\n",
                                        j, i, *p, COUNT);
                                fr_exit(4);
                        }
 
                        if (fr_fifo_num_elements(fi) != SPLIT - (i + 1)) {
                                fprintf(stderr, "%d %d\tgot size %d expected %d\n",
                                        j, i, SPLIT - (i + 1), fr_fifo_num_elements(fi));
                                fr_exit(1);
                        }
                }
 
                if (fr_fifo_num_elements(fi) != 0) {
                        fprintf(stderr, "ZERO %d %d\n",
                                fr_fifo_num_elements(fi), 0);
                        fr_exit(1);
                }
        }
 
        talloc_free(fi);
 
        fr_exit(0);
}
#endif