Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

VCBuilder Work Queue

WorkQueue stores the endpoints of any VCLists that need further processing.

Endpoints are pushed onto the back of the queue and popped off the front, in FIFO order. It also ensures only unique elements are added; that is, a list is added only once until it is processed.

The implementation here is a simple vector with an index simulating the front of the queue; that is, push() uses push_back() to add elements to the back and pop() increments the index of the front. This means the vector will need to be as large as the number of calls to push(), not the maximum number of elements in the queue at any given time.

On 11x11, the vector quickly grows to hold 2^14 elements if anding over the edge, and 2^13 if not. Since only unique elements are added, in the worst case this value will be the smallest n such that 2^n > xy, where x and y are the width and height of the board.

This implementation was chosen for efficiency: a std::deque uses dynamic memory, and so every push()/pop() requires at least one call to malloc/free. The effect is small, but can be as significant as 1-3% of the total run-time, especially on smaller boards.


6 Jan 2011 Doxygen 1.6.3