inc/binRange.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	binElement
struct	binKeeper
struct	binKeeperCookie
Defines
#define	BINRANGE_MAXEND_512M   (512*1024*1024)
#define	_binOffsetOldToExtended   4681
Functions
int	binLevelsExtended ()
int	binLevels ()
int	binFirstShift ()
int	binNextShift ()
int	binOffsetExtended (int level)
int	binOffset (int level)
int	binFromRange (int start, int end)
int	binElementCmpStart (const void *va, const void *vb)
binKeeper *	binKeeperNew (int minPos, int maxPos)
void	binKeeperFree (struct binKeeper **pBk)
void	binKeeperAdd (struct binKeeper *bk, int start, int end, void *val)
void	binKeeperRemove (struct binKeeper *bk, int start, int end, void *val)
binElement *	binKeeperFind (struct binKeeper *bk, int start, int end)
binElement *	binKeeperFindSorted (struct binKeeper *bk, int start, int end)
binElement *	binKeeperFindAll (struct binKeeper *bk)
boolean	binKeeperAnyOverlap (struct binKeeper *bk, int start, int end)
void	binKeeperReplaceVal (struct binKeeper *bk, int start, int end, void *oldVal, void *newVal)
binElement *	binKeeperFindLowest (struct binKeeper *bk, int start, int end)
binKeeperCookie	binKeeperFirst (struct binKeeper *bk)
binElement *	binKeeperNext (struct binKeeperCookie *cookie)

---

Define Documentation

#define _binOffsetOldToExtended   4681

Definition at line 17 of file binRange.h.

Referenced by binFromRangeExtended(), and binOffsetExtended().

#define BINRANGE_MAXEND_512M   (512*1024*1024)

Definition at line 16 of file binRange.h.

Referenced by binFromRange().

---

Function Documentation

int binElementCmpStart	(	const void *	va,
		const void *	vb
	)

Definition at line 189 of file binRange.c.

References binElement::start.

Referenced by binKeeperFindSorted().

{
const struct binElement *a = *((struct binElement **)va);
const struct binElement *b = *((struct binElement **)vb);
return a->start - b->start;
}

Here is the caller graph for this function:

int binFirstShift

(

)

Definition at line 40 of file binRange.c.

References _binFirstShift.

{
return _binFirstShift;
}

int binFromRange	(	int	start,
		int	end
	)

Definition at line 111 of file binRange.c.

References binFromRangeExtended(), binFromRangeStandard(), and BINRANGE_MAXEND_512M.

{
if (end <= BINRANGE_MAXEND_512M)
    return binFromRangeStandard(start, end);
else
    return binFromRangeExtended(start, end);
}

Here is the call graph for this function:

void binKeeperAdd	(	struct binKeeper *	bk,
		int	start,
		int	end,
		void *	val
	)

Definition at line 172 of file binRange.c.

References AllocVar, binFromRangeBinKeeperExtended(), binKeeper::binLists, binElement::end, errAbort(), binKeeper::maxPos, binKeeper::minPos, slAddHead, binElement::start, and binElement::val.

Referenced by mergeAdd(), and readPslToBinKeeper().

{
int bin;
struct binElement *el;
if (start < bk->minPos || end > bk->maxPos || start > end)
    errAbort("(%d %d) out of range (%d %d) in binKeeperAdd", 
        start, end, bk->minPos, bk->maxPos);
bin = binFromRangeBinKeeperExtended(start, end);
assert(bin < bk->binCount);
AllocVar(el);
el->start = start;
el->end = end;
el->val = val;
slAddHead(&bk->binLists[bin], el);
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean binKeeperAnyOverlap	(	struct binKeeper *	bk,
		int	start,
		int	end
	)

Definition at line 230 of file binRange.c.

References _binFirstShift, ArraySize, binKeeper::binLists, binOffsetsExtended, binElement::end, FALSE, binKeeper::maxPos, binKeeper::minPos, binElement::next, rangeIntersection(), binElement::start, and TRUE.

{
struct binElement *el;
int startBin, endBin;
int i,j;

if (start < bk->minPos) start = bk->minPos;
if (end > bk->maxPos) end = bk->maxPos;
if (start >= end) return FALSE;
startBin = (start>>_binFirstShift);
endBin = ((end-1)>>_binFirstShift);
for (i=0; i<ArraySize(binOffsetsExtended); ++i)
    {
    int offset = binOffsetsExtended[i];
    for (j=startBin+offset; j<=endBin+offset; ++j)
        {
        for (el=bk->binLists[j]; el != NULL; el = el->next)
            {
            if (rangeIntersection(el->start, el->end, start, end) > 0)
                {
                return TRUE;
                }
            }
        }
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
return FALSE;
}

Here is the call graph for this function:

struct binElement* binKeeperFind	(	struct binKeeper *	bk,
		int	start,
		int	end
	)			[read]

Definition at line 197 of file binRange.c.

References _binFirstShift, ArraySize, binKeeper::binLists, binOffsetsExtended, CloneVar, binKeeper::maxPos, binKeeper::minPos, binElement::next, rangeIntersection(), and slAddHead.

Referenced by binKeeperFindSorted(), and mergeAdd().

{
struct binElement *list = NULL, *newEl, *el;
int startBin, endBin;
int i,j;

if (start < bk->minPos) start = bk->minPos;
if (end > bk->maxPos) end = bk->maxPos;
if (start >= end) return NULL;
startBin = (start>>_binFirstShift);
endBin = ((end-1)>>_binFirstShift);
for (i=0; i<ArraySize(binOffsetsExtended); ++i)
    {
    int offset = binOffsetsExtended[i];
    for (j=startBin+offset; j<=endBin+offset; ++j)
        {
        for (el=bk->binLists[j]; el != NULL; el = el->next)
            {
            if (rangeIntersection(el->start, el->end, start, end) > 0)
                {
                newEl = CloneVar(el);
                slAddHead(&list, newEl);
                }
            }
        }
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
return list;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct binElement* binKeeperFindAll

(

struct binKeeper *

bk

)

[read]

Definition at line 304 of file binRange.c.

References binKeeperFindSorted(), binKeeper::maxPos, and binKeeper::minPos.

Referenced by pcrClumps().

{
return binKeeperFindSorted(bk, bk->minPos, bk->maxPos);
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct binElement* binKeeperFindLowest	(	struct binKeeper *	bk,
		int	start,
		int	end
	)			[read]

Definition at line 310 of file binRange.c.

References _binFirstShift, ArraySize, binKeeper::binLists, binOffsetsExtended, binElement::end, FALSE, binElement::next, rangeIntersection(), binElement::start, and TRUE.

{
struct binElement *first = NULL, *el;
int startBin = (start>>_binFirstShift), endBin = ((end-1)>>_binFirstShift);
int i,j;

/* Search the possible range of bins at each level, looking for lowest.  Once
 * an overlaping range is found at a level, continue with next level, however
 * must search an entire bin as they are not ordered. */
for (i=0; i<ArraySize(binOffsetsExtended); ++i)
    {
    int offset = binOffsetsExtended[i];
    boolean foundOne = FALSE;
    for (j=startBin+offset; (j<=endBin+offset) && (!foundOne); ++j)
        {
        for (el=bk->binLists[j]; el != NULL; el = el->next)
            {
            if ((rangeIntersection(el->start, el->end, start, end) > 0)
                && ((first == NULL) || (el->start < first->start)
                    || ((el->start == first->start)
                        && (el->end < first->end))))
                {
                first = el;
                foundOne = TRUE;
                }
            }
        }
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
return first;
}

Here is the call graph for this function:

struct binElement* binKeeperFindSorted	(	struct binKeeper *	bk,
		int	start,
		int	end
	)			[read]

Definition at line 296 of file binRange.c.

References binElementCmpStart(), binKeeperFind(), and slSort().

Referenced by binKeeperFindAll().

{
struct binElement *list = binKeeperFind(bk, start, end);
slSort(&list, binElementCmpStart);
return list;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct binKeeperCookie binKeeperFirst

(

struct binKeeper *

bk

)

[read]

Definition at line 366 of file binRange.c.

References binKeeper::binLists, and binKeeperCookie::bk.

{
struct binKeeperCookie cookie;
cookie.bk = bk;
cookie.blIdx = 0;
cookie.nextBel = bk->binLists[0];
return cookie;
}

void binKeeperFree

(

struct binKeeper **

pBk

)

Definition at line 158 of file binRange.c.

References binKeeper::binCount, binKeeper::binLists, freeMem(), freez(), and slFreeList().

Referenced by pcrClumps().

{
struct binKeeper *bk = *pBk;
if (bk != NULL)
    {
    int i;
    for (i=0; i<bk->binCount; ++i)
        slFreeList(&bk->binLists[i]);
    freeMem(bk->binLists);
    freez(pBk);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct binKeeper* binKeeperNew	(	int	minPos,
		int	maxPos
	)			[read]

Definition at line 141 of file binRange.c.

References AllocArray, AllocVar, binKeeper::binCount, binFromRangeBinKeeperExtended(), binKeeper::binLists, errAbort(), binKeeper::maxPos, and binKeeper::minPos.

Referenced by pcrClumps(), and readPslToBinKeeper().

{
int binCount;
struct binKeeper *bk;
if (minPos < 0 || maxPos < 0 || minPos > maxPos)
    errAbort("bad range %d,%d in binKeeperNew", minPos, maxPos);

binCount = binFromRangeBinKeeperExtended(maxPos-1, maxPos) + 1;
AllocVar(bk);
bk->minPos = minPos;
bk->maxPos = maxPos;
bk->binCount = binCount;
AllocArray(bk->binLists, binCount);
return bk;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct binElement* binKeeperNext

(

struct binKeeperCookie *

cookie

)

[read]

Definition at line 378 of file binRange.c.

References binKeeper::binCount, binKeeper::binLists, binKeeperCookie::bk, binKeeperCookie::blIdx, binElement::next, and binKeeperCookie::nextBel.

{
/* if we don't have a next, move down bin list until we find one */
while ((cookie->nextBel == NULL)
       && (++cookie->blIdx < cookie->bk->binCount))
    cookie->nextBel = cookie->bk->binLists[cookie->blIdx];
if (cookie->blIdx >= cookie->bk->binCount)
    return NULL;  /* no more */
else
    {
    struct binElement* bel = cookie->nextBel;
    cookie->nextBel = cookie->nextBel->next;
    return bel;
    }
}

void binKeeperRemove	(	struct binKeeper *	bk,
		int	start,
		int	end,
		void *	val
	)

Definition at line 345 of file binRange.c.

References binFromRangeBinKeeperExtended(), binKeeper::binLists, freeMem(), binElement::next, and slAddHead.

Referenced by mergeAdd().

{
int bin = binFromRangeBinKeeperExtended(start, end);
struct binElement **pList = &bk->binLists[bin], *newList = NULL, *el, *next;
for (el = *pList; el != NULL; el = next)
    {
    next = el->next;
    if (el->val == val && el->start == start && el->end == end)
        {
        freeMem(el);
        }
    else
        {
        slAddHead(&newList, el);
        }
    }
slReverse(&newList);
*pList = newList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void binKeeperReplaceVal	(	struct binKeeper *	bk,
		int	start,
		int	end,
		void *	oldVal,
		void *	newVal
	)

Definition at line 261 of file binRange.c.

References _binFirstShift, ArraySize, binKeeper::binLists, binOffsetsExtended, binElement::end, binKeeper::maxPos, binKeeper::minPos, binElement::next, rangeIntersection(), binElement::start, and binElement::val.

{
struct binElement *el;
int startBin, endBin;
int i,j;

if (start < bk->minPos) start = bk->minPos;
if (end > bk->maxPos) end = bk->maxPos;
if (start >= end) return;
startBin = (start>>_binFirstShift);
endBin = ((end-1)>>_binFirstShift);
for (i=0; i<ArraySize(binOffsetsExtended); ++i)
    {
    int offset = binOffsetsExtended[i];
    for (j=startBin+offset; j<=endBin+offset; ++j)
        {
        for (el=bk->binLists[j]; el != NULL; el = el->next)
            {
            if (rangeIntersection(el->start, el->end, start, end) > 0)
                {
                if (el->val == oldVal)
                    {
                    el->val = newVal;
                    }
                }
            }
        }
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
}

Here is the call graph for this function:

int binLevels

(

)

Definition at line 34 of file binRange.c.

References ArraySize, and binOffsets.

{
return ArraySize(binOffsets);
}

int binLevelsExtended

(

)

Definition at line 28 of file binRange.c.

References ArraySize, and binOffsetsExtended.

{
return ArraySize(binOffsetsExtended);
}

int binNextShift

(

)

Definition at line 46 of file binRange.c.

References _binNextShift.

{
return _binNextShift;
}

int binOffset

(

int

level

)

Definition at line 59 of file binRange.c.

References ArraySize, and binOffsets.

{
assert(level >= 0 && level < ArraySize(binOffsets));
return binOffsets[level];
}

int binOffsetExtended

(

int

level

)

Definition at line 52 of file binRange.c.

References _binOffsetOldToExtended, ArraySize, and binOffsetsExtended.

{
assert(level >= 0 && level < ArraySize(binOffsetsExtended));
return binOffsetsExtended[level] + _binOffsetOldToExtended;
}

---