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