Traverse multi-linked list?

Question

I am creating a tool for a closed-source program. after debugging I have the base address of the structure I want to access. And after close inspection I see it's a multi-linked list, of where the first 3 integers are pointers, and all the other values are data.

I have managed to reconstruct this structure from my analysis:

struct UnitsInfo
{
    //pointers to UnitsInfo structures, null when no structure available at that location
    DWORD * a;//0x00
    DWORD * b;//0x04
    DWORD * c;//0x08

    //data
    int unkown_1;       //0x0C
    unsigned int Type;  //0x10
    unsigned int Amount;//ox14
};
UnitsInfo * Base_Node = ((UnitsInfo*)( (*(DWORD*)( (*(DWORD*)(0x00400000+0x008E98EC)) + 0x38)) + 0x0C);

Now, I am really new to linked-structures, let alone multi-linked structures.

What I was thinking is making a map and bruteforcing until I have all adresses. (infinite loop possible)?

But I know this is not the way to traverse this linked list. How could I efficiently, without knowing how it's connected, traverse all nodes in this multi linked list (and avoid the ones I already had)?

---

Edit: Thanks to the answers I have finally made it!

Here is my code, may come handy for other people?

#define MAX_PLAYERS (6)
#define POINTER(type,addr) (*(type*)(addr))

struct UnitsInfo
{
    //pointers to UnitsInfo structures, null when no structure available at that location
    DWORD * nodes[3];//0x00

    //data
    int unkown_1;       //0x0C
    unsigned int Type;  //0x10
    unsigned int Amount;//ox14
};

struct pinfo
{
    bool            in;
    enum Controller {Ctrl_UNKNOWN,  Ctrl_HUMAN, Ctrl_AI             };
    enum Nation     {N_UNKNOWN,     N_ALLIES,   N_SOVIET,   N_JAPAN };
    std::string     Name;
    Nation          Side;
    short           Team;
    Controller      Who;
    int             *Money;
    int             *Power;
    int             *Usage;
    unsigned int    *Color;

    bool            GotUnits;
    DWORD           *unit_start_node;
};

std::map<DWORD*,UnitsInfo*> UnitList[MAX_PLAYERS];
void GenerateUnitList(unsigned short slot)
{
    std::set<DWORD*> todo;
    unsigned int inserted = 1;
    while(inserted)
    {
        inserted = 0;
        for(auto it = UnitList[slot].begin(); it != UnitList[slot].end(); ++it)
        {
            for(short i = 0; i < 3; ++i)
            {
                if(it->second->nodes[i] != NULL)
                {
                    if(UnitList[slot].find(it->second->nodes[i]) == UnitList[slot].end())
                    {
                        todo.insert(it->second->nodes[i]);
                        ++inserted;
                    }
                }
            }
        }
        while(!todo.empty())
        {
            UnitList[slot][*todo.begin()] = &POINTER(UnitsInfo,*todo.begin());
            todo.erase(todo.begin());
        }
    }
}

pinfo Player[MAX_PLAYERS];

//adding the first node
unsigned int CurrentSlot = (0xD8+(0x4*slot));
if(POINTER(DWORD,POINTER(DWORD,0x00400000+0x008E98EC)+CurrentSlot) != NULL)
{
    Player[slot].unit_start_node = &POINTER(DWORD,POINTER(DWORD,POINTER(DWORD,POINTER(DWORD,0x00400000+0x008E98EC)+CurrentSlot) + 0x38) + 0x0C);
}

//adding first unit if available, if yes continue generating list
if(!Player[i].GotUnits)
{
    if(POINTER(DWORD,*Player[i].unit_start_node+0x10) != NULL)
    {
        Player[i].GotUnits = true;
        UnitList[i][(Player[i].unit_start_node)] = &POINTER(UnitsInfo,*Player[i].unit_start_node);
    }
}
else
{
    GenerateUnitList(i);
}

And the best of all is, it works like a charm and doesn't lagg :)

Answer 1

BFS and DFS are the first ones coming into mind:

• Depth first search (see: http://en.wikipedia.org/wiki/Depth-first_search)

• Breadth first search (see: http://en.wikipedia.org/wiki/Breadth-first_search)

Both of them are commonly used to traverse a graph. Loops in the link structure will be detected in bost cases, so if implemented right there is no risk of an infinite loop.

Basically speaking both methods work by (at least at the conceptual level) marking any inspected nodes while keeping any unvisited nodes seen so far in some kind of list.

While breadth first traversal will keep nodes in a Queue handling nodes in some kind of a FIFO manner depth first traversal will push new nodes onto a Stack thus visiting newly discovered nodes first.

One of the most easiest ways to implement depth first traversal works even without having to implement a stack as by recursively calling itself it just (miss)uses the call stack of the program to keep track of the places still to visit.

Example

Suppose the nodes of the graph you want to traverse have something like the following structure:

struct Node {
  int visited;
  struct Node **edges;

  void *some_data;
}

With edges being a NULL terminated array of links leading to another node. Starting from any node of your choice. You basically just call a single function maybe called visit and you are done:

void visit (struct Node *node) {
  struct Node *n;

  node->visited = 1;    

  for (n=node->edges; *n!=NULL; ++n)
    if (!(*n)->visited)
      visit (*n, depth+1);
}

Of course you'll still have to do something useful with each visited node. But in order to visit all nodes reachable from your starting node without running in circles this is already everything that has to be done.

Complete Example

Here an attempt to provide you with a full working example. After some effortles tries I think I came up with a relatively nice graph showing different pathes chosen.

I tried to paint it down in the comment line below:

#include <stdio.h>

struct Node {
  int visited;
  int id;
  struct Node **edges;
};

/* recursively visit this node and all unvisited nodes
   reachable from here */

void visit (struct Node *node, int depth) {
  struct Node **n;
  node->visited = 1;

  /* show the node id surrounded with '[' ']' characters
     to indicate this node has been visited in the output */

  printf ("[%d]\n", node->id);

  for (n=node->edges; *n!=NULL; ++n) {

    /* indent this line according the depth that has
       been reached in recursion and show the id
       of the reachable node currently inspected */
    printf ("%*s %d ", 5*depth, "", (*n)->id);
    if (!(*n)->visited) {
      /* indicate the search goes down one recursion level
         by drawing a '=>' next to the node id */
      printf ("=>");
      visit (*n, depth+1);
    }
    else
      printf ("\n");
  }
}
int main (int argc, char *argv[]) {

  /*  This is the graph that will be modeled and traversed

             +----+
            v      \
       + -- 0 -+    \
      /    ^    \    |
      |   /      v  /
      v  /       2 - 
       1-        ^ \
       \       /    v
        +---> 3     4
   */


  struct Node v[5]; /* These will form the vertices of the graph */

  / * These will be the edges */
  struct Node *e[][5] = {
    {v+1, v+2, NULL},
    {v+0, v+3, NULL},
    {v+0, v+4, NULL},
    {v+2, NULL},
    { NULL}
  };

  /* initialize graph */
  int i;
  for (i=0; i<5; ++i) {
    v[i].id = i;
    v[i].visited = 0;
    v[i].edges=e[i];
  }


  /* starting with each vertex in turn traverse the graph */
  int j;
  for (j=0; j<5; ++j) {
    visit (v+j, 0);
    printf ("---\n");

    /* reset the visited flags before the 
       next round starts */ 
    for (i=0; i<5; ++i)
      v[i].visited = 0;
  }

  return 0;
}

The output will in some more or less cryptic manner show the algorithm jumping back and forth during recursion.

Output

Depending on the starting node you will get different results. Starting from node 4 for example there won't be any other node found, as there is not path leading away from there.

Here the output with starting nodes ranging from 0 to 4. Nodes visited will be surrounded by [ ] characters those not visited because they have already been inspected are drawn without border instead.

I hope the example will help to see how and why the algorithm works.

[0]
 1 =>[1]
      0 
      3 =>[3]
           2 =>[2]
                0 
                4 =>[4]
 2 
---
[1]
 0 =>[0]
      1 
      2 =>[2]
           0 
           4 =>[4]
 3 =>[3]
      2 
---
[2]
 0 =>[0]
      1 =>[1]
           0 
           3 =>[3]
                2 
      2 
 4 =>[4]
---
[3]
 2 =>[2]
      0 =>[0]
           1 =>[1]
                0 
                3 
           2 
      4 =>[4]
---
[4]
---

Answer 2

What I was thinking is making a map and bruteforcing until I have all adresses. (infinite loop possible)?

On the whole, I think this is workable. All you need is a set of addresses you've already processed, and a set of addresses to process. Whenever you encounter an address not in either set, you add it to the "todo" set. You keep processing addresses in the "todo" set (and moving them to the "done" set) until the former becomes empty.