corosync  2.3.6
sq.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2003-2004 MontaVista Software, Inc.
3  *
4  * All rights reserved.
5  *
6  * Author: Steven Dake (sdake@redhat.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 #include <string.h>
39 
43 struct sq {
44  unsigned int head;
45  unsigned int size;
46  void *items;
47  unsigned int *items_inuse;
48  unsigned int *items_miss_count;
49  unsigned int size_per_item;
50  unsigned int head_seqid;
51  unsigned int item_count;
52  unsigned int pos_max;
53 };
54 
55 /*
56  * Compare a unsigned rollover-safe value to an unsigned rollover-safe value
57  */
58 
63 #define ADJUST_ROLLOVER_POINT 0x80000000
64 
70 #define ADJUST_ROLLOVER_VALUE 0x10000
71 
78 static inline int sq_lt_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 
97 static inline int sq_lte_compare (unsigned int a, unsigned int b) {
98  if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
99  if ((a - ADJUST_ROLLOVER_VALUE) <= (b - ADJUST_ROLLOVER_VALUE)) {
100  return (1);
101  }
102  } else {
103  if (a <= b) {
104  return (1);
105  }
106  }
107  return (0);
108 }
109 
118 static inline int sq_init (
119  struct sq *sq,
120  int item_count,
121  int size_per_item,
122  int head_seqid)
123 {
124  sq->head = 0;
125  sq->size = item_count;
127  sq->head_seqid = head_seqid;
128  sq->item_count = item_count;
129  sq->pos_max = 0;
130 
131  sq->items = malloc (item_count * size_per_item);
132  if (sq->items == NULL) {
133  return (-ENOMEM);
134  }
135  memset (sq->items, 0, item_count * size_per_item);
136 
137  if ((sq->items_inuse = malloc (item_count * sizeof (unsigned int)))
138  == NULL) {
139  return (-ENOMEM);
140  }
141  if ((sq->items_miss_count = malloc (item_count * sizeof (unsigned int)))
142  == NULL) {
143  return (-ENOMEM);
144  }
145  memset (sq->items_inuse, 0, item_count * sizeof (unsigned int));
146  memset (sq->items_miss_count, 0, item_count * sizeof (unsigned int));
147  return (0);
148 }
149 
155 static inline void sq_reinit (struct sq *sq, unsigned int head_seqid)
156 {
157  sq->head = 0;
158  sq->head_seqid = head_seqid;
159  sq->pos_max = 0;
160 
161  memset (sq->items, 0, sq->item_count * sq->size_per_item);
162  memset (sq->items_inuse, 0, sq->item_count * sizeof (unsigned int));
163  memset (sq->items_miss_count, 0, sq->item_count * sizeof (unsigned int));
164 }
165 
171 static inline void sq_assert (const struct sq *sq, unsigned int pos)
172 {
173  unsigned int i;
174 
175 // printf ("Instrument[%d] Asserting from %d to %d\n",
176 // pos, sq->pos_max, sq->size);
177  for (i = sq->pos_max + 1; i < sq->size; i++) {
178  assert (sq->items_inuse[i] == 0);
179  }
180 }
181 
187 static inline void sq_copy (struct sq *sq_dest, const struct sq *sq_src)
188 {
189  sq_assert (sq_src, 20);
190  sq_dest->head = sq_src->head;
191  sq_dest->size = sq_src->item_count;
192  sq_dest->size_per_item = sq_src->size_per_item;
193  sq_dest->head_seqid = sq_src->head_seqid;
194  sq_dest->item_count = sq_src->item_count;
195  sq_dest->pos_max = sq_src->pos_max;
196  memcpy (sq_dest->items, sq_src->items,
197  sq_src->item_count * sq_src->size_per_item);
198  memcpy (sq_dest->items_inuse, sq_src->items_inuse,
199  sq_src->item_count * sizeof (unsigned int));
200  memcpy (sq_dest->items_miss_count, sq_src->items_miss_count,
201  sq_src->item_count * sizeof (unsigned int));
202 }
203 
208 static inline void sq_free (struct sq *sq) {
209  free (sq->items);
210  free (sq->items_inuse);
211  free (sq->items_miss_count);
212 }
213 
221 static inline void *sq_item_add (
222  struct sq *sq,
223  void *item,
224  unsigned int seqid)
225 {
226  char *sq_item;
227  unsigned int sq_position;
228 
229  sq_position = (sq->head + seqid - sq->head_seqid) % sq->size;
230  if (sq_position > sq->pos_max) {
231  sq->pos_max = sq_position;
232  }
233 
234  sq_item = sq->items;
235  sq_item += sq_position * sq->size_per_item;
236  assert(sq->items_inuse[sq_position] == 0);
237  memcpy (sq_item, item, sq->size_per_item);
238  if (seqid == 0) {
239  sq->items_inuse[sq_position] = 1;
240  } else {
241  sq->items_inuse[sq_position] = seqid;
242  }
243  sq->items_miss_count[sq_position] = 0;
244 
245  return (sq_item);
246 }
247 
254 static inline unsigned int sq_item_inuse (
255  const struct sq *sq,
256  unsigned int seq_id) {
257 
258  unsigned int sq_position;
259 
260  /*
261  * We need to say that the seqid is in use if it shouldn't
262  * be here in the first place.
263  * To keep old messages from being inserted.
264  */
265 #ifdef COMPILE_OUT
266  if (seq_id < sq->head_seqid) {
267  fprintf(stderr, "sq_item_inuse: seqid %d, head %d\n",
268  seq_id, sq->head_seqid);
269  return 1;
270  }
271 #endif
272  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
273  return (sq->items_inuse[sq_position] != 0);
274 }
275 
282 static inline unsigned int sq_item_miss_count (
283  const struct sq *sq,
284  unsigned int seq_id)
285 {
286  unsigned int sq_position;
287 
288  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
289  sq->items_miss_count[sq_position]++;
290  return (sq->items_miss_count[sq_position]);
291 }
292 
298 static inline unsigned int sq_size_get (
299  const struct sq *sq)
300 {
301  return sq->size;
302 }
303 
310 static inline unsigned int sq_in_range (
311  const struct sq *sq,
312  unsigned int seq_id)
313 {
314  int res = 1;
315 
316  if (sq->head_seqid > ADJUST_ROLLOVER_POINT) {
317  if (seq_id - ADJUST_ROLLOVER_VALUE <
319 
320  res = 0;
321  }
322  if ((seq_id - ADJUST_ROLLOVER_VALUE) >=
323  ((sq->head_seqid - ADJUST_ROLLOVER_VALUE) + sq->size)) {
324 
325  res = 0;
326  }
327  } else {
328  if (seq_id < sq->head_seqid) {
329  res = 0;
330  }
331  if ((seq_id) >= ((sq->head_seqid) + sq->size)) {
332  res = 0;
333  }
334  }
335  return (res);
336 
337 }
338 
346 static inline unsigned int sq_item_get (
347  const struct sq *sq,
348  unsigned int seq_id,
349  void **sq_item_out)
350 {
351  char *sq_item;
352  unsigned int sq_position;
353 
354  if (seq_id > ADJUST_ROLLOVER_POINT) {
355  assert ((seq_id - ADJUST_ROLLOVER_POINT) <
356  ((sq->head_seqid - ADJUST_ROLLOVER_POINT) + sq->size));
357 
358  sq_position = ((sq->head - ADJUST_ROLLOVER_VALUE) -
359  (sq->head_seqid - ADJUST_ROLLOVER_VALUE) + seq_id) % sq->size;
360  } else {
361  assert (seq_id < (sq->head_seqid + sq->size));
362  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
363  }
364 //printf ("seqid %x head %x head %x pos %x\n", seq_id, sq->head, sq->head_seqid, sq_position);
365 // sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
366 //printf ("sq_position = %x\n", sq_position);
367 //printf ("ITEMGET %d %d %d %d\n", sq_position, sq->head, sq->head_seqid, seq_id);
368  if (sq->items_inuse[sq_position] == 0) {
369  return (ENOENT);
370  }
371  sq_item = sq->items;
372  sq_item += sq_position * sq->size_per_item;
373  *sq_item_out = sq_item;
374  return (0);
375 }
376 
382 static inline void sq_items_release (struct sq *sq, unsigned int seqid)
383 {
384  unsigned int oldhead;
385 
386  oldhead = sq->head;
387 
388  sq->head = (sq->head + seqid - sq->head_seqid + 1) % sq->size;
389  if ((oldhead + seqid - sq->head_seqid + 1) > sq->size) {
390 // printf ("releasing %d for %d\n", oldhead, sq->size - oldhead);
391 // printf ("releasing %d for %d\n", 0, sq->head);
392  memset (&sq->items_inuse[oldhead], 0, (sq->size - oldhead) * sizeof (unsigned int));
393  memset (sq->items_inuse, 0, sq->head * sizeof (unsigned int));
394  } else {
395 // printf ("releasing %d for %d\n", oldhead, seqid - sq->head_seqid + 1);
396  memset (&sq->items_inuse[oldhead], 0,
397  (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
398  memset (&sq->items_miss_count[oldhead], 0,
399  (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
400  }
401  sq->head_seqid = seqid + 1;
402 }
403 
404 #endif /* SORTQUEUE_H_DEFINED */
unsigned int head_seqid
Definition: sq.h:50
The sq struct.
Definition: sq.h:43
unsigned int pos_max
Definition: sq.h:52
unsigned int size_per_item
Definition: sq.h:49
unsigned int * items_inuse
Definition: sq.h:47
#define ADJUST_ROLLOVER_POINT
ADJUST_ROLLOVER_POINT is the value used to determine when a window should be used to calculate a less...
Definition: sq.h:63
unsigned int item_count
Definition: sq.h:51
unsigned int size
Definition: sq.h:45
unsigned int head
Definition: sq.h:44
unsigned int * items_miss_count
Definition: sq.h:48
void * items
Definition: sq.h:46
#define ADJUST_ROLLOVER_VALUE
ADJUST_ROLLOVER_VALUE is the value by which both values in a comparison are adjusted if either value ...
Definition: sq.h:70