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 /* ********* NOTE!!! ********* */
28 /*                             */
29 /* CONCURRENT USE IS ONLY SAFE */
30 /* IN EXACTLY THE WAY THAT     */
31 /* refseq.c USES THIS.         */
32 /*                             */
33 /* That is, inserts only occur */
34 /* at the end and are outside  */
35 /* the region that another     */
36 /* thread would be using.      */
37 /*                             */
38 /* There is no provision for   */
39 /* synchronizing multiple      */
40 /* writers.                    */
41 /*                             */
42 /* ********* NOTE!!! ********* */
43 
44 typedef struct Range Range;
45 typedef struct RangeList RangeList;
46 typedef struct Sync Sync;
47 
48 /**
49  * @note start must be less than or equal to end
50  */
51 struct Range {
52     unsigned start, end;
53 };
54 
55 /**
56  * @brief An ordered list of Range, memset(0) to initialize.
57  * @note ranges do not overlap
58  */
59 struct RangeList {
60     Range *ranges;
61     Sync *sync;
62     unsigned count;
63     unsigned allocated; ///< used only by the writer
64     unsigned last;      ///< used only by the writer
65 };
66 
67 typedef void (*IntersectRangeListCallback)(void *data, Range const *intersectingRange);
68 
69 /**
70  * @brief intersect the query range with the ranges in the list and callback with the intersecting ranges
71  * @note thread safe
72  *
73  * This is the main function used by a reader.
74  *
75  * There is an unchecked assertion is that readers have checked that
76  * their query can not possibly overlap the end of the list before they got on this code path.
77  */
78 void withIntersectRangeList(RangeList const *list, Range const *query, IntersectRangeListCallback callback, void *data);
79 
80 /**
81  * @brief Extend the last range in the list or insert a new range if position is not contiguous
82  * @note thread safe
83  *
84  * This is the main function used by a writer.
85  */
86 RangeList *extendRangeList(RangeList *list, unsigned position);
87 
88 /**
89  * @brief performs a consistency check
90  */
91 int checkRangeList(RangeList const *);
92 
93 /**
94  * @brief free the memory for the ranges and any synchronization
95  * @param list this pointer is not freed
96  * @note *NOT* thread safe, only call after any writer thread has exited
97  */
98 void RangeListFree(RangeList *list);
99 
100 /**
101  * @brief intersect two ranges
102  * @note not used directly by refseq.c
103  */
104 void intersectRanges(Range *result, Range const *a, Range const *b);
105 
106 /**
107  * @brief add a range to the end of the list
108  * @note not used directly by refseq.c and not thread safe in general
109  */
110 Range *appendRange(RangeList *list, Range const *newValue);
111 
112 /**
113  * @brief intersect the query range with the ranges in the list
114  * @note not used by refseq.c and not thread safe or easy to use, exists for testing
115  */
116 void intersectRangeList(RangeList const *list, Range const **begin, Range const **end, Range const *query);
117 
118 /**
119  * @note not used by refseq.c and not thread safe or easy to use, exists for testing, don't use otherwise
120  */
121 RangeList const *copyRangeList(RangeList *list);
122