1 In this document I will try to draw the data structures and how they
2 interrelate in the Portals 3 reference implementation. It is probably
3 best shown with a drawing, so there may be an additional xfig or
10 First, a digression on memory allocation in the library. As mentioned
11 in the NAL Writer's Guide, the library does not link against any
12 standard C libraries and as such is unable to dynamically allocate
13 memory on its own. It requires that the NAL implement a method
14 for allocation that is appropriate for the protection domain in
15 which the library lives. This is only called when a network
16 interface is initialized to allocate the Portals object pools.
18 These pools are preallocate blocks of objects that the library
19 can rapidly make active and manage with a minimum of overhead.
20 It is also cuts down on overhead for setting up structures
21 since the NAL->malloc() callback does not need to be called
24 The objects are maintained on a per-object type singly linked free
25 list and contain a pointer to the next free object. This pointer
26 is NULL if the object is not on the free list and is non-zero
27 if it is on the list. The special sentinal value of 0xDEADBEEF
28 is used to mark the end of the free list since NULL could
29 indicate that the last object in the list is not free.
31 When one of the lib_*_alloc() functions is called, the library
32 returns the head of the free list and advances the head pointer
33 to the next item on the list. The special case of 0xDEADBEEF is
34 checked and a NULL pointer is returned if there are no more
35 objects of this type available. The lib_*_free() functions
36 are even simpler -- check to ensure that the object is not already
37 free, set its next pointer to the current head and then set
38 the head to be this newly freed object.
40 Since C does not have templates, I did the next best thing and wrote
41 the memory pool allocation code as a macro that expands based on the
42 type of the argument. The mk_alloc(T) macro expands to
43 write the _lib_T_alloc() and lib_T_free() functions.
44 It requires that the object have a pointer of the type T named
45 "next_free". There are also functions that map _lib_T_alloc()
46 to lib_T_alloc() so that the library can add some extra
47 functionality to the T constructor.
54 Many of the active Portals objects are stored in doubly linked lists
55 when they are active. These are always implemented with the pointer
56 to the next object and a pointer to the next pointer of the
57 previous object. This avoids the "dummy head" object or
58 special cases for inserting at the beginning or end of the list.
59 The pointer manipulations are a little hairy at times, but
60 I hope that they are understandable.
62 The actual linked list code is implemented as macros in <lib-p30.h>,
63 although the object has to know about