[crossposting to tech-userlevel because of twalk(3)]

> On Jul 21, 2006, at 5:15 AM, Jachym Holecek wrote:
>>   * Change names as per chap's comment (s/DIF_TOPDOWN/DIF_PREORDER,
>>     s/DIF_DOWNTOP/DIF_POSTORDER).

So I've just been reminded of a confusion on these terms that
unfortunately is built into POSIX.  There should be no need to change
this API (the terms are used correctly here) but it would be a good
idea for its documentation to have a caveat crossreferencing twalk(3)
and pointing out the issue.

The issue is that twalk(3) uses postorder to mean inorder, and uses
"endorder" to mean postorder. That usage appeared in the very first
edition of _The Art of Computer Programming_ vol 1 and was corrected
by Knuth for the second edition in 1973.

Although no change to the device tree API seems warranted, we do have
at least doc issues with twalk:

1.  Our tsearch.3 lacks the usual paragraph from SUS and most vendors'
    man pages that warns of the terminology confusion. It's important
    to have that.  As we recently got permission to incorporate the
    POSIX language, it should not be a problem to add.

    [IMO, the POSIX language is too equivocal: instead of talking
    about, um, mumble, alternative nomenclature, it would be better
    to just say twalk clings to a usage corrected in 1973 in TAOCP,
    and that this not MAY but DOES confuse the meaning of postorder.]

2.  tsearch.3 is actually in even worse shape than that: from our
    current language it's actually not possible at all to deduce
    correctly what the twalk function does. Perhaps the best fix is
    just to import the POSIX language wholesale.

3.  Though it might be more controversial, it seems to me that a more
    forward-looking approach to the twalk issue could look something
    like this:

search.h:

  typedef enum {
          preorder,
+         visit_preorder = preorder,
          postorder,
+         visit_inorder = postorder,
          endorder,
+         visit_postorder = endorder,
          leaf
+         ,visit_leaf = leaf
  } VISIT;

The man page could be reworked to describe the behavior exclusively in
terms of the visit_* constants, with a note that the constants without
the visit_ prefix exist to support old code using a deprecated nomenclature.

It might take forever to get such a change upstream into POSIX, but at
least it would offer a way to write code for twalk that wouldn't have
to perpetuate a 30 year old confusion of basic data structure terms....

-Chap