Project: 3D Craft -- Lists and Nodes

This page describes the lists used in P3DC. Lists are used everywhere to hold collections of things like vertices, polygons, clip results, etc. A lot of people have suggested that arrays are faster than linked lists in the rendering part of the engine and they are probably right, but lists give me some flexibility that I really like so I forego the speed advantage of arrays.

There are two parts to this page:

• List Architecture and Design
• List Constants and Programming Interface
  • Constants
  • Programming Interface
    • p3dc_init_list
    • p3dc_new_list
    • p3dc_free_list
    • p3dc_add_node
    • p3dc_remove_node
    • p3dc_get_node
    • p3dc_new_node
    • p3dc_free_node

List Architecture and Design

As I started writing the documentation on lists I realized they are in a complete jumble. This situation occured because lists were half written at the beginning of the project and then added to at the end of the project. I've concluded I need two lists and types for each. These are:

• LINKED -- best performance (default)
• SORTED -- Searchable by 'name.'

Then there are the methods on lists, we know there are:

• new -- allocate a new empty list
• free -- de-allocate a possibly non-empty list
• init -- initialize a new list to be empty
• add -- Add a node to a list:
  • HEAD (at the front)
  • TAIL (at the end of the list)
  • BYNAME (sorted insertion)
  • AFTER a given node.
  • BEFORE a given node.
• remove -- Remove a node from the list
  • FIRST -- first node on the list. (equivalent to a 'pop' operation)
  • LAST -- last node on the list (good for creating FIFO lists)
  • THIS -- When you have the list in hand and want it removed.
  • BYNAME -- Identified by a given name.
  • BYDATA -- Identified by the data pointer it is holding.
• get -- Find a node on this list
  • FIRST -- return the first node on the list.
  • LAST -- return the last node on the list
  • NEXT -- return the next node relative to the one returned last time.
  • PREVIOUS -- return the previous node relative to the one returned last time.
  • BYNAME -- return the node on the list associated with this name.
  • BYDATA -- return the node on the list that is "holding" a pointer to this data.
  • CURRENT -- return the same node returned last time.

List invariants we want to enforce:

1. A node lives on exactly one list. (node->owner == list)
2. A list with a specified type has only nodes of that type on it. (node->data.t == list->n_type)
3. Nodes in use do not appear on the free list.

List Constants and Programming Interface

Constants

Positioning nodes on lists with p3dc_add_node (type is p3dc_NODE_POSITION)

• P3DC_LIST_HEAD -- Node is added to the head of the list.
• P3DC_LIST_TAIL-- Node is added to the tail (end) of the list.
• P3DC_LIST_BEFORE-- Node is added to the list ahead of the passed in node.
• P3DC_LIST_AFTER-- Node is added to the list after the passed in node..
• P3DC_LIST_BYNAME-- Node is added to the searchable list based on its "name".

Types of lists supported (type is p3dc_LIST_TYPE)

• P3DC_LIST_LINKED -- List is a standard linked list.
• P3DC_LIST_SORTED -- List is a binary search tree (Red-Black tree).

Locations where nodes can be gotten or removed (type is p3dc_NODE_LOCATION)

• P3DC_NODE_CURRENT -- Use the same node that was returned last time.
• P3DC_NODE_FIRST -- Use the first node on the list.
• P3DC_NODE_NEXT -- Use the node after the last one that was used.
• P3DC_NODE_LAST -- Use the last node on the list.
• P3DC_NODE_PREVIOUS -- Use the node previous to the last one that was used.
• P3DC_NODE_BYNAME -- Use the node with the given name.
• P3DC_NODE_BYDATA -- Use the node holding the given data pointer.
• P3DC_NODE_THIS -- Use the node that was passed in.

List Programming Interface

void p3dc_init_list( p3dc_LIST *list, p3dc_TYPE n_type, p3dc_LIST_TYPE l_type )

Initialize the list pointed to by list to have hold only type n_type nodes. (if n_type is set to P3DC_TYPE_UNKNOWN then the list can hold any type. The type of list (sorted or linked) is specified by l_type.

p3dc_LIST *p3dc_new_list( p3dc_TYPE n_type, p3dc_LIST_TYPE l_type )

Allocate a list, initialize it, and return a pointer to it. As with p3dc_init_list the value in n_type sets the types of nodes allowed on the list and the value in l_type sets the type of list to either sorted or linked.

void p3dc_free_list( p3dc_LIST *list )

Free a list and the nodes that are on it. This is kind of a wart since p3dc_new_list only allocates an empty list and this function frees nodes and lists but it didn't seem worth architectural "purity" to have a p3dc_empty_list that only freed the nodes and then this function to free the list object itself.

int p3dc_add_node( p3dc_LIST *list, p3dc_NODE *node, p3dc_NODE_LOCATION where, ... )

This function adds the node referenced by node to the list referenced by list. The value in where tells the function if you want the node added to the end, beginning, by name etc. If the where parameter requires an argument it is passed after where. (currently the locations P3DC_LIST_BYNAME, P3DC_LIST_BEFORE, P3DC_LIST_AFTER require arguments.)

p3dc_NODE * p3dc_remove_node( p3dc_LIST *list, p3dc_NODE_POSITION where, ... )

This function removes a node from the list referenced by list. The value in where tells the function which node to remove. For some values of where an argument is required and that argument is passed after the where parameter. (currently the positions P3DC_NODE_BYNAME, P3DC_NODE_THIS, P3DC_NODE_BYDATA require arguments.) The node removed is actually returned so you can use it on another list or free it if you choose.

p3dc_NODE * p3dc_get_node( p3dc_LIST *list, p3dc_NODE_POSITION where, ... )

This function is used to retrieve nodes from the list, but leave them on the list. After it is called the node returned is set as the current node. The position of the node is identified by the where parameter. For some values of the where parameter an argument is required. (currently the positions P3DC_NODE_BYNAME, P3DC_NODE_CURRENT, P3DC_NODE_BYDATA, P3DC_NODE_BEFORE, and P3DC_NODE_AFTER require arguments.)

void p3dc_new_node( void *payload, char *name, int flags )

This function allocates a new node, and gives it payload to carry. If name is non-null it is used as the node's name and the value in flags can be either 0 or P3DC_NODE_FREEPAYLOAD which affects whether or not the library trys to free the node's payload when it frees the node. If this flag is not set you are responsible for freeing the payload if it is allocated from the heap.

void p3dc_free_node( p3dc_NODE *node )

This function will free a node, if the node was created with the flag P3DC_NODE_FREEPAYLOAD set then the payload will also be freed. NOTE: if the name is non-null it will also be freed so don't leave a char pointer in there by mistake. When you allocated the node if you gave it a name the name was strdup'd here and freeing it is the right thing to do.