%%s 0/0/0
%%d D 1.1 25-Mar-82 12:15:42 v1.1 1 0
%%c Version 1.1 is the Spring 1982 Distribution of the LBL/Hughes release
%%c of the Software Tools Virtual Operating System software and documentation.
%%T
%%I 1
#-h- ctsort           309  asc  25-mar-82 08:58:49  v1.1 (sw-tools v1.1)
 ## common block for tsort tool
 #  put on a file caled "ctsort"
 #  used only by tsort
 
 common /ctsort/ hash(128), nxtsym, nxtfre, buf(MAXBUF)
   integer hash		# hash table headers
   integer nxtsym	# next symbol structure
   integer nxtfre	# next free word at bottom of buf
   integer buf		# free storage
#-h- tsort.r         5674  asc  25-mar-82 08:58:52  v1.1 (sw-tools v1.1)
#-h- defns            747  asc  25-mar-82 08:58:18  v1.1 (sw-tools v1.1)
 # include ratdef
ifdef(LARGE_ADDRESS_SPACE)
  define(MAXBUF,20000)
elsedef
  define(MAXBUF,5000)     # storage array
enddef
define(MAXSYMBOL,120)   # maximum symbol size
# symbol table entries
define(NEXT,0)          # pointer to next entry
define(SYMBOL,1)        # pointer to symbol structure
define(CHARS,2)         # characters in symbol
# node structure
define(LINK,0)          # pointer to next node
define(SUCC,1)          # pointer to successor symbol structure
define(NODESIZE,2)      # size of node structure
# symbol structure
define(NAME,0)          # symbol structure; pointer to name
define(COUNT,1)         # successor count
define(TOP,2)           # beginning of successor list
define(SYMSIZE,3)       # size of symbol structure

#-h- main             636  asc  25-mar-82 08:58:20  v1.1 (sw-tools v1.1)
 ## tsort - symbolic topoligical sort on symbols
 
 DRIVER(tsort)
 
 integer getarg, open
 integer i, fd
 character arg(FILENAMESIZE)
 
 call query("usage:  tsort [file] ...")
 for (i=1; getarg(i, arg, FILENAMESIZE) != EOF; i=i+1)
        {
        if (arg(1) == '-' & arg(2) == EOS)
                fd = STDIN
        else
                {
                fd = open(arg, READ)
                if (fd == ERR)
                        call cant(arg)
                }
        call tpsort (fd)
        if (fd != STDIN)
                call close(fd)
        }
 if (i == 1)            #read STDIN
        call tpsort (STDIN)
 DRETURN
 end
#-h- tpsort          1513  asc  25-mar-82 08:58:21  v1.1 (sw-tools v1.1)
 ## tpsort - topological sort file 'fd'
 subroutine tpsort (fd)
   character linbuf(MAXLINE), symbuf(MAXSYMBOL)
   integer i, j, f, r, n, fd
   integer getwrd, getlin, looks
   include ctsort

   nxtsym = 1   # initialize
   nxtfre = MAXBUF
   for (i = 1; i <= 128; i = i + 1)
      hash(i) = 0
   while (getlin(linbuf, fd) != EOF) {
      i = 1
      if (getwrd(linbuf, i, symbuf) <= 0)       # ignore blank lines
         next
      j = looks(symbuf)
      while (getwrd(linbuf, i, symbuf) > 0)
         call entprc(j, looks(symbuf))          # insert a relation
      }
   f = 0        # build list of symbols with 0 counts
   for (i = 1; i < nxtsym & f == 0; i = i + SYMSIZE)    # find first 0
      if (buf(i+COUNT) == 0)
         f = i
   for (r = f; i < nxtsym; i = i + SYMSIZE)     # find rest of 0 counts
      if (buf(i+COUNT) == 0) {
         buf(r+COUNT) = i
         r = i
         }
   n = nxtsym   # will be 0 if non-circular
   for (; f > 0; f = buf(f+COUNT)) {    # print in topological order
#      call putlin(buf(buf(f+NAME)), STDOUT)
       call icopys (buf, buf(f+NAME), linbuf, 1)
       call putlin(linbuf, STDOUT)
      call putch('@n', STDOUT)
      for (i = buf(f+TOP); i > 0; i = buf(i+LINK)) {
         j = buf(i+SUCC)
         buf(j+COUNT) = buf(j+COUNT) - 1
         if (buf(j+COUNT) == 0) {       # add more onto list
            buf(r+COUNT) = j
            r = j
            }
         }
      n = n - SYMSIZE
      }
   if (n > 1)
      call error("circular.")
   return
   end
#-h- entprc           270  asc  25-mar-82 08:58:23  v1.1 (sw-tools v1.1)
# entprc - enter the relation a < b
   subroutine entprc(a, b)
   integer a, b
   integer p
   integer nalloc
   include ctsort

   buf(b+COUNT) = buf(b+COUNT) + 1
   p = nalloc(NODESIZE)
   buf(p+LINK) = buf(a+TOP)
   buf(p+SUCC) = b
   buf(a+TOP) = p
   return
   end
#-h- looks            672  asc  25-mar-82 08:58:23  v1.1 (sw-tools v1.1)
 ## looks - lookup symbol s, insert if necessary
   integer function looks(s)
   character s(MAXSYMBOL), lin(MAXSYMBOL)
   integer i
   integer length, nalloc, equal, symalc
   include ctsort

   for (i = hash(s(1)+1); i > 0; i = buf(i+NEXT))
      {
      call icopys (buf, i+CHARS, lin, 1)  # convert from int to char
      if (equal(s, lin) == YES)                 # got it
         return (buf(i+SYMBOL))
     }
   i = nalloc(CHARS + 1 + length(s) + 1)        # must make new entry
   buf(i+NEXT) = hash(s(1)+1)   # add onto proper hash chain
   hash(s(1)+1) = i
   buf(i+SYMBOL) = symalc(i+CHARS)
   call scopyi(s, 1, buf, i + CHARS)
   return (buf(i+SYMBOL))
   end
#-h- nalloc           222  asc  25-mar-82 08:58:25  v1.1 (sw-tools v1.1)
# nalloc - allocate n words in top part of buf
   integer function nalloc(n)
   integer n
   include ctsort

   nxtfre = nxtfre - n
   if (nxtfre < nxtsym)
      call error("out of storage.")
   return (nxtfre + 1)
   end
#-h- symalc           308  asc  25-mar-82 08:58:25  v1.1 (sw-tools v1.1)
# symalc - allocate a symbol structure for symbol s
   integer function symalc(s)
   integer s
   integer p
   include ctsort

   p = nxtsym
   nxtsym = nxtsym + SYMSIZE
   if (nxtsym > nxtfre)
      call error("out of storage.")
   buf(p+NAME) = s
   buf(p+COUNT) = 0
   buf(p+TOP) = 0
   return (p)
   end
#-h- icopys           326  asc  25-mar-82 08:58:26  v1.1 (sw-tools v1.1)
 ## icopys - copy integer string at from(i) to char string at to(j)
    subroutine icopys(from, i, to, j)
    integer from(ARB)
    character to(ARB)
    integer i, j, k1, k2
 
    k2 = j
    for (k1 = i; from(k1) != EOS; k1 = k1 + 1) {
       to(k2) = from(k1)
       k2 = k2 + 1
       }
    to(k2) = EOS
    return
    end
#-h- scopyi           323  asc  25-mar-82 08:58:27  v1.1 (sw-tools v1.1)
 ## scopyi - copy char string at from(i) to integer string to(j)
    subroutine scopyi(from, i, to, j)
    character from(ARB)
    integer to(ARB)
    integer i, j, k1, k2
 
    k2 = j
    for (k1 = i; from(k1) != EOS; k1 = k1 + 1) {
       to(k2) = from(k1)
       k2 = k2 + 1
       }
    to(k2) = EOS
    return
    end
#-h- tsort.fmt       1565  asc  25-mar-82 08:58:56  v1.1 (sw-tools v1.1)
.so ~bin/manhdr
.hd Tsort (1) 1-Oct-78
topologically sort symbols
.sy
tsort [file] ...
.ds
tsort topologically sorts the symbols in the named files.
If no files are specified, or the filename '-' is given,
tsort reads the standard input.
 
A symbol is considered any string of characters delimited
by blanks or tabs.
 
Each line of the input is assumed to be of the form
.sp
.in +3
.nf
a b c ...
.in -3
.sp
.fi
which states that
a
precedes
b, a
precedes
c,
and so on.
Note that there is nothing implied about the ordering of
b
and
c.
A line consisting of a single symbol simply "declares"
that symbol without specifying any ordering relations about it.
The output is a topologically sorted
list of symbols, one per line.
.sp
.fi
For example, suppose you have trouble getting up in the morning
because you can't quite remember what actions have to be
performed in which order.
However, you do know that the first action in the following
list precedes all others on the line:
 
.in +5
.nf
set_alarm   turn_off_alarm
wake_up    get_out_of_bed    turn_off_alarm
set_alarm     wake_up
.in -5
.fi
 
Using tsort to sort the above list would produce the following
set of actions for getting out of bed:
 
.in +5
.nf
set_alarm
wake_up
turn_off_alarm
get_out_of_bed
.fi
.in -5
.di
circular
.br
.in +3
The input specifies a graph that contains at least one cycle.
.in -3
.sp
out of storage
.br
.in +3
The input is too large.
The size of tsort's buffer is determined by the MAXBUF
definition in the source code.
.in -3
.sa
sort
.au
David Hanson and friends (U. of Arizona)
.bu
%%E 1