sq.h

Go to the documentation of this file.

/*
 * Copyright (c) 2003-2004 MontaVista Software, Inc.
 *
 * All rights reserved.
 *
 * Author: Steven Dake (sdake@redhat.com)
 *
 * This software licensed under BSD license, the text of which follows:
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * - Neither the name of the MontaVista Software, Inc. nor the names of its
 *   contributors may be used to endorse or promote products derived from this
 *   software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */
#ifndef SORTQUEUE_H_DEFINED
#define SORTQUEUE_H_DEFINED
 
#include <errno.h>
#include <string.h>
 
struct sq {
        unsigned int head;
        unsigned int size;
        void *items;
        unsigned int *items_inuse;
        unsigned int *items_miss_count;
        unsigned int size_per_item;
        unsigned int head_seqid;
        unsigned int item_count;
        unsigned int pos_max;
};
 
/*
 * Compare a unsigned rollover-safe value to an unsigned rollover-safe value
 */
 
#define ADJUST_ROLLOVER_POINT 0x80000000
 
#define ADJUST_ROLLOVER_VALUE 0x10000
 
static inline int sq_lt_compare (unsigned int a, unsigned int b) {
        if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
                if ((a - ADJUST_ROLLOVER_VALUE) < (b - ADJUST_ROLLOVER_VALUE)) {
                        return (1);
                }
        } else {
                if (a < b) {
                        return (1);
                }
        }
        return (0);
}
 
static inline int sq_lte_compare (unsigned int a, unsigned int b) {
        if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
                if ((a - ADJUST_ROLLOVER_VALUE) <= (b - ADJUST_ROLLOVER_VALUE)) {
                        return (1);
                }
        } else {
                if (a <= b) {
                        return (1);
                }
        }
        return (0);
}
 
static inline int sq_init (
        struct sq *sq,
        int item_count,
        int size_per_item,
        int head_seqid)
{
        sq->head = 0;
        sq->size = item_count;
        sq->size_per_item = size_per_item;
        sq->head_seqid = head_seqid;
        sq->item_count = item_count;
        sq->pos_max = 0;
 
        sq->items = malloc (item_count * size_per_item);
        if (sq->items == NULL) {
                return (-ENOMEM);
        }
        memset (sq->items, 0, item_count * size_per_item);
 
        if ((sq->items_inuse = malloc (item_count * sizeof (unsigned int)))
            == NULL) {
                return (-ENOMEM);
        }
        if ((sq->items_miss_count = malloc (item_count * sizeof (unsigned int)))
            == NULL) {
                return (-ENOMEM);
        }
        memset (sq->items_inuse, 0, item_count * sizeof (unsigned int));
        memset (sq->items_miss_count, 0, item_count * sizeof (unsigned int));
        return (0);
}
 
static inline void sq_reinit (struct sq *sq, unsigned int head_seqid)
{
        sq->head = 0;
        sq->head_seqid = head_seqid;
        sq->pos_max = 0;
 
        memset (sq->items, 0, sq->item_count * sq->size_per_item);
        memset (sq->items_inuse, 0, sq->item_count * sizeof (unsigned int));
        memset (sq->items_miss_count, 0, sq->item_count * sizeof (unsigned int));
}
 
static inline void sq_assert (const struct sq *sq, unsigned int pos)
{
        unsigned int i;
 
//      printf ("Instrument[%d] Asserting from %d to %d\n",
//              pos, sq->pos_max, sq->size);
        for (i = sq->pos_max + 1; i < sq->size; i++) {
                assert (sq->items_inuse[i] == 0);
        }
}
 
static inline void sq_copy (struct sq *sq_dest, const struct sq *sq_src)
{
        sq_assert (sq_src, 20);
        sq_dest->head = sq_src->head;
        sq_dest->size = sq_src->item_count;
        sq_dest->size_per_item = sq_src->size_per_item;
        sq_dest->head_seqid = sq_src->head_seqid;
        sq_dest->item_count = sq_src->item_count;
        sq_dest->pos_max = sq_src->pos_max;
        memcpy (sq_dest->items, sq_src->items,
                sq_src->item_count * sq_src->size_per_item);
        memcpy (sq_dest->items_inuse, sq_src->items_inuse,
                sq_src->item_count * sizeof (unsigned int));
        memcpy (sq_dest->items_miss_count, sq_src->items_miss_count,
                sq_src->item_count * sizeof (unsigned int));
}
 
static inline void sq_free (struct sq *sq) {
        free (sq->items);
        free (sq->items_inuse);
        free (sq->items_miss_count);
}
 
static inline void *sq_item_add (
        struct sq *sq,
        void *item,
        unsigned int seqid)
{
        char *sq_item;
        unsigned int sq_position;
 
        sq_position = (sq->head + seqid - sq->head_seqid) % sq->size;
        if (sq_position > sq->pos_max) {
                sq->pos_max = sq_position;
        }
 
        sq_item = sq->items;
        sq_item += sq_position * sq->size_per_item;
        assert(sq->items_inuse[sq_position] == 0);
        memcpy (sq_item, item, sq->size_per_item);
        if (seqid == 0) {
                sq->items_inuse[sq_position] = 1;
        } else {
                sq->items_inuse[sq_position] = seqid;
        }
        sq->items_miss_count[sq_position] = 0;
 
        return (sq_item);
}
 
static inline unsigned int sq_item_inuse (
        const struct sq *sq,
        unsigned int seq_id) {
 
        unsigned int sq_position;
 
        /*
         * We need to say that the seqid is in use if it shouldn't
         * be here in the first place.
         * To keep old messages from being inserted.
         */
#ifdef COMPILE_OUT
        if (seq_id < sq->head_seqid) {
                fprintf(stderr, "sq_item_inuse: seqid %d, head %d\n",
                                                seq_id, sq->head_seqid);
                return 1;
        }
#endif
        sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
        return (sq->items_inuse[sq_position] != 0);
}
 
static inline unsigned int sq_item_miss_count (
        const struct sq *sq,
        unsigned int seq_id)
{
        unsigned int sq_position;
 
        sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
        sq->items_miss_count[sq_position]++;
        return (sq->items_miss_count[sq_position]);
}
 
static inline unsigned int sq_size_get (
        const struct sq *sq)
{
        return sq->size;
}
 
static inline unsigned int sq_in_range (
        const struct sq *sq,
        unsigned int seq_id)
{
        int res = 1;
 
        if (sq->head_seqid > ADJUST_ROLLOVER_POINT) {
                if (seq_id - ADJUST_ROLLOVER_VALUE <
                        sq->head_seqid - ADJUST_ROLLOVER_VALUE) {
 
                        res = 0;
                }
                if ((seq_id - ADJUST_ROLLOVER_VALUE) >=
                        ((sq->head_seqid - ADJUST_ROLLOVER_VALUE) + sq->size)) {
 
                        res = 0;
                }
        } else {
                if (seq_id < sq->head_seqid) {
                        res = 0;
                }
                if ((seq_id) >= ((sq->head_seqid) + sq->size)) {
                        res = 0;
                }
        }
        return (res);
 
}
 
static inline unsigned int sq_item_get (
        const struct sq *sq,
        unsigned int seq_id,
        void **sq_item_out)
{
        char *sq_item;
        unsigned int sq_position;
 
        if (seq_id > ADJUST_ROLLOVER_POINT) {
                assert ((seq_id - ADJUST_ROLLOVER_POINT) <
                        ((sq->head_seqid - ADJUST_ROLLOVER_POINT) + sq->size));
 
                sq_position = ((sq->head - ADJUST_ROLLOVER_VALUE) -
                        (sq->head_seqid - ADJUST_ROLLOVER_VALUE) + seq_id) % sq->size;
        } else {
                assert (seq_id < (sq->head_seqid + sq->size));
                sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
        }
//printf ("seqid %x head %x head %x pos %x\n", seq_id, sq->head, sq->head_seqid, sq_position);
//      sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
//printf ("sq_position = %x\n", sq_position);
//printf ("ITEMGET %d %d %d %d\n", sq_position, sq->head, sq->head_seqid, seq_id);
        if (sq->items_inuse[sq_position] == 0) {
                return (ENOENT);
        }
        sq_item = sq->items;
        sq_item += sq_position * sq->size_per_item;
        *sq_item_out = sq_item;
        return (0);
}
 
static inline void sq_items_release (struct sq *sq, unsigned int seqid)
{
        unsigned int oldhead;
 
        oldhead = sq->head;
 
        sq->head = (sq->head + seqid - sq->head_seqid + 1) % sq->size;
        if ((oldhead + seqid - sq->head_seqid + 1) > sq->size) {
//              printf ("releasing %d for %d\n", oldhead, sq->size - oldhead);
//              printf ("releasing %d for %d\n", 0, sq->head);
                memset (&sq->items_inuse[oldhead], 0, (sq->size - oldhead) * sizeof (unsigned int));
                memset (sq->items_inuse, 0, sq->head * sizeof (unsigned int));
        } else {
//              printf ("releasing %d for %d\n", oldhead, seqid - sq->head_seqid + 1);
                memset (&sq->items_inuse[oldhead], 0,
                        (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
                memset (&sq->items_miss_count[oldhead], 0,
                        (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
        }
        sq->head_seqid = seqid + 1;
}
 
#endif /* SORTQUEUE_H_DEFINED */