d762c6dd610c1983daf0e73f3696960f286cdaf9 braney Sat May 6 11:30:17 2017 -0700 make rangeTree functions thread safe. diff --git src/lib/rangeTree.c src/lib/rangeTree.c index 7e8b708..b71cb7e 100644 --- src/lib/rangeTree.c +++ src/lib/rangeTree.c @@ -1,354 +1,353 @@ /* rangeTree - This module is a way of keeping track of * non-overlapping ranges (half-open intervals). It is * based on the self-balancing rbTree code. Use it in * place of a bitmap when the total number of ranges * is significantly smaller than the number of bits would * be. * Beware the several static/global variables which can be * changed by various function calls. */ /* Copyright (C) 2013 The Regents of the University of California * See README in this or parent directory for licensing information. */ #include "common.h" #include "limits.h" #include "localmem.h" #include "obscure.h" #include "rbTree.h" #include "rangeTree.h" int rangeCmp(void *va, void *vb) /* Return -1 if a before b, 0 if a and b overlap, * and 1 if a after b. */ { struct range *a = va; struct range *b = vb; if (a->end <= b->start) return -1; else if (b->end <= a->start) return 1; else return 0; } static void *sumInt(void *a, void *b) /* Local function used by rangeTreeAddValCount, which sums two ints a and b, * referenced by void pointers, returning the result in a */ { int *i = a, *j = b; *i += *j; return a; } struct range *rangeTreeAddVal(struct rbTree *tree, int start, int end, void *val, void *(*mergeVals)(void *existingVal, void *newVal) ) /* Add range to tree, merging with existing ranges if need be. * If this is a new range, set the value to this val. * If there are existing items for this range, and if mergeVals function is not null, * apply mergeVals to the existing values and this new val, storing the result as the val * for this range (see rangeTreeAddValCount() and rangeTreeAddValList() below for examples). */ { struct range *r, *existing; r = lmAlloc(tree->lm, sizeof(*r)); /* alloc new zeroed range */ r->start = start; r->end = end; r->val = val; while ((existing = rbTreeRemove(tree, r)) != NULL) { r->start = min(r->start, existing->start); r->end = max(r->end, existing->end); if (mergeVals) r->val = mergeVals(existing->val, r->val); } rbTreeAdd(tree, r); return r; } struct range *rangeTreeAdd(struct rbTree *tree, int start, int end) /* Add range to tree, merging with existing ranges if need be. */ { return rangeTreeAddVal(tree, start, end, NULL, NULL); } struct range *rangeTreeAddValCount(struct rbTree *tree, int start, int end) /* Add range to tree, merging with existing ranges if need be. * Set range val to count of elements in the range. Counts are pointers to * ints allocated in tree localmem */ { int *a = lmAlloc(tree->lm, sizeof(*a)); /* keep the count in localmem */ *a = 1; return rangeTreeAddVal(tree, start, end, (void *)a, sumInt); } struct range *rangeTreeAddValList(struct rbTree *tree, int start, int end, void *val) /* Add range to tree, merging with existing ranges if need be. * Add val to the list of values (if any) in each range. * val must be valid argument to slCat (ie, be a struct with a 'next' pointer as its first member) */ { return rangeTreeAddVal(tree, start, end, val, slCat); } void rangeTreeAddToCoverageDepth(struct rbTree *tree, int start, int end) /* Add area from start to end to a tree that is being built up to store the * depth of coverage. Recover coverage back out by looking at ptToInt(range->val) * on tree elements. */ { struct range q; q.start = start; q.end = end; struct range *r, *existing = rbTreeFind(tree, &q); if (existing == NULL) { lmAllocVar(tree->lm, r); r->start = start; r->end = end; r->val = intToPt(1); rbTreeAdd(tree, r); } else { if (existing->start <= start && existing->end >= end) /* The existing one completely encompasses us */ { /* Make a new section for the bit before start. */ if (existing->start < start) { lmAllocVar(tree->lm, r); r->start = existing->start; r->end = start; r->val = existing->val; existing->start = start; rbTreeAdd(tree, r); } /* Make a new section for the bit after end. */ if (existing->end > end) { lmAllocVar(tree->lm, r); r->start = end; r->end = existing->end; r->val = existing->val; existing->end = end; rbTreeAdd(tree, r); } /* Increment existing section in overlapping area. */ existing->val = (char *)(existing->val) + 1; } else /* In general case fetch list of regions that overlap us. Remaining cases to handle are: r >> e rrrrrrrrrrrrrrrrrrrr eeeeeeeeee e < r rrrrrrrrrrrrrrr eeeeeeeeeeee r < e rrrrrrrrrrrr eeeeeeeeeeeee */ { struct range *existingList = rangeTreeAllOverlapping(tree, start, end); #ifdef DEBUG /* Make sure that list is really sorted for debugging... */ int lastStart = existingList->start; for (r = existingList; r != NULL; r = r->next) { int start = r->start; if (start < lastStart) internalErr(); } #endif /* DEBUG */ int s = start, e = end; for (existing = existingList; existing != NULL; existing = existing->next) { /* Deal with start of new range that comes before existing */ if (s < existing->start) { lmAllocVar(tree->lm, r); r->start = s; r->end = existing->start; r->val = intToPt(1); s = existing->start; rbTreeAdd(tree, r); } else if (s > existing->start) { lmAllocVar(tree->lm, r); r->start = existing->start; r->end = s; r->val = existing->val; existing->start = s; rbTreeAdd(tree, r); } existing->val = (char *)(existing->val) + 1; s = existing->end; } if (s < e) /* Deal with end of new range that doesn't overlap with anything. */ { lmAllocVar(tree->lm, r); r->start = s; r->end = e; r->val = intToPt(1); rbTreeAdd(tree, r); } } } } boolean rangeTreeOverlaps(struct rbTree *tree, int start, int end) /* Return TRUE if start-end overlaps anything in tree */ { struct range tempR; tempR.start = start; tempR.end = end; tempR.val = NULL; return rbTreeFind(tree, &tempR) != NULL; } -static struct range *rangeList; - -static void rangeListAdd(void *v) +static void rangeListAdd(void *v, void *context) /* Callback to add item to range list. */ { struct range *r = v; -slAddHead(&rangeList, r); +struct range **list = (struct range **)context; +slAddHead(list, r); } struct range *rangeTreeList(struct rbTree *tree) /* Return list of all ranges in tree in order. Not thread safe. * No need to free this when done, memory is local to tree. */ { -rangeList = NULL; -rbTreeTraverse(tree, rangeListAdd); +struct range *rangeList = NULL; +rbTreeTraverseWithContext(tree, rangeListAdd, &rangeList); slReverse(&rangeList); return rangeList; } struct range *rangeTreeFindEnclosing(struct rbTree *tree, int start, int end) /* Find item in range tree that encloses range between start and end * if there is any such item. */ { struct range tempR, *r; tempR.start = start; tempR.end = end; r = rbTreeFind(tree, &tempR); if (r != NULL && r->start <= start && r->end >= end) { r->next = NULL; /* this can be set by previous calls to the List functions */ return r; } return NULL; } struct range *rangeTreeAllOverlapping(struct rbTree *tree, int start, int end) /* Return list of all items in range tree that overlap interval start-end. * Do not free this list, it is owned by tree. However it is only good until * next call to rangeTreeFindInRange or rangeTreeList. Not thread safe. */ { struct range tempR; tempR.start = start; tempR.end = end; -rangeList = NULL; -rbTreeTraverseRange(tree, &tempR, &tempR, rangeListAdd); +struct range *rangeList = NULL; +rbTreeTraverseRangeWithContext(tree, &tempR, &tempR, rangeListAdd, &rangeList); slReverse(&rangeList); return rangeList; } struct range *rangeTreeMaxOverlapping(struct rbTree *tree, int start, int end) /* Return item that overlaps most with start-end. Not thread safe. Trashes list used * by rangeTreeAllOverlapping. */ { struct range *range, *best = NULL; int bestOverlap = 0; for (range = rangeTreeAllOverlapping(tree, start, end); range != NULL; range = range->next) { int overlap = rangeIntersection(range->start, range->end, start, end); if (overlap > bestOverlap) { bestOverlap = overlap; best = range; } } if (best) best->next = NULL; /* could be set by calls to List functions */ return best; } /* A couple of variables used to calculate total overlap. */ static int totalOverlap; static int overlapStart, overlapEnd; static void addOverlap(void *v) /* Callback to add item to range list. */ { struct range *r = v; totalOverlap += positiveRangeIntersection(r->start, r->end, overlapStart, overlapEnd); } int rangeTreeOverlapSize(struct rbTree *tree, int start, int end) /* Return the total size of intersection between interval * from start to end, and items in range tree. Sadly not * thread-safe. * On 32 bit machines be careful not to overflow * range of start, end or total size return value. */ { struct range tempR; tempR.start = overlapStart = start; tempR.end = overlapEnd = end; totalOverlap = 0; rbTreeTraverseRange(tree, &tempR, &tempR, addOverlap); return totalOverlap; } int rangeTreeOverlapTotalSize(struct rbTree *tree) /* Return the total size of all ranges in range tree. * Sadly not thread-safe. * On 32 bit machines be careful not to overflow * range of start, end or total size return value. */ { return rangeTreeOverlapSize(tree, INT_MIN, INT_MAX); } void rangeTreeSumRangeCallback(void *item, void *context) /* This is a callback for rbTreeTraverse with context. It just adds up * end-start */ { struct range *range = item; long long *pSum = context; *pSum += range->end - range->start; } long long rangeTreeSumRanges(struct rbTree *tree) /* Return sum of end-start of all items. */ { long long sum = 0; rbTreeTraverseWithContext(tree, rangeTreeSumRangeCallback, &sum); return sum; } struct rbTree *rangeTreeNew() /* Create a new, empty, rangeTree. */ { return rbTreeNew(rangeCmp); } struct rbTree *rangeTreeNewDetailed(struct lm *lm, struct rbTreeNode *stack[128]) /* Allocate rangeTree on an existing local memory & stack. This is for cases * where you want a lot of trees, and don't want the overhead for each one. * Note, to clean these up, just do freez(&rbTree) rather than rbFreeTree(&rbTree). */ { return rbTreeNewDetailed(rangeCmp, lm, stack); }