UEFI Application Programming: SysList and SysListO (Part 2)

In the previous article I introduced the basic functions of the System Object library that I use when writing C applications in UEFI. In this article I will extend this by introducing two container objects: a list of arbitrary data and a list of objects. To those of you wondering, "Where's the UEFI?" I understand. Don't worry, in the next article I will introduce the next two containers and use them in my UEFI HII application.

 

SysList
The SysList container is derived from the System Object and acts as a list of pointers to arbitrary data. The list does not free the data when removed from the list. Each of the list entries points to the data. In this way, the list can organize any data.

 

The first entry in the list is called the head. The last entry in the list is called the tail. New list entries can be added before the head, after the tail or before or after any other entry. It is possible to navigate to the next entry or the previous entry, but there is no easy way to navigate to the nth entry. Arrays are more suitable for that sort of behavior.

 

SysList is implemented with the SYS_LIST structure, as follows:

typedef struct _SYS_LIST {
  SYS_OBJ Obj; // standard object structure. must be first.

  SYS_LIST_ENTRY Header;
} SYS_LIST; 

The first thing to notice is that the System Object structure, SYS_OBJ is placed first. This is true for all of the derived object containers. Header, in turn, acts as a dummy list entry which points to the first and last list entries. The entries look like this:

typedef struct _SYS_LIST_ENTRY {
  SYS_LIST_ENTRY *Prev;
  SYS_LIST_ENTRY *Next;
  VOID *Value;
} SYS_LIST_ENTRY;

 

Each entry points to the next and previous list entry OR the header's dummy entry. If it points to the dummy entry, it means it is either the first or the last list entry. Each entry also points to the data. That is, the list itself does not contain the data, only a pointer to the data.

 

Here are the standard functions for manipulating lists:

• SysListInit - Initialize an empty list container.
• SysListEmpty - Free all list entries and reset to empty. Does not free data.
• SysListIsValid - Return if pointer points to a valid list container.
• SysListIsEmpty - Return whether list contains any list entries.
• SysListAddTail - Add a new list entry for data after the last list entry.
• SysListRemoveTail - Remove last list entry and return pointer to data.
• SysListRemoveHead - Remove first list entry and return pointer to data.
• SysListGetNext - Iterate through a list container.

Here are some common tasks using lists:

 

1. Initialize a declared list:

 

SYS_LIST l;
SysListInit(&l);

 

2. Create a new list:

 

SYS_LIST *pl;
pl == SysNew(SysList);
if (pl == NULL) {
  // error...
}

 

3. Add an entry to the list:

 

VOID *p;  // ptr to data
SYS_LIST *pl;
if (!SysListAddTail (pl, p)) {
  // error...
}

 

4. Remove all entries in a list:

 

SYS_LIST *pl;
SysListEmpty(pl);

 

5. Remove and free all entries in a list:

 

SYS_LIST *pl;
while (!SysListIsEmpty(pl)) {
  free (SysListRemoveTail(pl));
}

 

6. Walk through all entries in the list. This function uses SYS_LIST_POS as an abstract type that refers to the current position in a list, as opposed to the list's data.

 

SYS_LIST *pl;
SYS_LIST_POS pos;
VOID *p;
for (pos = NULL; SysListGetNext (pl, &pos, &p); ) {
  // ... do something with p ...
}

 

SysListO
The SysListO container is derived from SysList. But, instead of pointers to arbitrary data, the list contains system objects. When adding objects to the list, a copy is made of the specified object and when delete list entries, the object is deleted. Any object derived from SysObj can be in the list.

The SysListO is a simple, repurposed version of SysList. So, it doesn't need much more than a typedef and a few new library functions that talk about SysObj instead of VOID *. For example:

typedef SYS_LIST SYS_LIST_O;

And here's an example of a  function prototype that uses SYS_OBJ instead of VOID *:

BOOLEAN
SysListOGetNext (
  IN CONST SYS_LIST_O *p,
  IN OUT SYS_LIST_POS *Pos,
  OUT SYS_OBJ **Value
  );

Here are the functions provided by the library for object lists.

• SysListOInit - Initialize object list.
• SysListOEmpty - Empty an object list.
• SysListOAddTail - Add a copy of an object to the end of the list.
• SysListORemoveTail - Remove the last object from the list and return a pointer to it.
• SysListORemoveHead - Remove the first object from the list and return a pointer to it.
• SysListOGetNext - Iterate through all objects in the list, returning a pointer.

Conclusion
So this gives us a real container! Simple, non-invasive and powerful.

Next time, I will introduce how I use these in a real program as two new containers SysStrA (a dynamic ASCII string container) and SysListStrA (a list of ASCII strings) make their appearance in the command-line handling of my UEFI HII parser.

The full source code for the library will be available at the end of this blog series, but if you want more right now, you can see much of the code for SysList in the next section. SysListO is very similar.

The Nitty-Gritty Details

SysListInit - Initialize a List

SYS_LIST *
SysListInit (OUT SYS_LIST *p)
{
  if (SysObjInit (
        &p->Obj,
        SYS_LIST_SIGNATURE,
        sizeof (SYS_LIST),
        (SYS_OBJ_INIT) SysListInit,
        (SYS_OBJ_EMPTY) SysListEmpty,
        NULL,
        (SYS_OBJ_VALID) SysListIsValid,
        NULL) == NULL) {
    SYSINFO ("unable to initialize List container.\n");
    return NULL;
  }
 
  p->Header.Prev = p->Header.Next = &p->Header;
  p->Header.Value = 0;
  return p;
}

SysListEmpty - Empty a List

SYS_LIST *
SysListEmpty (IN OUT SYS_LIST *p)
{
  if (!SysIsValid (p)) {
    SYSINFO ("unable to empty List container.");
    return NULL;
  }
 
  while (!SysListIsEmpty (p)) {    // remove all entries.
    SysListRemoveHead (p);
  }
 
  return p;                         // return pointer to now-empty List container.
}

SysListIsValid - Check whether list is valid  

 

BOOLEAN
SysListIsValid (IN CONST SYS_LIST *p)
{
  if (!SysObjIsValid (&p->Obj, SYS_LIST_SIGNATURE, sizeof (SYS_LIST))) {
    SYSINFO ("invalid List container.\n");
    return FALSE;
  }
 
  return TRUE;
}

SysListAddTail - Add a list entry to the end of the list 

 

BOOLEAN
SysListAddTail (
  IN OUT SYS_LIST *p,
  IN VOID *v
  )
{
  SYS_LIST_ENTRY *e;

  if (!SysListIsValid (p)) {
    SYSINFO ("unable to add tail.\n");
    return FALSE;
  }

  e = malloc (sizeof (SYS_LIST_ENTRY));
  if (e == NULL) {
    SYSINFO ("out of memory.\n");
    return FALSE;
  }

 

  e->Prev = p->Header.Prev;
  e->Next = &p->Header;
  e->Value = v;

  p->Header.Prev->Next = e;
  p->Header.Prev = e;
  return TRUE;
}

 

SysListRemoveTail - Remove last list entry in the list

VOID *
SysListRemoveTail (IN OUT SYS_LIST *p)
{
  SYS_LIST_ENTRY *e;
  VOID *v;
  if (!SysListIsValid (p)) {
    SYSINFO ("unable to remove tail.\n");
    return NULL;
  }
 
  if (SysListIsEmpty (p)) {
    SYSERR ("list is empty. unable to remove List element.\n");
    return NULL;
  }
  e = p->Header.Prev;                // retrieve the tail entry.
  p->Header.Prev->Next = e->Next;    // unlink the tail entry.
  p->Header.Prev = e->Prev;
  v = e->Value;                   // retrieve the value from old tail entry.
  free(e);                           // delete the old tail entry.
  return v;    
}

SysListGetNext - Iterate through list entries
BOOLEAN
SysListGetNext (
  IN CONST SYS_LIST *p,
  IN OUT SYS_LIST_POS *Pos,
  OUT VOID **Value
  )
{
  SYS_LIST_ENTRY *pe;

  if (!SysListIsValid (p)) {
    SYSINFO ("unable to get next element.\n");
    return FALSE;
  }

  if (Pos == NULL) {
    SYSINFO ("invalid list position. unable to get next element\n");
    return FALSE;
  }

  if (*Pos == NULL) {
    *Pos = (SYS_LIST_POS) p->Header.Next;
  }

  pe = (SYS_LIST_ENTRY *)(*Pos);
  if (pe->Next == &p->Header) {
    *Pos = NULL;
  } else {
   *Pos = (SYS_LIST_POS)(pe->Next);
  }

  if (*Pos == NULL) {
    *Value = NULL;
    return FALSE;
  }
  *Value = pe->Value;
  return TRUE;
}