Functions
recom.c File Reference

Functions used for recomputation of vectors (only a fraction of LH vectors stored in RAM) More...

Functions

void protectNode (recompVectors *rvec, int nodenum, int mxtips)
 Locks node nodenum to force it remains availably in memory. More...
 
static boolean isNodePinned (recompVectors *rvec, int nodenum, int mxtips)
 Checks if nodenum is currently pinned (available in RAM) More...
 
boolean needsRecomp (boolean recompute, recompVectors *rvec, nodeptr p, int mxtips)
 Checks if the likelihood entries at node p should be updated. More...
 
void allocRecompVectorsInfo (pllInstance *tr)
 Allocates memory for recomputation structure. More...
 
static int findUnpinnableSlotByCost (recompVectors *v, int mxtips)
 Find the slot id with the minimum cost to be recomputed. More...
 
static void unpinAtomicSlot (recompVectors *v, int slot, int mxtips)
 
static int findUnpinnableSlot (recompVectors *v, int mxtips)
 Finds the cheapest slot and unpins it. More...
 
static int findFreeSlot (recompVectors *v, int mxtips)
 Finds a free slot. More...
 
static void pinAtomicNode (recompVectors *v, int nodenum, int slot, int mxtips)
 Pins node nodenum to slot slot. More...
 
static int pinNode (recompVectors *rvec, int nodenum, int mxtips)
 
void unpinNode (recompVectors *v, int nodenum, int mxtips)
 Marks node nodenum as unpinnable. More...
 
boolean getxVector (recompVectors *rvec, int nodenum, int *slot, int mxtips)
 Get a pinned slot slot that holds the likelihood vector for inner node nodenum. More...
 
static int subtreeSize (nodeptr p, int maxTips)
 
void computeTraversalInfoStlen (nodeptr p, int maxTips, recompVectors *rvec, int *count)
 Annotes unoriented tree nodes tr with their subtree size. More...
 
void computeFullTraversalInfoStlen (nodeptr p, int maxTips, recompVectors *rvec)
 Annotes all tree nodes tr with their subtree size. More...
 
void allocTraversalCounter (pllInstance *tr)
 
void countTraversal (pllInstance *tr)
 
void printTraversalInfo (pllInstance *tr)
 

Detailed Description

Functions used for recomputation of vectors (only a fraction of LH vectors stored in RAM)

Function Documentation

void allocRecompVectorsInfo ( pllInstance tr)

Allocates memory for recomputation structure.

Todo:
this should not depend on tr (vectorRecomFraction should be a parameter) PLL_TRUE if recomputation is currently applied
void computeFullTraversalInfoStlen ( nodeptr  p,
int  maxTips,
recompVectors rvec 
)

Annotes all tree nodes tr with their subtree size.

Similar to computeTraversalInfoStlen, but does a full traversal ignoring orientation. The minum cost is defined as the minimum subtree size. In general, the closer a vector is to the tips, the less recomputations are required to re-establish its likelihood entries

Parameters
pPointer to node
maxTipsNumber of tips in the tree
rvecRecomputation info

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void computeTraversalInfoStlen ( nodeptr  p,
int  maxTips,
recompVectors rvec,
int *  count 
)

Annotes unoriented tree nodes tr with their subtree size.

This function recursively updates the subtree size of each inner node.

Note
The subtree size of node p->number is the number of nodes included in the subtree where node record p is the virtual root.
Parameters
pPointer to node
maxTipsNumber of tips in the tree
rvecRecomputation info
countNumber of visited nodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static int findFreeSlot ( recompVectors v,
int  mxtips 
)
static

Finds a free slot.

If all slots are occupied, it will find the cheapest slot and unpin it

+ Here is the call graph for this function:

static int findUnpinnableSlot ( recompVectors v,
int  mxtips 
)
static

Finds the cheapest slot and unpins it.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static int findUnpinnableSlotByCost ( recompVectors v,
int  mxtips 
)
static

Find the slot id with the minimum cost to be recomputed.

The minum cost is defined as the minimum subtree size. In general, the closer a vector is to the tips, the less recomputations are required to re-establish its likelihood entries

Todo:
remove _DEBUG_RECOMPUTATION code
Parameters
v
mxtipsNumber of tips in the tree

+ Here is the caller graph for this function:

boolean getxVector ( recompVectors rvec,
int  nodenum,
int *  slot,
int  mxtips 
)

Get a pinned slot slot that holds the likelihood vector for inner node nodenum.

If node node nodenum is not pinned to any slot yet, the minimum cost replacement strategy is used.

Parameters
vRecomputation info
nodenumnode id
slotslot id
mxtipsNumber of tips in the tree

+ Here is the caller graph for this function:

static boolean isNodePinned ( recompVectors rvec,
int  nodenum,
int  mxtips 
)
static

Checks if nodenum is currently pinned (available in RAM)

Note
shall we document static functions?
Parameters
rvecRecomputation info
nodenumNode id to be checked
mxtipsNumber of tips in the tree

+ Here is the caller graph for this function:

boolean needsRecomp ( boolean  recompute,
recompVectors rvec,
nodeptr  p,
int  mxtips 
)

Checks if the likelihood entries at node p should be updated.

A node needs update if one of the following holds:

  1. It is not oriented (p->x == 0)
  2. We are applying recomputations and node p is not currently available in RAM
Parameters
recomputePLL_TRUE if recomputation is currently applied
pNode to check whether it is associated with the likelihood vector
mxtipsNumber of tips in the tree

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pinAtomicNode ( recompVectors v,
int  nodenum,
int  slot,
int  mxtips 
)
static

Pins node nodenum to slot slot.

The slot is initialized as non-unpinnable (ensures that the contents of the vector will not be overwritten)

Parameters
nodenumnode id
slotslot id
mxtipsNumber of tips in the tree
void protectNode ( recompVectors rvec,
int  nodenum,
int  mxtips 
)

Locks node nodenum to force it remains availably in memory.

Warning
If a node is available we dont need to recompute it, but we neet to make sure it is not unpinned while buildding the rest of the traversal descriptor, i.e. unpinnable must be PLL_FALSE at this point, it will automatically be set to PLL_TRUE, after the counter post-order instructions have been executed Omitting this call the traversal will likely still work as long as num_allocated_nodes >> log n, but wrong inner vectors will be used at the wrong moment of pllNewviewIterative, careful!
@param rvec 
  Recomputation info

@param nodenum
  Node id that must remain available in memory 

@param mxtips
  Number of tips in the tree

+ Here is the caller graph for this function:

void unpinNode ( recompVectors v,
int  nodenum,
int  mxtips 
)

Marks node nodenum as unpinnable.

The slot holding the node nodenum is added to the pool of slot candidates that can be overwritten.

Parameters
vRecomputation info
nodenumnode id
mxtipsNumber of tips in the tree

+ Here is the caller graph for this function: