1 /*===========================================================================
2 *
3 * PUBLIC DOMAIN NOTICE
4 * National Center for Biotechnology Information
5 *
6 * This software/database is a "United States Government Work" under the
7 * terms of the United States Copyright Act. It was written as part of
8 * the author's official duties as a United States Government employee and
9 * thus cannot be copyrighted. This software/database is freely available
10 * to the public for use. The National Library of Medicine and the U.S.
11 * Government have not placed any restriction on its use or reproduction.
12 *
13 * Although all reasonable efforts have been taken to ensure the accuracy
14 * and reliability of the software and data, the NLM and the U.S.
15 * Government do not and cannot warrant the performance or results that
16 * may be obtained by using this software or data. The NLM and the U.S.
17 * Government disclaim all warranties, express or implied, including
18 * warranties of performance, merchantability or fitness for any particular
19 * purpose.
20 *
21 * Please cite the author in any work or product based on this material.
22 *
23 * ===========================================================================
24 *
25 */
26
27 #include <stdlib.h>
28 #include <string.h>
29 #include <assert.h>
30 #include "range-list.h"
31 #include <atomic.h>
32 #include <kproc/lock.h>
33
34 /* Note: This synchronization is very specific to this use.
35 * Give a good thought or two before using it somewhere else.
36 * In particular, there is only one writer, and it needs to
37 * synchronize very rarely, but the readers happen many
38 * tens of thousands of times while the writer is running.
39 * Furthermore, the readers continue to access the structure
40 * long after the writer has finished and there's no longer
41 * any possibility of a race condition.
42 */
43 struct Sync {
44 /* low order bit indicates that a writer is waiting (or active)
45 * remainder of bits is the count of active readers
46 */
47 KLock *mutex;
48 atomic_t counter;
49 };
50
syncReadLock(Sync * const sync)51 static void syncReadLock(Sync *const sync)
52 {
53 if ((atomic_read_and_add_even(&sync->counter, 2) & 1) != 0) {
54 /* a writer is waiting or active */
55 KLockAcquire(sync->mutex);
56 atomic_add(&sync->counter, 2);
57 KLockUnlock(sync->mutex);
58 }
59 }
60
syncReadUnlock(Sync * const sync)61 static void syncReadUnlock(Sync *const sync)
62 {
63 atomic_add(&sync->counter, -2);
64 }
65
syncWriteLock(Sync * const sync)66 static void syncWriteLock(Sync *const sync)
67 {
68 assert((atomic_read(&sync->counter) & 1) == 0); /* there is only one writer */
69
70 atomic_inc(&sync->counter); /* tell readers to wait */
71 KLockAcquire(sync->mutex);
72 while (atomic_read(&sync->counter) != 1) /* wait for readers to finish */
73 ;
74 }
75
syncWriteUnlock(Sync * const sync)76 static void syncWriteUnlock(Sync *const sync)
77 {
78 atomic_dec(&sync->counter);
79 KLockUnlock(sync->mutex);
80 }
81
readerStart(RangeList const volatile * const list)82 static RangeList const *readerStart(RangeList const volatile *const list)
83 {
84 syncReadLock(list->sync);
85
86 // list is not volatile now
87 return (RangeList const *)list;
88 }
89
readerDone(RangeList const * const list)90 static RangeList const volatile *readerDone(RangeList const *const list)
91 {
92 syncReadUnlock(list->sync);
93
94 // list is volatile again
95 return (RangeList const volatile *)list;
96 }
97
98 /// Note: One the writer's side, the list is not volatile since there are no changes being made by other threads
99
writerStart(RangeList * const list)100 static void writerStart(RangeList *const list)
101 {
102 syncWriteLock(list->sync);
103 }
104
writerDone(RangeList * const list)105 static void writerDone(RangeList *const list)
106 {
107 syncWriteUnlock(list->sync);
108 }
109
updateRanges(RangeList * const list,Range * const ranges,unsigned const allocated)110 static void updateRanges( RangeList *const list
111 , Range *const ranges
112 , unsigned const allocated)
113 {
114 writerStart(list);
115 list->ranges = ranges;
116 list->allocated = allocated;
117 writerDone(list);
118 }
119
intersectRanges(Range * result,Range const * a,Range const * b)120 void intersectRanges(Range *result, Range const *a, Range const *b)
121 {
122 unsigned const s = a->start < b->start ? b->start : a->start;
123 unsigned const e = a->end < b->end ? a->end : b->end;
124 result->start = s;
125 result->end = s < e ? e : s;
126 }
127
intersectRangeList(RangeList const * list,Range const ** begin,Range const ** end,Range const * query)128 void intersectRangeList(RangeList const *list, Range const **begin, Range const **end, Range const *query)
129 {
130 assert(begin != NULL);
131 assert(end != NULL);
132 assert(query != NULL);
133 assert(list != NULL);
134
135 *end = &list->ranges[list->count];
136 *begin = *end;
137 if (query->start < query->end && list->count > 0) {
138 unsigned f = 0;
139 unsigned e = list->count;
140
141 while (f < e) {
142 unsigned const m = f + (e - f) / 2;
143 Range const *const M = &list->ranges[m];
144 if (M->start < query->end)
145 f = m + 1;
146 else
147 e = m;
148 }
149 *end = &list->ranges[f];
150
151 f = 0;
152 while (f < e) {
153 unsigned const m = f + (e - f) / 2;
154 Range const *const M = &list->ranges[m];
155 if (M->end <= query->start)
156 f = m + 1;
157 else
158 e = m;
159 }
160 *begin = &list->ranges[f];
161 }
162 }
163
164 /// This is the main reader function, and a read lock is maintained throughout.
165 /// The read lock does not prevent new elements from being appended,
166 /// it only prevents reallocation of the list (which would invalidate the list pointer).
167 /// There is an assertion is that readers can never be interested in elements
168 /// that might get appended during the duration of this call.
withIntersectRangeList_1(RangeList const volatile * const vol,Range const * const query,IntersectRangeListCallback const callback,void * const data)169 static void withIntersectRangeList_1( RangeList const volatile *const vol
170 , Range const *const query
171 , IntersectRangeListCallback const callback
172 , void *const data)
173 {
174 if (vol->sync) {
175 RangeList const *const list = readerStart(vol);
176 Range const *ranges = list->ranges; ///< this pointer will not change while the read lock is held
177 unsigned const count = list->count; ///< this can change, but it can only increase
178 unsigned f = 0;
179 unsigned e = count;
180
181 while (f < e) {
182 unsigned const m = f + (e - f) / 2;
183 Range const *const M = &ranges[m];
184 if (M->end <= query->start)
185 f = m + 1;
186 else
187 e = m;
188 }
189 while (f < count) {
190 Range intersected;
191
192 intersectRanges(&intersected, &ranges[f++], query);
193 if (intersected.end == intersected.start)
194 break;
195
196 callback(data, &intersected);
197 }
198 (void)readerDone(list);
199 }
200 }
201
202
withIntersectRangeList(RangeList const * list,Range const * query,IntersectRangeListCallback callback,void * data)203 void withIntersectRangeList(RangeList const *list, Range const *query, IntersectRangeListCallback callback, void *data)
204 {
205 withIntersectRangeList_1((RangeList const volatile *)list, query, callback, data);
206 }
207
grow(RangeList * const list)208 static RangeList *grow(RangeList *const list)
209 {
210 if (list->sync == NULL) {
211 Sync *sync = calloc(1, sizeof(*sync));
212 if (sync) {
213 rc_t const rc = KLockMake(&sync->mutex);
214 if (rc == 0)
215 list->sync = sync;
216 else {
217 free(sync);
218 return NULL;
219 }
220 }
221 else
222 return NULL;
223 }
224
225 if (list->count == list->allocated) {
226 void *const old = list->ranges;
227 unsigned const allocated = list->allocated;
228 unsigned const new_allocated = allocated == 0 ? 16 : (allocated * 2);
229 void *tmp = calloc(new_allocated, sizeof(list->ranges[0]));
230 if (tmp == NULL)
231 return NULL;
232 memmove(tmp, old, allocated * sizeof(list->ranges[0]));
233
234 updateRanges(list, tmp, new_allocated);
235 free(old);
236 }
237 return list;
238 }
239
insert(RangeList * const list,unsigned const at)240 static void insert(RangeList *const list, unsigned const at)
241 {
242 unsigned i = list->count;
243 while (i > at) {
244 list->ranges[i] = list->ranges[i - 1];
245 --i;
246 }
247 ++list->count;
248 }
249
remove(RangeList * const list,unsigned at)250 static void remove(RangeList *const list, unsigned at)
251 {
252 while (at + 1 < list->count) {
253 list->ranges[at] = list->ranges[at + 1];
254 ++at;
255 }
256 --list->count;
257 }
258
259 /* merge [at] and [at + 1] */
collapse(RangeList * const list,unsigned const at)260 static void collapse(RangeList *const list, unsigned const at)
261 {
262 if (at + 1 < list->count && list->ranges[at].end == list->ranges[at + 1].start) {
263 unsigned const start = list->ranges[at].start;
264 remove(list, at);
265 list->ranges[at].start = start;
266 }
267 }
268
appendRange(RangeList * list,Range const * newValue)269 Range *appendRange(RangeList *list, Range const *newValue)
270 {
271 if (grow(list) != NULL) {
272 Range *nr = &list->ranges[list->count];
273
274 if (newValue)
275 *nr = *newValue;
276 list->last = list->count;
277 ++list->count;
278
279 return nr;
280 }
281 return NULL;
282 }
283
extendRangeList_1(RangeList * const list,unsigned const position)284 static RangeList *extendRangeList_1(RangeList *const list, unsigned const position)
285 {
286 if (list->count > 0) {
287 Range const lastRange = list->ranges[list->last];
288
289 if (lastRange.end == position) {
290 list->ranges[list->last].end = position + 1;
291 collapse(list, list->last);
292 return list;
293 }
294 if (lastRange.start <= position && position < lastRange.end)
295 return list;
296 if (position < list->ranges[list->count - 1].end) {
297 unsigned f = 0;
298 unsigned e = list->count;
299
300 while (f < e) {
301 unsigned const m = f + (e - f) / 2;
302 Range const *const M = &list->ranges[m];
303 if (M->end < position)
304 f = m + 1;
305 else
306 e = m;
307 }
308 if (f < list->count) {
309 if (position < list->ranges[f].start) {
310 // insert new range before f
311 if (!grow(list))
312 return NULL;
313 insert(list, f);
314 list->ranges[f].start = position;
315 list->ranges[f].end = position + 1;
316 list->last = f;
317 return list;
318 }
319 if (position > list->ranges[f].end) {
320 // insert new range after f
321 if (!grow(list))
322 return NULL;
323 insert(list, f + 1);
324 list->ranges[f + 1].start = position;
325 list->ranges[f + 1].end = position + 1;
326 list->last = f + 1;
327 return list;
328 }
329 if (position == list->ranges[f].end) {
330 list->last = f;
331 return extendRangeList_1(list, position);
332 }
333 }
334 }
335 }
336 {
337 Range nr;
338 nr.end = (nr.start = position) + 1;
339 if (appendRange(list, &nr))
340 return list;
341 }
342 return NULL;
343 }
344
extendRangeList(RangeList * list,unsigned position)345 RangeList *extendRangeList(RangeList *list, unsigned position)
346 {
347 return extendRangeList_1(list, position);
348 }
349
RangeListFree(RangeList * list)350 void RangeListFree(RangeList *list)
351 {
352 free(list->ranges);
353 }
354
copyRangeList(RangeList * list)355 RangeList const *copyRangeList(RangeList *list)
356 {
357 struct {
358 RangeList list;
359 Range array[1];
360 } *temp = NULL;
361 size_t const alloc = (uint8_t const *)&temp->array[list->count] - (uint8_t const *)temp;
362
363 temp = malloc(alloc);
364 assert(temp != NULL);
365 if (temp) {
366 {
367 unsigned i;
368 for (i = 0; i < list->count; ++i)
369 temp->array[i] = list->ranges[i];
370 }
371 temp->list = *list;
372 temp->list.ranges = temp->array;
373 temp->list.last = 0;
374
375 return &temp->list;
376 }
377 return NULL;
378 }
379
checkRangeList(RangeList const * list)380 int checkRangeList(RangeList const *list)
381 {
382 unsigned i = 0;
383 if (i < list->count) {
384 Range r = list->ranges[i++];
385
386 assert(r.start < r.end);
387 if (!(r.start < r.end)) return !!0;
388 while (i < list->count) {
389 Range const p = r;
390
391 r = list->ranges[i++];
392
393 assert(r.start < r.end);
394 if (!(r.start < r.end)) return !!0;
395 assert(p.end < r.start);
396 if (!(p.end < r.start)) return !!0;
397 }
398 }
399 return !0;
400 }
401