include/sq.h

   1 /*
   2  * Copyright (c) 2003-2004 MontaVista Software, Inc.
   3  *
   4  * All rights reserved.
   5  *
   6  * Author: Steven Dake (sdake@mvista.com)
   7  *
   8  * This software licensed under BSD license, the text of which follows:
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions are met:
  12  *
  13  * - Redistributions of source code must retain the above copyright notice,
  14  *   this list of conditions and the following disclaimer.
  15  * - Redistributions in binary form must reproduce the above copyright notice,
  16  *   this list of conditions and the following disclaimer in the documentation
  17  *   and/or other materials provided with the distribution.
  18  * - Neither the name of the MontaVista Software, Inc. nor the names of its
  19  *   contributors may be used to endorse or promote products derived from this
  20  *   software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  23  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  26  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  27  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  28  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  29  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  30  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  31  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  32  * THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34 #ifndef SORTQUEUE_H_DEFINED
  35 #define SORTQUEUE_H_DEFINED
  36
  37 #include "errno.h"
  38
  39 struct sq {
  40         unsigned int head;
  41         unsigned int size;
  42         void *items;
  43         unsigned int *items_inuse;
  44         unsigned int size_per_item;
  45         unsigned int head_seqid;
  46         unsigned int item_count;
  47         unsigned int pos_max;
  48 };
  49
  50 /*
  51  * Compare a unsigned rollover-safe value to an unsigned rollover-safe value
  52  */
  53
  54 /*
  55  * ADJUST_ROLLOVER_POINT is the value used to determine when a window should be
  56  *      used to calculate a less-then or less-then-equal comparison.
  57  *
  58  * ADJUST_ROLLOVER_VALUE is the value by which both values in a comparison are
  59  *      adjusted if either value in a comparison is greater then
  60  *      ADJUST_ROLLOVER_POINT.
  61  */
  62 #define ADJUST_ROLLOVER_POINT 0x80000000
  63 #define ADJUST_ROLLOVER_VALUE 0x10000
  64
  65 static inline int sq_lt_compare (unsigned int a, unsigned int b) {
  66         if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
  67                 if ((a - ADJUST_ROLLOVER_VALUE) < (b - ADJUST_ROLLOVER_VALUE)) {
  68                         return (1);
  69                 }
  70         } else {
  71                 if (a < b) {
  72                         return (1);
  73                 }
  74         }
  75         return (0);
  76 }
  77
  78 static inline int sq_lte_compare (unsigned int a, unsigned int b) {
  79         if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
  80                 if ((a - ADJUST_ROLLOVER_VALUE) <= (b - ADJUST_ROLLOVER_VALUE)) {
  81                         return (1);
  82                 }
  83         } else {
  84                 if (a <= b) {
  85                         return (1);
  86                 }
  87         }
  88         return (0);
  89 }
  90
  91 static inline int sq_init (
  92         struct sq *sq,
  93         int item_count,
  94         int size_per_item,
  95         int head_seqid)
  96 {
  97         sq->head = 0;
  98         sq->size = item_count;
  99         sq->size_per_item = size_per_item;
 100         sq->head_seqid = head_seqid;
 101         sq->item_count = item_count;
 102         sq->pos_max = 0;
 103
 104         sq->items = (void *)malloc (item_count * size_per_item);
 105         if (sq->items == 0) {
 106                 return (-ENOMEM);
 107         }
 108         memset (sq->items, 0, item_count * size_per_item);
 109
 110         sq->items_inuse = (void *)malloc (item_count * sizeof (unsigned int));
 111         memset (sq->items_inuse, 0, item_count * sizeof (unsigned int));
 112         return (0);
 113 }
 114
 115 static inline void sq_reinit (struct sq *sq, unsigned int head_seqid)
 116 {
 117         sq->head = 0;
 118         sq->head_seqid = head_seqid;
 119         sq->pos_max = 0;
 120
 121         memset (sq->items, 0, sq->item_count * sq->size_per_item);
 122         memset (sq->items_inuse, 0, sq->item_count * sizeof (unsigned int));
 123 }
 124
 125 static inline void sq_assert (struct sq *sq, unsigned int pos)
 126 {
 127         unsigned int i;
 128
 129 //      printf ("Instrument[%d] Asserting from %d to %d\n",
 130 //              pos, sq->pos_max, sq->size);
 131         for (i = sq->pos_max + 1; i < sq->size; i++) {
 132                 assert (sq->items_inuse[i] == 0);
 133         }
 134 }
 135 static inline void sq_copy (struct sq *sq_dest, struct sq *sq_src)
 136 {
 137         sq_assert (sq_src, 20);
 138         sq_dest->head = sq_src->head;
 139         sq_dest->size = sq_src->item_count;
 140         sq_dest->size_per_item = sq_src->size_per_item;
 141         sq_dest->head_seqid = sq_src->head_seqid;
 142         sq_dest->item_count = sq_src->item_count;
 143         sq_dest->pos_max = sq_src->pos_max;
 144         memcpy (sq_dest->items, sq_src->items,
 145                 sq_src->item_count * sq_src->size_per_item);
 146         memcpy (sq_dest->items_inuse, sq_src->items_inuse,
 147                 sq_src->item_count * sizeof (unsigned int));
 148 }
 149
 150 static inline void sq_free (struct sq *sq) {
 151         free (sq->items);
 152         free (sq->items_inuse);
 153 }
 154
 155 static inline void *sq_item_add (
 156         struct sq *sq,
 157         void *item,
 158         unsigned int seqid)
 159 {
 160         char *sq_item;
 161         unsigned int sq_position;
 162
 163         sq_position = (sq->head + seqid - sq->head_seqid) % sq->size;
 164         if (sq_position > sq->pos_max) {
 165                 sq->pos_max = sq_position;
 166         }
 167
 168         sq_item = sq->items;
 169         sq_item += sq_position * sq->size_per_item;
 170         assert(sq->items_inuse[sq_position] == 0);
 171         memcpy (sq_item, item, sq->size_per_item);
 172         if (seqid == 0) {
 173                 sq->items_inuse[sq_position] = 1;
 174         } else {
 175                 sq->items_inuse[sq_position] = seqid;
 176         }
 177
 178         return (sq_item);
 179 }
 180
 181 static inline unsigned int sq_item_inuse (
 182         struct sq *sq,
 183         unsigned int seq_id) {
 184
 185         unsigned int sq_position;
 186
 187         /*
 188          * We need to say that the seqid is in use if it shouldn't
 189          * be here in the first place.
 190          * To keep old messages from being inserted.
 191          */
 192 #ifdef COMPILE_OUT
 193         if (seq_id < sq->head_seqid) {
 194                 fprintf(stderr, "sq_item_inuse: seqid %d, head %d\n",
 195                                                 seq_id, sq->head_seqid);
 196                 return 1;
 197         }
 198 #endif
 199         sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
 200         return (sq->items_inuse[sq_position] != 0);
 201 }
 202
 203 static inline unsigned int sq_size_get (
 204         struct sq *sq)
 205 {
 206         return sq->size;
 207 }
 208
 209 static inline unsigned int sq_in_range (
 210         struct sq *sq,
 211         unsigned int seq_id)
 212 {
 213         int res = 1;
 214
 215         if (sq->head_seqid > ADJUST_ROLLOVER_POINT) {
 216                 if (seq_id - ADJUST_ROLLOVER_VALUE <
 217                         sq->head_seqid - ADJUST_ROLLOVER_VALUE) {
 218
 219                         res = 0;
 220                 }
 221                 if ((seq_id - ADJUST_ROLLOVER_VALUE) >=
 222                         ((sq->head_seqid - ADJUST_ROLLOVER_VALUE) + sq->size)) {
 223
 224                         res = 0;
 225                 }
 226         } else {
 227                 if (seq_id < sq->head_seqid) {
 228                         res = 0;
 229                 }
 230                 if ((seq_id) >= ((sq->head_seqid) + sq->size)) {
 231                         res = 0;
 232                 }
 233         }
 234         return (res);
 235
 236 }
 237
 238 static inline unsigned int sq_item_get (
 239         struct sq *sq,
 240         unsigned int seq_id,
 241         void **sq_item_out)
 242 {
 243         char *sq_item;
 244         unsigned int sq_position;
 245
 246         if (seq_id > ADJUST_ROLLOVER_POINT) {
 247                 assert ((seq_id - ADJUST_ROLLOVER_POINT) <
 248                         ((sq->head_seqid - ADJUST_ROLLOVER_POINT) + sq->size));
 249
 250                 sq_position = ((sq->head - ADJUST_ROLLOVER_VALUE) -
 251                         (sq->head_seqid - ADJUST_ROLLOVER_VALUE) + seq_id) % sq->size;
 252         } else {
 253                 assert (seq_id < (sq->head_seqid + sq->size));
 254                 sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
 255         }
 256 //printf ("seqid %x head %x head %x pos %x\n", seq_id, sq->head, sq->head_seqid, sq_position);
 257 //      sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
 258 //printf ("sq_position = %x\n", sq_position);
 259 //printf ("ITEMGET %d %d %d %d\n", sq_position, sq->head, sq->head_seqid, seq_id);
 260 assert (sq_position >= 0);
 261         if (sq->items_inuse[sq_position] == 0) {
 262                 return (ENOENT);
 263         }
 264         sq_item = sq->items;
 265         sq_item += sq_position * sq->size_per_item;
 266         *sq_item_out = sq_item;
 267         return (0);
 268 }
 269
 270 static inline void sq_items_release (struct sq *sq, unsigned int seqid)
 271 {
 272         unsigned int oldhead;
 273
 274         oldhead = sq->head;
 275
 276         sq->head = (sq->head + seqid - sq->head_seqid + 1) % sq->size;
 277         if ((oldhead + seqid - sq->head_seqid + 1) > sq->size) {
 278 //              printf ("releasing %d for %d\n", oldhead, sq->size - oldhead);
 279 //              printf ("releasing %d for %d\n", 0, sq->head);
 280                 memset (&sq->items_inuse[oldhead], 0, sq->size - oldhead);
 281                 memset (sq->items_inuse, 0, sq->head * sizeof (unsigned int));
 282         } else {
 283 //              printf ("releasing %d for %d\n", oldhead, seqid - sq->head_seqid + 1);
 284                 memset (&sq->items_inuse[oldhead], 0,
 285                         (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
 286         }
 287         sq->head_seqid = seqid + 1;
 288 }
 289
 290 #endif /* SORTQUEUE_H_DEFINED */