struct ListNode
{
int val;
ListNode* next;
ListNode (int x) :
val (x), next (NULL)
{
}
};
static ListNode* reverse_list (ListNode* pHead)
{
/**
* 输入一个链表，反转链表后，输出链表的所有元素。
* ------------------------------
* Given a list. Please reverse it and then print all elements in it.
*
* train of thought:
* order sublist and put the first unorder ele in the front of ordered sublist
* 1 234 1 is init ordered sublist, 234 is unordered sublist
* we put the first ele 2 in unordered sublist to the front of ordered sublist 1, we have
* 21 34 21 is ordered sublist, 34 is unordered sublist
* we put the first ele 3 in unordered sublist to the front of ordered sublist 21, we have
* 321 4 321 is init ordered sublist, 4 is unordered sublist
* we put the first ele 4 in unordered sublist to the front of ordered sublist 321, we have
* 4321
* done!
*/
if (pHead == NULL)
return NULL;
ListNode *tail = pHead, *nxt = pHead->next;
while (nxt != NULL)
{
// insert nxt to front of head
tail->next = nxt->next;
nxt->next = pHead;
pHead = nxt;
nxt = tail->next;
}
return pHead;
}
TEST_F(mpath,test_reverse_list)
{
ListNode one = ListNode (1);
ListNode two = ListNode (2);
ListNode three = ListNode (3);
one.next = &two;
two.next = &three;
ListNode* head = reverse_list (&one);
ASSERT_EQ(3, head->val);
ASSERT_EQ(2, head->next->val);
ASSERT_EQ(1, head->next->next->val);
}
A Cell Application, or CellApp, is the actual process or executable running on a CellApp machine.
A CellApp manages various cells, or instances of the Cell class. A cell is a geometric part of a large space, or the entirety of a small space.
BigWorld divides large spaces into multiple cells in order to share the load evenly. It typically allocates one large cell to each CellApp. When handling smaller spaces, such as dynamically created mission ones, BigWorld typically allocates several cells to each CellApp.
In BigWorld, the CellApp machines are intended to run only BWMachined and one CellApp per CPU, and nothing else.
CellApps are concerned with a generic type, the entity. Each CellApp maintains a list of the real and ghost entities within its reach. The CellApp also maintains a list of any real entities that need to be updated periodically (e.g., 10 times per second), and those that maintain an AoI.
Each entity understands the messages that are associated with its type. The CellApp delivers entity messages to the appropriate entity, and it is up to it to interpret them. The way this is implemented is by having every entity include a pointer to an entity type object. This object has information related to the entity’s type, such as the messages that the type can handle and the script associated with it.
Every entity type has it own script file. Scripts execute in the context of a particular entity (i.e., they have a this or self), and have access to the data that other entities choose to make available (server and client data), as well as the basic members of every entity (id, position, …).
Scripts are responsible for handling messages sent to an entity. When any server or client data is changed, the changes are automatically forwarded to interested entities.
In order to efficiently update its client, each avatar keeps a list of entities in its AoI, which is typically a circle with a radius of 500m. One issue that arises is that not all entities might be controlled by the same cell.
However, it would be very inefficient to have each entity individually determine which entities on adjacent cells should be ghosted. The solution is to have cells generically manage ghost entities. If an entity is within the ghost distance of a cell boundary, the cell creates a ghost of the entity on that nearby cell.
The term real entity is introduced to distinguish between the master representations and the (imported) ghosts. The figure below shows all entities maintained by cell 1:
Once a second, a cell goes through its real entities to check if it should add or delete ghosts for them on neighbouring cells. It sends messages to the neighbour to add and remove the ghosts.
The simplest method to transition between different spaces is simply to ‘pop’, i.e., to remove the entity from the old space and recreate it in the new one. This is simple on both client and server.
Whenever an entity has a client attached to it, a sub-object known as a witness is associated to the entity, in order to maintain the list of entities in its AoI. The witness builds update packets to send to its client, and it must send the most important information as a priority.
The client requires the position and other information of other entities that are closest to it to be the most accurate and current. Closer entities should be updated more frequently. To achieve this, the witness keeps the list of entities in its AoI as a priority queue.
To construct a packet to be sent to the client, relevant information about the entities on the top of the list is added to the packet until the desired size is reached. The information can include position and direction, as well as events that the entity has processed since the last update. For more details, see Event History.
Closer entities receive more frequent updates, and get a greater share of the available bandwidth.
BigWorld throttles downstream bandwidth according to both the size of
update packets, and their frequency. These parameters are specified in
the configuration file
aoi priority list of e0:
Each entity keeps a history of its recent events. The history includes both events that change its state (such as weapon change), as well as actions that do not (such as jumping and shooting). Frequent actions, such as movement, which affect volatile data, are not kept in the history list.
When an entity consumes its priority queue to construct an update packet, it searches through new events of the top entities (i.e., the ones closes to it), and adds all messages it is interested in. This requires keeping a timestamp (actually a sequence number) for the last update of each entity in the priority queue.
The history of these types of events is fairly short (around 60 seconds) since we expect that each entity in the priority queue will be considered (roughly) once every 30 seconds in the worst case scenario.
The priority queue handles the data throttling for continuous information. For events, we still need to handle the case where there are too many events filling up available downstream bandwidth to the client.
When there are many entities in an entity’s AoI, information about each one is sent less often, but the total number of events remains the same.
To address this, BigWorld uses a Level of Detail (LOD) system for handling event-based changes. Its principle is that the closer an entity is to the avatar, the more detail it should send to its client.
For example, when a player initially comes within the avatar’s AoI, the avatar does not need to know all details about the other player. The visible inventory may only be required when within, say, 100 metres. Finer details, such as a badge on clothing, might only be needed within 20 metres.
In the description of each entity type, there is a description of all messages (non-state-changing events) it can generate, along with the priority associated with each one.
When an avatar adds information about an entity, it only adds messages with a priority greater than the avatar’s current interest in the entity. Therefore, messages will be ignored depending on the distance between the avatar and the entity.
For example, there might be a type of chat heard only within 50 metres, or a jump seen only within 100 metres.
GECOEngine cannot ignore state-changing events that occur out of range, because if the entity subsequently does get close enough, the client will have an incorrect copy of the entity’s state.
For example, the client may be interested in the type of weapon that an entity is carrying, but only when it is within 100 metres. If the entity changes its weapon outside this range, then this information is not sent to the client as yet. BigWorld will only send it if the entity comes within range.
Unlike non-state-changing events, in which the priority level can have any value, state-changing events have a discrete or non-contiguous number of state LODs specified by the developer.
These can be thought of as rings around the client. Each property of an entity’s type can be associated with one of these rings. For an example:
<seatType>
<Type> INT8 </Type>
<Flags> OTHER_CLIENT </Flags>
<Default> -1 </Default> <!-- See Seat.py -->
<DetailLevel> NEAR </DetailLevel>
</seatType>
For example, supposed an avatar A is surrounded by four entities of the same type, with LOD levels at 20m, 100m, and 500m. It will process each entity according to its distance, as described in the table below:
| Entity | Distance | 20m | 100m | 500m |
|---|---|---|---|---|
| E1 | 15m | y | y | y |
| E2 | 90m | n | y | y |
| E3 | 400m | n | n | y |
| E4 | 1000m | n | n | n |
When an entity with an associated witness comes within an LOD ring of another entity, any state associated with the ring that has changed since they were last this close is sent to the client.
uses timestamps to achieve to prevent very often updates. A timestamp is stored with each property of each entity. This timestamp indicates when that property was last changed. Also, for each entity in a witness’ AoI, a timestamp corresponding to when that entity last left that level is kept for each LOD ring.
By itself, this does not allow us to throttle this data. To achieve this, we only need to apply a multiplying factor to the interested level of the avatar when it is calculated for other entities. Multiplying by a factor less than one has the effect of reducing the amount of data sent. As a result, the bigger the ring is, the more data to be sent. the smaller the ring is, the less data to be sent.
The following sub-sections describe how to use scripting for entities.
An entity class describes a type of entity. The list below describes its component parts:
The XML definition file can be considered the interface between the Cell, Base and Client scripts. It defines all available public methods, and all properties of an entity. In addition, it defines global characteristics of the class, such as:
The following is an example entity definition file
<root>
<Properties>
<seatType>
<Type> INT8 </Type>
<Flags> OTHER_CLIENT </Flags>
<Default> -1 </Default> <!-- See Seat.py -->
<DetailLevel> NEAR </DetailLevel>
</seatType>
<ownerID>
<Type> INT32 </Type>
<Flags> OTHER_CLIENT </Flags>
<Default> 0 </Default>
</ownerID>
<channel>
<Type> INT32 </Type>
<Flags> PRIVATE </Flags>
</channel>
</Properties>
<ClientMethods>
<clientMethod1>
<Arg> STRING </Arg> <!-- msg -->
<DetailDistance> 30 </DetailDistance>
</clientMethod1>
</ClientMethods>
<CellMethods>
<sitDownRequest>
<Exposed/>
<Arg> OBJECT_ID </Arg> <!-- WHO -->
</sitDownRequest>
<getUpRequest>
<Exposed/>
<Arg> OBJECT_ID </Arg> <!-- WHO -->
</getUpRequest>
<ownerNotSeated>
</ownerNotSeated>
<tableChat>
<Arg> STRING </Arg> <!-- msg -->
</tableChat>
</CellMethods>
<LODLevels>
<level> 20 <hyst> 4 </hyst> <label> NEAR </label> </level>
<level> 100 <hyst> 10 </hyst> <label> MEDIUM </label> </level>
<level> 250 <hyst> 20 </hyst> <label> FAR </label> </level>
</LODLevels>
</root>
All properties are defined in the XML file,
All cell entity properties need to be defined, even if they are private to the class. This is because CellApps need to offload entities to other CellApps, and having the data types of all properties defined allows the data to be transported as efficiently as possible.
Note: For security and efficiency reasons, when a client modifies a shared property, the change is not propagated to the server. All communication from the client to the server must be done using method calls.
This is because only when original data is changed or updated, propagation of the new value on copy data can be done. And the only way a client can change the original data is via rpc.
When a Python script modifies the value of a property, the server does the work of propagating this property change to the correct places.
In other words, when a property changed from the entity’s own client via rpc or command msg, the server uses:
Flag is consisted of SourceProcess + Accessibility +PropagationProcess.
SourceProcess must not be same to PropagationProcess.
SourceProcess is among CELL, BASE or CLIENT,
Accessibility is among of PUBLIC, PRIVATE OR PROTECTED.
PropagationProcess is among of ALL_CLIENT, OWN_CLIENT, OTHER_CLIENT, BASE or NONE if only stored in SourceProcess no propagation.
IE., ALL_CLIENT can be treated as CELL__PUBLIC__ALL_CLIENT.
The following flags are used in the XML definition to determine how each property should be replicated.
NOTE: Property definitions can also include the tag DetailLevel. This is used for data LOD processing. For details on LOD processing, see the document Server Programming Guide Proxies and Players → Entity Control.
In addition to the properties defined in the XML file, cell entity scripts also have access to several built-in properties provided by the cell scripting environment. These include:
It is possible to move an entity by changing its position property. However, for continuous movement, the method moveToPoint is recommended. The spaceID and vehicle properties are influenced by the teleport and boardVehicle methods, respectively.
There are different sections for client, cell, and base methods, and each method contains its name and its list of arguments.
Cell and base methods can also have an optional
Method definitions can also have a
A client has references to all entities that are within its AoI. A cell component of an entity can call methods on other client entities (including its own) that exist within this AoI.
Four properties are available to the cell script, to facilitate calling client methods. These are:
A method called on one of these objects will be delivered to the indicated clients.
For example, to call the chat method on the client script for this object,
for all nearby clients: self.allClients.chat( "hi!" ).
The cell script has access to numerous built-in script methods, some of which are described in the list below:
A controller is a C++ object associated with a cell entity. It normally performs a task that would be inefficient or difficult to do from script. It also generally has state information, which must be sent across the network if the entity is offloaded to another cell.
Examples of currently implemented controllers are:
Since controllers normally perform operations asynchronously, they notify the script object of completion by calling a named script callback. For example, the TimerController always calls the onTimer event handler, and the MoveToPointController always calls the onMove event handler.
5.1.6.10. Example Script File
Cell entity script —
"This module implements the Seat entity."
import BigWorld
import Avatar
# -----------------------------------------------------------------------
# Section: class Seat
# -----------------------------------------------------------------------
class Seat( BigWorld.Entity ):
"A Seat entity."
def __init__( self ):
BigWorld.Entity.__init__( self )
def sitDownRequest( self, source, entityID ):
if self.ownerID == 0 and source == entityID:
self.ownerID = entityID
BigWorld.entities[ self.ownerID ].enterMode(
Avatar.Avatar.MODE_SEATED, self.id, 0 )
if self.channel:
try:
channel = BigWorld.entities[ self.channel ]
channel.register( self.ownerID )
except:
pass
def getUpRequest( self, source, entityID ):
if self.ownerID == entityID and source == entityID:
if self.channel:
try:
channel = BigWorld.entities[ self.channel ]
channel.deregister( entityID )
except:
pass
BigWorld.entities[ self.ownerID ].cancelMode()
# The Avatar's cancelMode() method will in-turn call this
# Seat's ownerNotSeated() method to release itself.
def ownerNotSeated( self ):
self.ownerID = 0
def tableChat( self, msg ):
if self.channel:
channel = BigWorld.entities[ self.channel ]
assert( channel )
assert( self.ownerID )
channel.tellOthers( self.ownerID, "[local] " + msg )
Not all events are propagated via the event history. If an event is destined for a specific player, or a small number of players, then it can be delivered almost immediately in its next packet.
Each ghost knows its real cell, so that it can forward messages to its real version to be processed.
Most messages are of the pull type, as in when another player jumps — it is up to the avatar (via the priority queue) to decide if and when to send this to its client.
Minority of the messages is of the push variety, as in when player A wants to shake hands with player B. To do this, client A sends a handshake request to its cell, which in turns makes a request to avatar B on the same cell.
Avatar B may be a ghost, in which case it forwards the request to its real representation. This communication happens automatically and transparently.
Approximately once a second each cell checks whether to offload any entities to other cells. Each entity is considered against the boundary of the current cell.
The boundary is artificially increased (by about 10 metres) to avoid hysteresis. If an entity is found to be outside the boundary of the current cell, it is offloaded to the most appropriate one.
When an entity is offloaded, the real entity object is transformed into a ghost entity, and vice-versa when an entity is loaded.
When a cell is added to a large multi-cellular space during runtime, it is done by gradually increasing its area, in order to avoid a large spike in entities trying to change cells. Similarly for removing a cell, its area slowly decreases until all entities are gone.
Cell boundaries are moved in order to adjust the proportion of the server load that an individual cell is responsible for.
The basic (simplified) idea is that if a cell is overloaded in comparison to other cells, then its area is reduced. Conversely, if it is underloaded, then its area is increased.
Because of factors such as latency inherent in traversing the Internet, large number of desired players, and bandwidth limits, it is difficult (if not impossible) to achieve a convincing game where full collision handling is attempted.
For more details, see the document Server Programming Guide’s section Proxies and Players → Entity Control.
The key features of the navigation system are:
For details, see the document Server Programming Guide, section Entities and the Universe → Navigation System.
There is often the need to trigger an event when an entity (of a specific type) gets close enough to another. These are called Range Triggers.
There is also the need to find all entities that are in a given area. This is called a Range Query.
To perform a range query, the software searches just one of these lists to the distance of the query range, and then selects the entities geometrically in range (can be achieved by set intersection that must <z and <y).
To perform a range trigger, the entity that is interested in a particular range inserts high and low triggers in both the X and Z lists. When the entity moves, the lists and the triggers are updated. When other entities move, the lists are updated. If an entity crosses a trigger, or a trigger crosses an entity, then the software checks the other dimension to test whether it is actually a trigger event.
For the majority of situations this algorithm has been found to be very effective.
The CellApp is designed to be fault tolerant. A CellApp process can stop suddenly, or its machine can become disconnected from the network, with little noticeable impact on the server.
The CellAppMgr is responsible for:
When a new CellApp is started, it finds the location of the CellAppMgr by broadcasting a message to all BWMachined daemons.
If a BWMachined process has a CellAppMgr on its machine, then its address is returned to the CellApp. Once the CellApp has the location of the CellAppMgr, the CellApp registers itself with it. Next time the CellAppMgr needs to create more cells, the new CellApp will be considered as a potential host for it.
Similarly, when the CellApp stops, it deregisters itself with the CellAppMgr, after having all its cells gradually removed.
The SR latch is awkward because it behaves strangely when both S and R are simultaneously asserted.
Moreover,the S and R inputs conflate the issues of what and when. Asserting one of the inputs determines not only what the state should be but also when it should change.
Designing circuits becomes easier when these questions of what and when are separated. The D latch in Figure 3.7(a) solves these problems.
It has two inputs. The data input, D, controls what the next state should be. The clock input, CLK, controls when the state should change.
The D latch updates its state continuously while CLK = 1. We shall see later in this chapter that it is useful to update the state only at a specific instant in time. The D flip-flop described in the next section does just that.
a D flip-flop copies D to Q on the rising edge of the clock, and remembers its state at all other times.
How long does it take to find the root cause of a failure in your system?
If you log too much, you’ll need to:
normally two main goals of logging:
If your log can’t explain the cause of a bug or whether a certain transaction took place,
you are logging too little.
critical and error msgs are generated when application itself goes wrong
and problems need to be fixed by external forces like developer or system admin.
the process actually died if critical msg happens while the process is still alive
but cannot provide service if error msg happens.
The classic categories are (based on functionality):
Statistical log and Diagnostic log complement each other
For each log type above (request entry and exit and so on),
they should:
create unique identifiers for transactions that involve processing across
many threads and/or processes to makes it much easier to trace a specific
transaction when many transactions are being processed concurrently.
Logged timing data can help debug performance issues
Logging the start and finish times of calls that can take measurable time:
When problems occur, before fixing the problem: