L2List

The class Test1 is pure virtual.

The class L2List implements a doubly linked list.
In QHG4 it is mainly used to manage memory for the agent arrays.

Inside a L2List there are two chains: ACTIVE and PASSIVE representing used and unused locations.

../../images/L2L_A1.png

L2List is used by LayerBuf and LBContoller.

Code:
L2List.h
L2List.cpp

Structures

typedef struct {
    int  iPrev;
    int  iNext;
} L2Node;

Representation of a node for the doubly linked list

Public Methods

constructor

L2List(int iSize);

Create a list with specified number of nodes.

constructor

L2List(const L2List *pL2L);

The copy constructor

destructor

~L2List();

The destructor.

clear

void clear();

Clears the list (all nodes are moved to the PASSIVE chain)

reserveSpace2

int reserveSpace2(uint iNum);

Moves iNum nodes after the last ACTIVE node into the ACTIVE chain.

iNum

Number of nodes to activate.

Returns the index of the first node which was activated, or -1

getNumEndFree

int getNumEndFree();

Returns the number of nodes after the last ACTIVE node

addElement

int addElement();

Remove a node to from the PASSIVE chain and add it to the ACTIVE chain.

removeElement

int removeElement(int iEl);

Remove the specified node to from the ACTIVE chain and add it to the PASSIVE chain.

iEl

Index of node to be removed.

getFirstIndex

int getFirstIndex(uchar uState) const;

Find index of first node in specified chain.

uState

Must be either ACTIVE or PASSIVE.

getLastIndex

int getLastIndex(uchar uState) const;

Find index of last node in specified chain.

int getNext

int getNext(int iCur) const;

Get index of the node following specified node in the L2List.

iCur

Node index.

countOfState

int countOfState(uchar uState);

Count number of nodes in specified chain.

uState

Must be either ACTIVE or PASSIVE.

Returns count.

collectFragInfo

uint collectFragInfo(uint iSize, uint *piHoles, uint *piActive);
Collects data used to defragment.
After defragmentation, both chains have contiguous nodes.
For this it gets the indexes of the first PASSIVE nodes, as well as the indexes of the lats ACTIVE nodes.
The highest index of the selected PASSIVE nodes is less than the lowest index of the selected PASSIVE nodes.

Example:

Linked list (x=ACTIVE, o=PASSIVE)
0         1         2
0123456789012345678901234567890
xxoxooxxxxoxooooxoxxxoooxxooooo

piHoles:
   2  4  5 10 12 13
piActive:
  25 24 20 19 18 16
iSize

Size of the buffers piHoles and piActive

piHole

Array to hold the indexes of the first nodes in the PASSIVE chain.

piActive

Array to hold the indexes of the first nodes in the ACTIVE chain.

Returns the number of found holes, or iSize+1 if there are mor than iSize holes.

defragment

int defragment(uint iSize, uint *piActive);

Performs the actual defragmentation.

iSize

Size of the buffer piActive

piActive

Array containing the non-contiguous nodes of the ACTIVE chain.

setState

int setState(uchar uState, uint iNum);

Sets the state of node iNum to the specified state,

uState

Must be either ACTIVE or PASSIVE.

iNum

Index of the node to be mdified.

getBufSize

int getBufSize(int iDumpMode);

Calculates the size of a buffer to hold the entire L2List data ina seriaized form.

iDumpMode

Various modes for dumping. Possible values DUMP_MODE_FLAT or DUMP_MODE_SMART-

Returns calculated size.

serialize

uchar *serialize(uchar *pBuf);

Serializes the L2List into pBuf.

pBuf

Buffer to serialize into.

Returns pointer to one position after the end of the serialized data.

deserialize

uchar *deserialize(uchar *pBuf);

Creates L2List from serialized data.

pBuf

Buffer containing serialized L2List data.

Returns pointer to one position after the end of the serialized data.