[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Graeme Russ]

Hi Wolfgang, Detlev

> But, tsort works on paired entries, while INIT_FUNC allows functions to
> have multiple dependencies. So to use tsort, I will need to process the
> list to produce entry pairs - That should be a pretty simple operation.

Well the solution appears to be trivial anyway:

http://www.algorithmist.com/index.php/Topological_sort

for each init_functions list entry {
  Check all functions which are a mandatory dependency on any other
      function exist (already done)

  Strip from pre-deps and post-deps all functions which do not have an
      INIT_FUNC entry

  Move all entries from mandatory_deps into pre_deps

  Convert all post_dep entries into corresponding pre_dep entries
}

while (init_functions list is non-empty) {

  if (no init_functions entry has an empty pre_deps) {
    Fail - cyclic dependencies
  }

  Get first entry in init_functions where pre_deps list is empty

  Add init_functions.function_name to final list

  for each init_functions list entry {
    remove init_functions.function_name from pre_deps list
  }

  remove entry from init_functions list
}

so I don't need to reduce the entries down to a list of pairs and the
sorting function will probably be one of the smaller components of the
whole thing

Regards,

Graeme