corosync  2.3.2
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 
40 struct sq {
41  unsigned int head;
42  unsigned int size;
43  void *items;
44  unsigned int *items_inuse;
45  unsigned int *items_miss_count;
46  unsigned int size_per_item;
47  unsigned int head_seqid;
48  unsigned int item_count;
49  unsigned int pos_max;
50 };
51 
52 /*
53  * Compare a unsigned rollover-safe value to an unsigned rollover-safe value
54  */
55 
60 #define ADJUST_ROLLOVER_POINT 0x80000000
61 
66 #define ADJUST_ROLLOVER_VALUE 0x10000
67 
68 static inline int sq_lt_compare (unsigned int a, unsigned int b) {
69  if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
70  if ((a - ADJUST_ROLLOVER_VALUE) < (b - ADJUST_ROLLOVER_VALUE)) {
71  return (1);
72  }
73  } else {
74  if (a < b) {
75  return (1);
76  }
77  }
78  return (0);
79 }
80 
81 static inline int sq_lte_compare (unsigned int a, unsigned int b) {
82  if ((a > ADJUST_ROLLOVER_POINT) || (b > ADJUST_ROLLOVER_POINT)) {
83  if ((a - ADJUST_ROLLOVER_VALUE) <= (b - ADJUST_ROLLOVER_VALUE)) {
84  return (1);
85  }
86  } else {
87  if (a <= b) {
88  return (1);
89  }
90  }
91  return (0);
92 }
93 
94 static inline int sq_init (
95  struct sq *sq,
96  int item_count,
97  int size_per_item,
98  int head_seqid)
99 {
100  sq->head = 0;
101  sq->size = item_count;
102  sq->size_per_item = size_per_item;
103  sq->head_seqid = head_seqid;
104  sq->item_count = item_count;
105  sq->pos_max = 0;
106 
107  sq->items = malloc (item_count * size_per_item);
108  if (sq->items == NULL) {
109  return (-ENOMEM);
110  }
111  memset (sq->items, 0, item_count * size_per_item);
112 
113  if ((sq->items_inuse = malloc (item_count * sizeof (unsigned int)))
114  == NULL) {
115  return (-ENOMEM);
116  }
117  if ((sq->items_miss_count = malloc (item_count * sizeof (unsigned int)))
118  == NULL) {
119  return (-ENOMEM);
120  }
121  memset (sq->items_inuse, 0, item_count * sizeof (unsigned int));
122  memset (sq->items_miss_count, 0, item_count * sizeof (unsigned int));
123  return (0);
124 }
125 
126 static inline void sq_reinit (struct sq *sq, unsigned int head_seqid)
127 {
128  sq->head = 0;
129  sq->head_seqid = head_seqid;
130  sq->pos_max = 0;
131 
132  memset (sq->items, 0, sq->item_count * sq->size_per_item);
133  memset (sq->items_inuse, 0, sq->item_count * sizeof (unsigned int));
134  memset (sq->items_miss_count, 0, sq->item_count * sizeof (unsigned int));
135 }
136 
137 static inline void sq_assert (const struct sq *sq, unsigned int pos)
138 {
139  unsigned int i;
140 
141 // printf ("Instrument[%d] Asserting from %d to %d\n",
142 // pos, sq->pos_max, sq->size);
143  for (i = sq->pos_max + 1; i < sq->size; i++) {
144  assert (sq->items_inuse[i] == 0);
145  }
146 }
147 static inline void sq_copy (struct sq *sq_dest, const struct sq *sq_src)
148 {
149  sq_assert (sq_src, 20);
150  sq_dest->head = sq_src->head;
151  sq_dest->size = sq_src->item_count;
152  sq_dest->size_per_item = sq_src->size_per_item;
153  sq_dest->head_seqid = sq_src->head_seqid;
154  sq_dest->item_count = sq_src->item_count;
155  sq_dest->pos_max = sq_src->pos_max;
156  memcpy (sq_dest->items, sq_src->items,
157  sq_src->item_count * sq_src->size_per_item);
158  memcpy (sq_dest->items_inuse, sq_src->items_inuse,
159  sq_src->item_count * sizeof (unsigned int));
160  memcpy (sq_dest->items_miss_count, sq_src->items_miss_count,
161  sq_src->item_count * sizeof (unsigned int));
162 }
163 
164 static inline void sq_free (struct sq *sq) {
165  free (sq->items);
166  free (sq->items_inuse);
167  free (sq->items_miss_count);
168 }
169 
170 static inline void *sq_item_add (
171  struct sq *sq,
172  void *item,
173  unsigned int seqid)
174 {
175  char *sq_item;
176  unsigned int sq_position;
177 
178  sq_position = (sq->head + seqid - sq->head_seqid) % sq->size;
179  if (sq_position > sq->pos_max) {
180  sq->pos_max = sq_position;
181  }
182 
183  sq_item = sq->items;
184  sq_item += sq_position * sq->size_per_item;
185  assert(sq->items_inuse[sq_position] == 0);
186  memcpy (sq_item, item, sq->size_per_item);
187  if (seqid == 0) {
188  sq->items_inuse[sq_position] = 1;
189  } else {
190  sq->items_inuse[sq_position] = seqid;
191  }
192  sq->items_miss_count[sq_position] = 0;
193 
194  return (sq_item);
195 }
196 
197 static inline unsigned int sq_item_inuse (
198  const struct sq *sq,
199  unsigned int seq_id) {
200 
201  unsigned int sq_position;
202 
203  /*
204  * We need to say that the seqid is in use if it shouldn't
205  * be here in the first place.
206  * To keep old messages from being inserted.
207  */
208 #ifdef COMPILE_OUT
209  if (seq_id < sq->head_seqid) {
210  fprintf(stderr, "sq_item_inuse: seqid %d, head %d\n",
211  seq_id, sq->head_seqid);
212  return 1;
213  }
214 #endif
215  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
216  return (sq->items_inuse[sq_position] != 0);
217 }
218 
219 static inline unsigned int sq_item_miss_count (
220  const struct sq *sq,
221  unsigned int seq_id)
222 {
223  unsigned int sq_position;
224 
225  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
226  sq->items_miss_count[sq_position]++;
227  return (sq->items_miss_count[sq_position]);
228 }
229 
230 static inline unsigned int sq_size_get (
231  const struct sq *sq)
232 {
233  return sq->size;
234 }
235 
236 static inline unsigned int sq_in_range (
237  const struct sq *sq,
238  unsigned int seq_id)
239 {
240  int res = 1;
241 
242  if (sq->head_seqid > ADJUST_ROLLOVER_POINT) {
243  if (seq_id - ADJUST_ROLLOVER_VALUE <
245 
246  res = 0;
247  }
248  if ((seq_id - ADJUST_ROLLOVER_VALUE) >=
249  ((sq->head_seqid - ADJUST_ROLLOVER_VALUE) + sq->size)) {
250 
251  res = 0;
252  }
253  } else {
254  if (seq_id < sq->head_seqid) {
255  res = 0;
256  }
257  if ((seq_id) >= ((sq->head_seqid) + sq->size)) {
258  res = 0;
259  }
260  }
261  return (res);
262 
263 }
264 
265 static inline unsigned int sq_item_get (
266  const struct sq *sq,
267  unsigned int seq_id,
268  void **sq_item_out)
269 {
270  char *sq_item;
271  unsigned int sq_position;
272 
273  if (seq_id > ADJUST_ROLLOVER_POINT) {
274  assert ((seq_id - ADJUST_ROLLOVER_POINT) <
275  ((sq->head_seqid - ADJUST_ROLLOVER_POINT) + sq->size));
276 
277  sq_position = ((sq->head - ADJUST_ROLLOVER_VALUE) -
278  (sq->head_seqid - ADJUST_ROLLOVER_VALUE) + seq_id) % sq->size;
279  } else {
280  assert (seq_id < (sq->head_seqid + sq->size));
281  sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
282  }
283 //printf ("seqid %x head %x head %x pos %x\n", seq_id, sq->head, sq->head_seqid, sq_position);
284 // sq_position = (sq->head - sq->head_seqid + seq_id) % sq->size;
285 //printf ("sq_position = %x\n", sq_position);
286 //printf ("ITEMGET %d %d %d %d\n", sq_position, sq->head, sq->head_seqid, seq_id);
287  if (sq->items_inuse[sq_position] == 0) {
288  return (ENOENT);
289  }
290  sq_item = sq->items;
291  sq_item += sq_position * sq->size_per_item;
292  *sq_item_out = sq_item;
293  return (0);
294 }
295 
296 static inline void sq_items_release (struct sq *sq, unsigned int seqid)
297 {
298  unsigned int oldhead;
299 
300  oldhead = sq->head;
301 
302  sq->head = (sq->head + seqid - sq->head_seqid + 1) % sq->size;
303  if ((oldhead + seqid - sq->head_seqid + 1) > sq->size) {
304 // printf ("releasing %d for %d\n", oldhead, sq->size - oldhead);
305 // printf ("releasing %d for %d\n", 0, sq->head);
306  memset (&sq->items_inuse[oldhead], 0, (sq->size - oldhead) * sizeof (unsigned int));
307  memset (sq->items_inuse, 0, sq->head * sizeof (unsigned int));
308  } else {
309 // printf ("releasing %d for %d\n", oldhead, seqid - sq->head_seqid + 1);
310  memset (&sq->items_inuse[oldhead], 0,
311  (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
312  memset (&sq->items_miss_count[oldhead], 0,
313  (seqid - sq->head_seqid + 1) * sizeof (unsigned int));
314  }
315  sq->head_seqid = seqid + 1;
316 }
317 
318 #endif /* SORTQUEUE_H_DEFINED */