This file is a concatenation (for Netlib purposes) of eight
source files:

          dominoport.c
          domdec.h
          domparam.h
          domstruct.h
          domdefault.c
          spproface.c
          boot.c
          brigade.c

They should be split up after receipt at the places marked by lines
of the form

     #     SPLIT HERE     FILENAME =  <filename>                 #

                

#     SPLIT HERE     FILENAME =  dominoport.c               #


/* 
     DOMINO:accept.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"

/*
   accept is called by PROFACE or sendn to transfer an incoming
   message.  The message is brought in item by item, and accept
   determines its actions from the information in the message.
   In fact once a transfer is initiated, accept drives PROFACE
   by returning MORE to request another item or DONE to signal
   that the message has been processed.

   The zero item of the message is a message type, which can be
   SENDN or SENDP. The remaining items depend on the message type.

      1. SENDN:

         This type of message is placed on the destination
         node's in-queue for later processing by ready.
         The message items have the following
         interpretation.

            1. The originating processor.

            2. The index of the originating node.

            3. The length of the originating node name.

            4. The originating node name.

            5. The index of the destination node.

            6. The length of the destination node name.

            7. The destination node name.

            8. The length n of the message (i.e., the number
               of items following this one).

         If the system flag noname is set items 3, 4, 6, and
         7 are not transmitted.

      2. SENDP

         This type of message is passed directly to memory
         beginning in a location pointed to by the second
         data item.  The items have the following meaning.

            1. A pointer to where the data is to be placed.

            2. The length n of the message

            3. Message data.

            4. End of message flag.

         Message items are placed in memory by the PROFACE
         entry

                   accburst(&pointer, &n, item)

         which increases the pointer and decreases n by one
         for each item transferred.  accburst will attempt
         to transfer the entire message in burst mode.  If
         it succeeds it will return with n equal to zero.

         If the end of message flag is FALSE, accept remains
         in burst mode, and expects another message.

*/

extern int accburst();              /* Transfers data to memory, pos-   */
                                    /* in burst mode.  See the descrip- */
                                    /* tion of SENDP above.             */
extern struct qentry *addq(),       /* Adds a message to a queue        */
                     *queuep();     /* Returns a new qentry             */
extern struct listentry *listp();   /* Returns a new list entry         */
extern int error();                 /* Error routine                    */
extern int match();                 /* Determines if nodeids match      */
extern int freelist();              /* Returns linked list to pool      */

accept(item)
int item;                           /* Current item in message           */
{
   static int type,                 /* Type of message                   */
              *pointer,             /* Pointer to where to load the      */
                                    /* message                           */
              meslen,               /* The length of the message         */
              m, n,                 /* Indices                           */
              mtch;                 /* True if a match is found          */
   static struct qentry *tail,      /* Pointer to the queue entry to be  */
                                    /* appended to the destination       */
                                    /* node's in queue                   */
                        *destent;   /* Pointer to the destination entry  */
                                    /* for the save queue                */
   static struct listentry *lp;     /* Used in constructing lists        */
   static struct nodeid dest;       /* Destination node id               */

   if (itemno == 0){ /* Beginning of a new message. */
      type = item;
   }

   /* Branch to the appropriate type of transmission. */

   switch (type){

      case SENDN:

         if (itemno < 9){

            switch (itemno){

               case 0: /* Get a qpool entry. */

                  tail = queuep(11);
                  itemno = 1;
                  return(MORE);

               case 1: /* Source processor */

                  tail->node.processor = item;
                  itemno = 2;
                  return(MORE);

               case 2: /* Source index */

                  tail->node.index = item;
                  itemno = noname ? 5 : 3;
                  return(MORE);

               case 3: /* Source name length */

                  if (item == 0){
                     tail->node.name = NULL;
                     itemno = 5;
                  }
                  else{
                     n = item;
                     lp = listp(12);
                     tail->node.name = lp;
                     itemno = 4;
                  }
                  return(MORE);

               case 4: /* Source name */

                  lp->item = item;
                  if (--n > 0){
                     lp->nextent = listp(12);
                     lp = lp->nextent;
                  }
                  else{
                     lp->nextent = NULL;
                     itemno = 5;
                  }
                  return(MORE);

               case 5: /* Destination index */

                  dest.processor = selfaddr;
                  dest.index = item;
                  itemno = noname ? 8 : 6;
                  return(MORE);

               case 6: /* Destination name length */

                  if (item == 0){
                     dest.name = NULL;
                     itemno = 8;
                  }
                  else{
                     n = item;
                     lp = listp(12);
                     dest.name = lp;
                     itemno = 7;
                  }
                  return(MORE);

               case 7: /* Destination name */

                  lp->item = item;
                  if (--n > 0){
                     lp->nextent = listp(12);
                     lp = lp->nextent;
                  }
                  else{
                     lp->nextent = NULL;
                     itemno = 8;
                  }
                  return(MORE);

               case 8: /* Message length */

                  meslen = n = item;
                  itemno = 9;
                  if (meslen == 0)
                     tail->mesp = NULL;
                  else{
                     lp = listp(12);
                     tail->mesp = lp;
                     return(MORE);
                  }
            }
         }

         if (meslen != 0){
            lp->item = item;
            if (--n > 0){
               lp->nextent = listp(12);
               lp = lp->nextent;
               return(MORE);
            }
            else
               lp->nextent = NULL;
         }
         
         if (dest.index < 0){
            if (-dest.index > NUTNODES)
               error(13);
            addq(&utnode[-dest.index].inq, tail);
            itemno = 0;
            return(DONE);
         }

         mtch = FALSE;

         if ((n=dest.index) < nnodes)
            for (m=0; m<nnodes; m++){
               if (mtch = match(&node[n]->id, &dest)) break;
               n = n++<nnodes ? n : 0;
            }

         if (mtch){
            addq(&node[n]->inq, tail);
            if (!noname) freelist(dest.name);
         }
         else{
            destent = queuep(11);
            destent->node.processor = dest.processor;
            destent->node.index = dest.index;
            destent->node.name = dest.name;
            addq(&saveq, destent);
            addq(&saveq, tail);
         }
         itemno = 0;
         return (DONE);

      case SENDP:

         receiving = TRUE;
         switch (itemno){

            case 0:

               itemno = 1;
               return(MORE);

            case 1: /* The item is the pointer. */

               pointer = (int *) item;
               itemno = 2;
               return(MORE);

            case 2: /* The item is the message length. */

               n = item;
               itemno = n==0 ? 4 : 3;
               return(MORE);

            case 3: /* The item is a datum.  Transfer it. */

               accburst(&pointer, &n, item);
               if (n == 0) itemno = 4;
               return(MORE);

            case 4: /* The item is an end of message flag. */

               if (item){
                  itemno = 0;
                  receiving = FALSE;
                  return(DONE);
               }
               else{
                  itemno = 1;
                  return(MORE);
               } 
         }

      default:

         error(14);
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:addq.c                                 DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   addq appends the qentry pointed to by qent to the
   queue specified by qpointers.  If qent is null, addq
   obtains an entry from the queue pool.  addq returns
   a pointer to the entry just added.  inoff should be
   called before calling addq.
*/

extern int error();                 /* Error routine                    */

struct qentry *addq(qpointers, qent)
struct qpointers *qpointers; 
struct qentry *qent;    
{
   if (qent == NULL){
      if (qpoolp == NULL) error(21);
      qent = qpoolp;
      qpoolp = qpoolp->nextent;
   }
   qent->nextent = NULL;
   if (qpointers->tail != NULL) qpointers->tail->nextent = qent;
   qpointers->tail = qent;
   if (qpointers->head == NULL) qpointers->head = qent;
   return(qent);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:cleanup.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   cleanup frees the inq and wantq of the node pointed to
   by node, returning the entries to the qpool and all names
   and messages on the wantq to the listpool.  inoff must
   have been called before calling cleanup.
*/

extern int freelist();              /* Returns linked list to pool      */
extern struct qentry *removeq();    /* Remove element from linked list  */

cleanup(node)
struct node *node;  
{
   while (node->inq.head != NULL){
      if(!noname) freelist(node->inq.head->node.name);
      freelist(node->inq.head->mesp);
      removeq(node->inq.head, NULL, &node->inq);
   }
   while (node->wantq.head != NULL)
                removeq(node->wantq.head, NULL, &node->wantq);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:cmcheck.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   cmcheck is called by control to respond to control messages.
   In this implementation of DOMINO there are four control
   messages: a general purpose message, which does nothing;
   a restart message, which restarts the system; a halt
   message, which causes activity to cease until another control
   message, is received and a toggle message, which switches the
   system back and forth between user and executive modes.
*/

extern int conmes();                /* Returns control message, if      */
                                    /* any                              */
extern int error();                 /* Error routine                    */

cmcheck()
{
   int ndx;                        /* Node index                    */
   static struct node *oldnodep;   /* Pointer to the user node that */
                                   /* was current before a toggle.  */

   /* If there was no control message, return */

   if (cm==0) cm = conmes();
   if (cm==0) return(CONTINUE);
   switch (cm){
      case GENERAL_PURPOSE:

         /* Do nothing. */

         cm = 0;
         return(CONTINUE);
      case RESTART:

         /* Wait for another message before reinitializing. */

         cm = 0;
         while(!conmes());
         return(START);
      case HALT:

         /* Wait for another message before starting things
         up again */

         cm = 0;
         while(!conmes());
         if (hung){
            hung = FALSE;
            return(AWAKEN);
         }
         else
            return(CONTINUE);
      case TOGGLE:

         /* Change modes. */

         cm = 0;
         if (mode==USER){
            /* Change to executive mode. */

            mode = EXECUTIVE;
            oldnodep = nownodep;   /* Save the current user node */

            /* Restore all detached executive nodes to active status. */

            for (ndx=0; ndx<nnodes; ndx++)
               if (node[ndx]->class==EXECUTIVE &&
                               node[ndx]->status==DETACHED)
                  node[ndx]->status = READY;
            execstart = TRUE;
            return(CONTINUE);
         }
         else{
            /* Change to user mode. */

            mode = USER;
            nownodep = oldnodep;    /* Restore the current user node. */
            if (hung){
               hung = FALSE;
               return(AWAKEN);
            }
            else
               return(CONTINUE);
         otherwise:

            error(31);
            return(CONTINUE);
         }
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:conmes.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   conmes returns the value of cmes, resetting it if non-zero.
   It would be better to put control messages on a queue,
   allowing new control messages to arrive before old ones
   have been acknowledged.
*/

int cmes = 0;           /* Set when control message   */
                        /* arrives.                   */

conmes(){
   int temp;     
   if (!cmes) 
      return(0);
   else {
      temp = cmes;
      cmes = 0;
      return(temp);
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:control.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   Control does three things.  It initializes DOMINO by calling
   startup.  It loops awakening nodes as they become ready.  And
   it responds to control interrupts by continuing normally,
   by restarting DOMINO, or by awakening a hung node.
*/

extern int startup();               /* DOMINO initialization routine    */
extern int conmes();                /* Returns control message, if      */
                                    /* any                              */
extern int cmcheck();               /* Checks control message           */
extern struct node *schedule();     /* Scheduling routine               */
extern int awaken();                /* Awaken current node              */
extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */

control()
{
   /* Initialize by calling startup. */

strt:
   startup();

   /* Main loop in which nodes are awakened. */

   while (TRUE){

      /* If there is a ready node and no control message, then
      awaken the node. */

      if ((nownodep=schedule()) != NULL){
         if (!(cm=conmes()) || nownodep->class==UTILITY){
awkn:       initial = nownodep->status==READY;
            awaken(nownodep);
            if (nownodep->status == DETACHED){
               inoff();
                  cleanup(nownodep);
               inon(TRUE);
            }
         }
         else /* User node interrupted by control message*/
            if (nownodep->class == USER) hung = TRUE;
      }

      /* Check control message and act accordingly. */

      switch (cmcheck()){
         case CONTINUE: break;
         case START: goto strt;
         case AWAKEN: goto awkn;
      }
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:data.c                                 DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

extern int match();                 /* Determines if nodeids match      */

/* 
   getdata returns a pointer to the the auxiliary storage of
   the data node whose id matches the one pointed to by name.
*/

*getdata(name)
struct nodeid *name;
{
   int i;
   for (i=0; i<nnodes; i++)
      if (node[i]->class==DATA && match(name, &node[i]->id))
         return(node[i]->auxp);
   return(NULL);
}

/*
   lockdata returns a pointer to the the auxiliary storage of
   the data node whose id matches the one pointed to by name,
   profided its status is not DETACHED.  It sets the status
   to DETACHED.
*/

*lockdata(name)
struct nodeid *name;
{
   int i;
   for (i=0; i<nnodes; i++)
      if (node[i]->class==DATA && match(name, &node[i]->id))
         if (node[i]->status == DETACHED)
            return(NULL);
         else{
            node[i]->status = DETACHED;
            return(node[i]->auxp);
         }
   return(NULL);
}

/*
   freedata frees a data node by setting its status to READY.
*/

freedata(name)
struct nodeid *name;
{
   int i;
   for (i=0; i<nnodes; i++)
      if (node[i]->class==DATA && match(name, &node[i]->id)){
         node[i]->status = READY;
         return;
      }
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:domdefs.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
*/

int initial = 0;                   /* Initialization flag (TRUE   */
                                   /* or FALSE                    */
int nqents = 0;                    /* Number of entries in the    */
                                   /* queue pool.                 */
int nlents = 0;                    /* Number of entries in the    */
                                   /* list pool.                  */
int goauxsize = 0;                 /* Size of the go node's       */
                                   /* auxiliary storage           */
int gostksize = 0;                 /* Size of the go node's stack */
int noname = 0;                    /* A flag supressing the       */
                                   /* naming of nodes             */
struct qentry q0[3] = {0};         /* Initial qpool               */
struct node utnode[NUTNODES+1] = 0;/* Utility node table          */
int syssp = 0;                     /* System stack pointer        */
int hardc = 0;                     /* Hard control message flag   */
                                   /* (TRUE or FALSE)             */
int cm = 0;                        /* Current control message     */
                                   /* (GENERAL_PURPOSE, RESTART,  */
                                   /* HALT, TOGGLE)               */
int itemno = 0;                    /* Number of current item in   */
                                   /* an incoming message         */
int sending = FALSE;               /* A flag indicating whether   */
                                   /* PROFACE is transmitting a   */
                                   /* message                     */
int receiving = FALSE;             /* A flag indicating whether   */
                                   /* accept is receiving in      */
                                   /* burst mode.                 */
int mode = 0;                      /* Mode of execution (USER or  */
                                   /* EXECUTIVE)                  */
int hung = FALSE;                  /* Hung node flag (TRUE or     */
                                   /* FALSE)                      */
int userstart = FALSE;             /* Restart scheduling of user  */
                                   /* nodes (TRUE or FALSE)       */
int execstart = FALSE;             /* Restart scheduling of exec- */
                                   /* utive nodes (TRUE or FALSE) */
struct node *nownodep = 0;         /* Pointer to the currently    */
                                   /* executing node              */
int selfaddr = 0;                  /* Address of the processor    */
struct qentry *qpoolp = 0;         /* Pointer to available queue  */
                                   /*  entry                      */
struct qpointers saveq = 0;        /* Pointers for the queue to   */
                                   /* save unmatched messages     */
struct listentry *lpoolp = 0;      /* Pointer to available message*/
                                   /* entry                       */
int nnodes = 0;                    /* Number of nodes             */
int storex = 0;                    /* Current top of storage      */
struct node *node[NTSIZE] = {0};   /* The node table              */
int store[STORSIZE] = {0};         /* Common storage              */


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:freelist.c                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   freelist returns list pointed to by l to the listpool.
   inoff should be called before calling freelist.
*/

freelist(l)
struct listentry *l;
{
   struct listentry *temp;

   if ((temp = l) == NULL) return;
   while (temp->nextent != NULL) temp = temp->nextent;
   temp->nextent = lpoolp;
   lpoolp = l;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:killnodes.c                            DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   killnodes removes all the nodes from the end of the
   node table beginning with the one which index is index.
   All names and qentries are returned to their pools.
*/

extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */
extern int freelist();              /* Returns linked list to pool      */
extern int cleanup();               /* Returns linked lists associated  */
                                    /* with node (inq and wantq)        */

killnodes(index)
int index;
{
   int i;
   if (index >= nnodes) return;
   inoff();
      for (i=index; i<nnodes; i++){
         if (!noname) freelist(node[i]->id.name);
         cleanup(node[i]);
      }
      storex = (int *) node[index] - store;
      nnodes = index;
   inon(TRUE);
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:listp.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   listp returns a list entry.  If none is available,
   it attempts to obtain one by delivering messages.  If
   there is still no entry, listp passes the error message
   errmes to the error routine.  inoff must have been called
   before calling listp.  In future listp will be changed
   to have two arguments: listp(n, errmes), and will return
   n list entries.
*/

extern int sweep();                 /* match as many entries on inq's   */
                                    /* and wantq's as possible          */
extern int error();                 /* Error routine                    */

struct listentry *listp(errmes)
int errmes;
{
   struct listentry *temp;
   if (lpoolp == NULL){
      sweep();
      if (lpoolp == NULL) error(errmes);
   }
   temp = lpoolp;
   lpoolp = temp->nextent;
   return(temp);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:main.c                                 DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   main consists of a call to the DOMINO control routine.
*/

extern int control();               /* DOMINO control routine           */

main()
{
   control();
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:makeid.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   makeid creates a node id in memory pointed to by idp,
   Amount of memory used equals 3+namesize*2 integers.
   proc and index equal the processor address and node
   table index of id.  A linked list is created 
   containing nodename indicated by integer array name
   of size namesize.
*/
            
makeid(proc, index, namesize, name, idp)
int proc, index, namesize, *name;
struct nodeid *idp;
{
   struct listentry *temp;

   idp->processor = proc;
   idp->index     = index;
   idp->name = (namesize) ? (temp = (struct listentry *) (idp+1)) : NULL;  

   while (namesize>0){
      temp->item = *name++;
      temp->nextent = (--namesize) ? (temp+1) : NULL;
      temp++;
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:makenode.c                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   makenode places a node on the node table.  The class of
   the new node is specified by class, and must be USER,
   EXECUTIVE, or DATA.  A node id is constructed from
   the array name, which has namesize entries.  The
   node program is specified by program and the sizes
   of the auxiliary storage and the stack by auxsize
   and stacksize.  If there are any pending messages for
   the node on the saveq, they are placed on its inq.
*/

extern int error();                 /* Error routine                    */
extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */
extern int match();                 /* Determines if nodeids match      */
extern int freelist();              /* Returns linked list to pool      */
extern struct qentry *removeq();    /* Remove element from linked list  */
extern struct qentry *addq();       /* Adds a message to a queue        */

makenode(class, namesize, name, program, auxsize, stacksize)
int class, namesize, *name, (*program)(), auxsize, stacksize;
{
   int i, newx;                  /* indices                     */
   struct node *nd;              /* points to new node def      */
   struct listentry *np;         /* used to copy name           */
   struct qentry *sqp, *lastsqp; /* used to find messages which */
                                 /* already arrived             */

   /* Check for overflow. */

   if (nnodes >= NTSIZE) error(41);
   if ((newx=storex+NODESIZE+auxsize+stacksize)>=STORSIZE) error(42);

   /* Initialize the node */

   node[nnodes] = nd = (struct node *) &store[storex];
   if (!(class==USER || class==EXECUTIVE || class==DATA)) error(43);
   nd->class = class;
   nd->status = READY;
   nd->id.processor = selfaddr;
   nd->id.index = nnodes;
   nd->id.name = NULL;
   if (!noname && namesize>0){
      if(namesize > MAXNAME) error(44);
      nd->id.name = np = listp(45);
      for (i=1; i<namesize; i++){
         np->item = *name++;
         np->nextent = listp(45);
         np = np->nextent;
      }
      np->item = *name;
      np->nextent = NULL;
   }
   nd->program = program;
   nd->auxp = &store[storex + NODESIZE];
   nd->stacktop = nd->stackbot = &store[newx - 1];
   nd->inq.head = NULL;
   nd->inq.tail = NULL;
   nd->wantq.head = NULL;
   nd->wantq.tail = NULL;

   /* Place any messages for the node on its inqueue. */

   sqp = saveq.head;
   lastsqp = NULL;
   inoff();
      while (sqp != NULL){
         if (match(&sqp->node, &nd->id)){
            freelist(sqp->node.name);
            sqp = removeq(sqp, lastsqp, &saveq);
            sqp = removeq(sqp, lastsqp, &saveq);
            addq(&nd->inq, NULL);
         }
         else{
            lastsqp = sqp->nextent;
            sqp = lastsqp->nextent;
         }
      }
      storex = newx;
      nnodes++;
   inon(TRUE);
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:makeutnd.c                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   makeutnd makes several entries on the utility node table.
   This particular makeutnd routine creates a boot node, which
   is used to boot DOMINO, and a pass node, used to relay 
   messages between processors which are not connected.
*/

int stack1[300] = 0;           /* space from which the boot node */
                               /* stack and aux are created      */
int stack2[100] = 0;           /* space from which the pass node */
                               /* stack and aux are created      */
extern int boot(),             /* boot node program              */
           passn();            /* pass node program              */

makeutnd()
{
   utnode[1].class = UTILITY;
   utnode[1].status = READY;
   utnode[1].id.processor = selfaddr;
   utnode[1].id.index = -1;
   utnode[1].id.name = NULL;
   utnode[1].program = boot;
   utnode[1].auxp = NULL;
   utnode[1].stacktop = utnode[1].stackbot = &stack1[299];
   utnode[1].inq.head = NULL;
   utnode[1].inq.tail = NULL;
   utnode[1].wantq.head = NULL;
   utnode[1].wantq.tail = NULL;

   utnode[2].class = UTILITY;
   utnode[2].status = READY;
   utnode[2].id.processor = selfaddr;
   utnode[2].id.index = -2;
   utnode[2].id.name = NULL;
   utnode[2].program = passn;
   utnode[2].auxp = NULL;
   utnode[2].stacktop = utnode[2].stackbot = &stack2[99];
   utnode[2].inq.head = NULL;
   utnode[2].inq.tail = NULL;
   utnode[2].wantq.head = NULL;
   utnode[2].wantq.tail = NULL;

   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:match.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   match determines whether the nodeids pointed to by id1 and
   id2 match.  The rules are as follows.

        1. If the processor field of either of the ids
           is negative, there is a match.

        2. Otherwise, if the name field of both ids are
           null and the processor and index fields are
           equal, there is a match.

        3. Otherwise, if the processors and names of 
           both ids are equal, there is a match.

        4. Otherwise, there is no match.

*/

match(id1, id2)
struct nodeid *id1, *id2;
{
   struct listentry *np1, *np2;  /* used to match names  */

   if (id1->processor<0 || id2->processor<0) return(TRUE);
   if (id1->processor != id2->processor) return(FALSE);

   if (noname || (id1->name==NULL && id2->name==NULL)){
      if (id1->index != id2->index) return(FALSE);
      return(TRUE);
   }

   np1 = id1->name;
   np2 = id2->name;
   while (np1!=NULL && np2!=NULL){
      if (np1->item != np2->item) return(FALSE);
      np1 = np1->nextent;
      np2 = np2->nextent;
   }
   if (np1 == np2)
      return(TRUE);
   else
      return(FALSE);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:passn.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   passn is the node program for the pass (utility) node.
   The pass node takes message from any other node. When
   it arrives, buf[1] indicates the processor for which
   message is intended.  If buf[1] == selfaddr,  the
   accept routine is called with the contents of buf,
   simulating a message arriving from the node which
   originated the message using sendrn. Otherwise the
   message is relayed to the pass node on the next
   processor on the path to the destination, as
   defined by nextproc. See also sendrn.
*/

extern int infree();                /* Wait until current inbound       */
                                    /* has been consumed by accept      */
extern int inon();                  /* End critical section             */
extern int accept();                /* Processes current message item   */
extern int nextproc();              /* Returns next processor id in     */
                                    /* chain to destination processor   */
extern int makeid();                /* Create nodeid                    */
extern int pause();                 /* Return to control until node is  */
                                    /* ready to be reawakened           */
extern int request();               /* Request data from another node   */
extern int sendn();                 /* Send data to another node        */

passn(nd, sysp)
struct node *nd;           /* pointer to boot node        */
int *sysp;                 /* pointer to system var's     */
{
   int anyone[3],          /* node id for "any node"      */
       pass[3],            /* node id of pass node on     */
                           /* next processor              */
       buf[PNBUFSIZE],     /* message buffer              */
       i;                  /* index                       */
   makeid(-1, 0, 0, NULL, anyone);
   makeid( 0, -2, 0, NULL, pass);
   while(TRUE){
      request(anyone, buf);
      pause();
      if (selfaddr == buf[1]){
         infree();
         for(i=2; i<buf[0]; i++) accept(buf[i]);
         inon(TRUE);
      }
      else{
         pass[0] = nextproc(selfaddr, buf[1]);
         sendn(pass, buf[0], buf);
      }
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:queuep.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   queuep returns a queue entry.  If none is available,
   it attempts to obtain one by delivering messages.  If
   there is still no entry, queuep passes the error message
   errmess to the error routine. Call inoff before calling
   queuep.
*/

extern int sweep();                 /* match as many entries on inq's   */
                                    /* and wantq's as possible          */
extern int error();                 /* Error routine                    */

struct qentry *queuep(errmes)
int errmes;
{
   struct qentry *temp;
   if (qpoolp == NULL){
      sweep();
      if (qpoolp == NULL) error(errmes);
   }
   temp = qpoolp;
   qpoolp = temp->nextent;
   return(temp);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:ready.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   Nominally ready takes a pointer to a node and returns
   TRUE if it is ready for execution (i.e. if its want queue
   is empty) and false if NOT; and this is the way it is
   used by the scheduling routine.  However, it has the side
   effect of transfering data on the in-queue that can
   be matched with requests on the want-queue.  If all is
   true all matched requests are transfered.  If not, only
   requests up to the first unmatched one are transfered.
*/

extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */
extern int match();                 /* Determines if nodeids match      */
extern int freelist();              /* Returns linked list to pool      */
extern struct qentry *removeq();    /* Remove element from linked list  */

ready(node, all)
struct node *node;
int all;
{
   int             *destp,        /* Used to transfer message data  */
                   satisfied;     /* A flag indicating whether a    */
                                  /* match has been found for a     */
                                  /* request                        */
   struct qentry   *wqp,          /* Pointers used in searching the */
                   *lastwqp,      /* in and want queues             */
                   *inqp,
                   *lastinqp;
   struct listentry *mesp,        /* Pointers used to pass through  */
                    *lastmesp;    /* a message                      */

   /* Take care of the obvious case. */

   if (node->status==DETACHED) return(FALSE);

   /* Loop through the node's want queue. */

   wqp = node->wantq.head;
   lastwqp = NULL;
   while (wqp != NULL){
      satisfied = FALSE;

      /* Stop input while manipulating the in queue. */

      inoff();

         /* Search through the in queue for a match. */

         inqp = node->inq.head;
         lastinqp = NULL;
         while (inqp != NULL){
            if (match(&inqp->node, &wqp->node)){

               /* A match has been found. Transfer the data. */

               mesp = inqp->mesp;
               lastmesp = NULL;
               destp = (int *) wqp->mesp;
               while (mesp != NULL){
                  *destp++ = mesp->item;
                  lastmesp = mesp;
                  mesp = mesp->nextent;
               }

               /* Restore the entries to the queue and message pools. */

               freelist(inqp->node.name);
               removeq(inqp, lastinqp, &node->inq);
               if (lastmesp != NULL){
                  lastmesp->nextent = lpoolp;
                  lpoolp = inqp->mesp;
               }

               /* Mark the request satisfied and leave the in queue search. */

               satisfied = TRUE;
               break;
            }
            lastinqp = inqp;
            inqp = inqp->nextent;
         }
         if (satisfied)

            /* Request satisfied.  Remove the entry from the
            want queue. */

            wqp = removeq(wqp, lastwqp, &node->wantq);
         else{
            lastwqp = wqp;
            wqp = wqp->nextent;
         }
      inon(TRUE);
      if (!(all || satisfied)) break;
   }
   if (node->wantq.head == NULL)
      return(TRUE);
   else
      return(FALSE);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:removeq.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   removeq removes an item from an in- or a want-queue,
   returning the item to the queue pool and if necessary
   adjusting the pointers to the beginning and end of the
   queue.  The arguments in the calling sequence are

        qp         a pointer to the entry to be removed
        lastqp     a pointer to the entry proceeding the one
                   to be removed -- or NULL if the entry to
                   be removed is the first one
        qpointers  a pointer to the structure containing
                   the head and tail of the queue

   removeq returns a pointer to the next entry in the queue or
   null if the entry removed was at the end of the queue.
*/

struct qentry *removeq(qp, lastqp, qpointers)
struct qentry *qp, *lastqp;
struct qpointers *qpointers;
{
   struct qentry *temp;

   temp = qp->nextent;
   if (qpoolp == NULL){
      qpoolp = qp;
      qpoolp->nextent = NULL;
   }
   else{
      qp->nextent = qpoolp;
      qpoolp = qp;
   }
   if (lastqp == NULL)
      qpointers->head = temp;
   else
      lastqp->nextent = temp;
   if (temp == NULL)
      qpointers->tail = lastqp;

   return(temp);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:request.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   request adds an entry to the current node's want table.
   source is the nodeloc of the node from which a message
   is requested, and addr points to where the data is to
   be placed.
*/

extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */
extern struct qentry *addq();       /* Adds a message to a queue        */

request(source, addr)
struct nodeid *source;
struct listentry *addr;
{
   if (source == NULL) return;

   /* Block input while messing with the want queue. */

   inoff();
      addq(&nownodep->wantq, NULL);
      nownodep->wantq.tail->node.processor = source->processor;
      nownodep->wantq.tail->node.index = source->index;
      nownodep->wantq.tail->node.name = source->name;
      nownodep->wantq.tail->mesp = addr;
   inon(TRUE);
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:schedule.c                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   Schedule is a local function that returns a pointer to the
   next node to be awakened.  This particular scheduling program
   adopts the following strategy.

        1. Utility nodes are given priority over user and executive
           nodes.  Earlier nodes in the utility node table are
           given priority over later nodes.

        2. User and executive nodes are examined in round robin
           order for execution.

   Setting userstart to TRUE will cause the scheduling of user nodes
   to begin ab initio; similarly for execstart.  If no node is found
   to be ready in one cycle through the node table, schedule returns
   NULL.
*/

extern int ready();           /* Returns TRUE if a node is ready */
                              /* for execution                   */

struct node *schedule()
{
   int utnx, usnx, exnx;      /* Indexes for utility, user, and  */
                              /* executive nodes                 */
   static int lastusnx,       /* Indexes of the last user and    */
              lastexnx;       /* executive nodes that were       */
                              /* executed                        */

   /* Look for a ready utility node first */

   for (utnx=1; utnx<=NUTNODES; utnx++){
      if (ready(&utnode[utnx], FALSE)) return(&utnode[utnx]);
   }
   if (nnodes == 0) return(NULL);
   if (mode == USER){

      /* Schedule user nodes. */

      if (userstart){ /* Restart the scheduling. */
         userstart = FALSE;
         lastusnx = nnodes-1;
      }
      usnx = lastusnx;
      do{     
         usnx = ++usnx % nnodes;
         if (node[usnx]->class==USER && ready(node[usnx], FALSE)){
            lastusnx = usnx;
            return(node[usnx]);
         }
      } while (usnx != lastusnx);
   }
   else{

      /* Schedule executive nodes. */

      if (execstart){ /* Restart the scheduling. */
         execstart = FALSE;
         lastexnx = nnodes-1;
      }
      exnx = lastexnx;
      do{
         exnx = ++exnx % nnodes;
         if (node[exnx]->class==EXECUTIVE && ready(node[exnx], FALSE)){
            lastexnx = exnx;
            return(node[exnx]);
         }
      } while (exnx != lastexnx);
   }
   return(NULL);
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:sendn.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/


/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   sendn causes a message of size length, whose initial 
   location is pointed to by mes, to be placed on the
   inqueue of the node whose nodeid matches dest.  The
   first items of the packet are control items which
   have the following meanings.

            0. The type of transmission (SENDN);

            1. The originating processor.

            2. The index of the originating node.

            3. The length of the originating node name.

            4. The originating node name.

            5. The index of the destination node.

            6. The length of the destination node name.

            7. The destination node name.

            8. The length n of the message (i.e., the number
               of items following this one).

   If the noname flag is set items 3, 4, 6, and 7 are not sent.
   If the destination node is on the processor, accept is
   called directly; otherwise transmit is used to transfer the
   packet.  (transmit should call error if destination processor
   is not physically adjacent.
*/

extern int transmit();              /* Transmit data to another proc    */
extern int infree();                /* Wait until current inbound       */
                                    /* has been consumed by accept      */
extern int inon();                  /* End critical section             */
extern int error();                 /* Error routine                    */
extern int accept();                /* Processes current message item   */

sendn(dest, length, mes)
struct nodeid *dest;
int length, *mes;
{
   int cp[8+2*MAXNAME],        /* buffer for header         */
       n, m;                   /* indices                   */
   struct listentry *namep;    /* used to copy name         */

   /* Construct the message packet. */

   cp[0] = SENDN;
   cp[1] = nownodep->id.processor;
   cp[2] = nownodep->id.index;
   n = 3;
   if (!noname){
      cp[3] = 0;
      n = 4;
      namep = nownodep->id.name;
      while (namep != NULL){
         if (++cp[3] > MAXNAME) error(51);
         cp[n++] = namep->item;
         namep = namep->nextent;
      }
   }
   cp[n++] = dest->index;
   if (!noname){
      cp[m=n++] = 0;
      namep = dest->name;
      while (namep != NULL){
         if (++cp[m] > MAXNAME) error(51);
         cp[n++] = namep->item;
         namep = namep->nextent;
      }
   }
   cp[n++] = length;
   if (dest->processor == selfaddr){

      /* Node on same processor.  Wait for accept to become
      free and transmit the message. */

      infree();
         for (m=0; m<n; m++) accept(cp[m]);
         while (length-- > 0) accept(*mes++);
      inon(TRUE);
   }
   else{

      /* Node on a different processor.  Use transmit. */

      while (receiving);
      sending = TRUE;
      transmit(dest->processor, n, cp);
      transmit(dest->processor, length, mes);
      sending = FALSE;
   }
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:sendp.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   sendp causes a message of size length, whose initial 
   location is pointed to by mes, to be placed on processor
   destproc beginning in location pointed to by pointer.
   The first three items of the message are control items
   with the following meanings.

      1. Type of transmission (SENDP).

      2. The destination pointer.

      3. The length of the message.

   sendp operates in two modes.  If the message is to go to
   the local processor, it is placed there directly (without
   the control items).  Otherwise, it uses the PROFACE
   functions transmit and sburst to communicate with the
   DOMINO accept function on the other processor.

   Since it may be necessary to transmit data from noncontiguous
   areas of storage, sendp interrogates endflg before returning.
   if endflg is FALSE, sendp retains its connection with
   the receiving processor and returns expecting another
   message.
*/

extern int transmit();           /* Transmits an block of to */
                                 /* of data to another pro-  */
                                 /* cessor.                  */
extern int reqinblock();         /* Sets up transmit for     */
                                 /* burst mode               */
extern int freeinblock();        /* Turns off burst mode     */

sendp(destproc, pointer, length, mes, endflg)

int destproc, *pointer, length, *mes, endflg;
{
   static int type = SENDP,      /* type of message          */
              oldproc;           /* proc last sent to        */

   if (destproc == selfaddr)

      /* The message is local.  Transfer it directly. */

     while (length-- >= 0) *pointer++ = *mes++;

   else{

      /* The message is to another processor.  Transmit it. */

      if (!sending){
         while (receiving);
         oldproc = destproc;
         transmit(destproc, 1, &type);
         sending = TRUE;
         reqinblock();
      }

      transmit(oldproc, 1, &pointer);
      transmit(oldproc, 1, &length);
      transmit(oldproc, length, mes);
      transmit(oldproc, 1, &endflg);

      if (endflg){
         freeinblock();
         sending = FALSE;
      }

      return;
   }
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:sendrn.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
     Modified by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   sendrn is similar to sendn, but allows passage of a message
   to a destination processor which is not physically adjacent.
   It sends mes of size length to processor dest.sendrn creates
   a package with format:

         1. length of package

         2. destination processor

         3. array with data exactly in order as sendn
            would send it.

   This package is send using sendn to the pass node on 
   processor, which relays it to the pass node of the
   destination processor, which in turn calls accept.
*/

extern int makeid();                /* Create nodeid                    */
extern int error();                 /* Error routine                    */
extern int sendn();                 /* Send data to another node        */

sendrn(dest, length, mes)
struct nodeid *dest;
int length, *mes;
{
   static int buf[PNBUFSIZE],       /* buffer used to make package */
          n, m, i,                  /* indices                     */
          passnid[3];               /* node id of pass node        */
   static struct listentry *namep;  /* used to copy name of dest   */

   makeid(selfaddr, -2, 0, NULL, passnid);

   buf[2] = SENDN;
   buf[3] = nownodep->id.processor;
   buf[4] = nownodep->id.index;
   n = 4;
   if (!noname){
      buf[++n] = 0;
      namep = nownodep->id.name;
      while (namep != NULL){
         if (++n >= PNBUFSIZE) error(61);
         buf[n] = namep->item;
         namep = namep->nextent;
         buf[5]++;
      }
   }
   if (++n >= PNBUFSIZE) error(61);
   buf[1] = dest->processor;
   buf[n] = dest->index;
   if (!noname){
      if (++n >= PNBUFSIZE) error(61);
      buf[m=n] = 0;
      namep = dest->name;
      while (namep != NULL){
         if (++n >= PNBUFSIZE) error(61);
         buf[n] = namep->item;
         namep = namep->nextent;
         buf[m]++;
      }
   }
   if (++n+length >= PNBUFSIZE) error(61);
   buf[n++] = length;
   for (i=0; i<length; i++) buf[n++] = *mes++;
   buf[0] = n;
   sendn(passnid, n, buf);
}



/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:startup.c                              DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   Startup is the initialization routine for DOMINO.  It 
   clears the communication chanels, resets the system
   parameters, and sets up a small qpool for utility node
   zero to use.
*/

extern int inon();                  /* End critical section             */
extern int prostart();              /* Initializes proface              */
extern int makeutnd();              /* Sets up utility nodes            */

startup()
{
   /* Initialize PROFACE and create a critical section. */

   prostart();

      /* Initialize system parameters. */

      itemno = 0;
      noname = FALSE;
      sending = FALSE;
      receiving = FALSE;
      mode = USER;
      hung = FALSE;
      userstart = TRUE;
      execstart = TRUE;
      nnodes = 0;
      storex = 0;

      /* Set up starter queue and list pools. */

      qpoolp = q0;
      q0[0].nextent = &q0[1];
      q0[1].nextent = &q0[2];
      q0[2].nextent = NULL;

      lpoolp = NULL;

      /* Initialize saveq. */

      saveq.head = NULL;
      saveq.tail = NULL;

      /* Initialize utility nodes. */

      makeutnd();

   inon(TRUE);
   
   return;
}


/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:sweep.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   sweep is called when the queue pool or list pool is empty.
   It attempts to match entries on want- and in-queues in order
   to free up entries.
*/

extern int ready();           /* Returns TRUE if a node is ready */
                              /* for execution                   */

sweep()
{
   int i;
   for (i=1; i<=NUTNODES; i++)
      if (nownodep != &utnode[i]) ready(&utnode[i], TRUE);
   for (i=1; i<nnodes; i++)
      if (nownodep != node[i]) ready(node[i], TRUE);
   return;
}

#     SPLIT HERE     FILENAME =  domdec.h                   #

/* 
     DOMINO:domdec.h                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

extern int initial;                /* Initialization flag (TRUE   */
                                   /* or FALSE                    */
extern int nqents;                 /* Number of entries in the    */
                                   /* queue pool.                 */
extern int nlents;                 /* Number of entries in the    */
                                   /* list pool.                  */
extern int goauxsize;              /* Size of the go node's       */
                                   /* auxiliary storage           */
extern int gostksize;              /* Size of the go node's stack */
extern int noname;                 /* A flag supressing the       */
                                   /* naming of nodes             */
extern struct qentry q0[];         /* Initial qpool               */
extern struct node utnode[];       /* Utility node table          */
extern int syssp;                  /* System stack pointer        */
extern int hardcm;                 /* Hard control message flag   */
                                   /* (TRUE or FALSE)             */
extern int cm;                     /* Current control message     */
                                   /* (GENERAL_PURPOSE, RESTART,  */
                                   /* HALT, TOGGLE)               */
extern int itemno;                 /* Number of current item in   */
                                   /* an incoming message         */
extern int sending;                /* A flag indicating whether   */
                                   /* PROFACE is transmitting a   */
                                   /* message                     */
extern int receiving;              /* A flag indicating whether   */
                                   /* accept is receiving in      */
                                   /* burst mode.                 */
extern int mode;                   /* Mode of execution (USER or  */
                                   /* EXECUTIVE)                  */
extern int hung;                   /* Hung node flag (TRUE or     */
                                   /* FALSE)                      */
extern int userstart;              /* Restart scheduling of user  */
                                   /* nodes (TRUE or FALSE)       */
extern int execstart;              /* Restart scheduling of exec- */
                                   /* utive nodes (TRUE or FALSE) */
extern struct node *nownodep;      /* Pointer to the currently    */
                                   /* executing node              */
extern int selfaddr;               /* Address of the processor    */
extern struct qentry *qpoolp;      /* Pointer to available queue  */
                                   /* entry                       */
extern struct qpointers saveq;     /* Pointers for the queue to   */
                                   /* save unmatched messages     */
extern struct listentry *lpoolp;   /* Pointer to available message*/
                                   /* entry                       */
extern int nnodes;                 /* Number of nodes             */
extern int storex;                 /* Current top of storage      */
extern struct node *node[];        /* The node table              */
extern int store[];                /* Common storage              */

#     SPLIT HERE     FILENAME =  domparam.h                 #

/* 
     DOMINO:domparam.h                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

#define NTSIZE 100                 /* Node table size             */
#define STORSIZE 15000             /* Common storage size         */
#define NUTNODES 2                 /* Number of utility nodes     */
#define MAXNAME 10                 /* Maximum size of node name   */
#define NODESIZE 13                /* Size (integers) of struct   */
                                   /* node                        */
#define QENTSIZE 5                 /* Size (integers) of struct   */
                                   /* qentry                      */
#define LENTSIZE 2                 /* Size (integers) of struct   */
                                   /* Lentry                      */
#define TRUE 1                     /* True                        */
#define FALSE 0                    /* False                       */
#define NULL 0                     /* Value of null pointer       */
#define UTILITY 0                  /* Node class UTILITY          */
#define DATA 1                     /* Node class DATA             */
#define USER 2                     /* Node class USER             */
#define EXECUTIVE 3                /* Node class EXECUTIVE        */
#define CONTINUE 0                 /* Signal passed to control by */
                                   /* cmcheck: CONTINUE           */
#define START 1                    /* Signal passed to control by */
                                   /* cmcheck: START              */
#define AWAKEN 2                   /* Signal passed to control by */
                                   /* cmcheck: AWAKEN             */
#define GENERAL_PURPOSE 1          /* Control message type        */
                                   /* GENERAL_PURPOSE             */
#define RESTART 2                  /* Control message type        */
                                   /* RESTART                     */
#define HALT 3                     /* Control message type        */
                                   /* HALT                        */
#define TOGGLE 4                   /* Control message type        */
                                   /* TOGGLE                      */
#define SENDN 0                    /* Message type SENDN          */
#define SENDP 1                    /* Message type SENDP          */
#define DONE 0                     /* Signal passed by accept to  */
                                   /* PROFACE: end of message     */
#define MORE 1                     /* Signal passed by accept to  */
                                   /* PROFACE: not end of message */
#define READY 0                    /* Node status READY           */
#define ACTIVE 1                   /* Node status ACTIVE          */
#define DETACHED 2                 /* Node status DETACHED        */
#define PNBUFSIZE 20               /* Maximimum length of message */
                                   /* created by sendrn           */

#     SPLIT HERE     FILENAME =  domstruct.h                #

/* 
     DOMINO:domstruct.h                            DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/* listentry:

   DOMINO stores message and names as linked lists of the following
   structure.
*/
struct listentry{
   int item;
   struct listentry *nextent;
};

/* nodeloc:

   The location of a node is specified by two integers and
   an optional name.  The itegers are the node's processor
   and its position on the nodetable.  The name is stored in
   a linked list.  The structure nodeid holds these integers
   and a pointer to the name.

*/
struct nodeid{
   int processor;
   int index;
   struct listentry *name;
};

/* qentry:

   Each node has associated with it a want-queue, consisting
   of requests of data from other nodes, and an in-queue, consisting
   of messages directed to it by other nodes.  Both queues are
   implemented as linked lists, whose entries consist of
   the location of the source node, a pointer to where the
   message is to go (or in the case of the in-queue, where it
   has been buffered), and a pointer to the next entry in the
   queue.  In the case of the want-queue we are guilty of a mild
   abuse of pointers, since mesp does not point to a linked message
   list, but instead to where the message is to be placed.
*/
struct qentry{
   struct nodeid node;
   struct listentry *mesp;
   struct qentry *nextent;
};

/* qpointers:

   qpointers is a structure containing pointers to the head and
   tail of an in-queue or a want-queue.
*/
struct qpointers{
   struct qentry *head;
   struct qentry *tail;
};

/* node:

   A node is specified by the following structure. */

struct node{
   int class;                 /* USER or EXECUTIVE                   */
   int status;                /* READY, ACTIVE, or DETACHED          */
   struct nodeid id;          /* The id of the node                  */
   int (*program)();          /* Pointer to the program that         */
                              /* executes the node                   */
   int *auxp;                 /* Pointer to the auxiliary storage    */
                              /* for the node                        */
   int *stacktop;             /* Stack pointer for the node          */
   int *stackbot;             /* Starting location of the node stack */
   struct qpointers inq;      /* Contains the head and tail of the   */
                              /* node's in-queue                     */
   struct qpointers wantq;    /* Contains the head and tail of the   */
                              /* node's want-queue                   */
};

#     SPLIT HERE     FILENAME =  domdefault.c               #

/* 
     DOMINO:error.c                                DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Van de Geijn
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/* 
   error is the (machine dependent) error routine. 
   This version simply prints out errnum.
   DOMINO errors are coded as follows:

        1* : accept detected error
        11 : qpool empty (error called from queuep)
        12 : lpool empty (error called from listp)
        13 : destination utility node invalid
        14 : illegal type

        2* : addq detected error
        21 : qpool empty
 
        3* : cmcheck detected error
        31 : illegal control message

        4* : makenode detected error
        41 : node table overflow
        42 : storage overflow
        43 : illegal class
        44 : name size too large
        45 : lpool empty (called from listp)

        5* : sendn detected error
        51 : name too long

        6* : sendrn detected error
        61 : buffer size exceeded

        7* : default boot detected error 
        71 : too many queue entries (nqents too large)
        72 : too many list entries  (nlents too large)
*/

error(errnum)
int errnum;
{
   printf("DOMINO ERROR: %d", errnum);
   exit(0);
}



/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:nextproc.c                             DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

/*
   nextproc will return the address of the next
   processor on the path between processor with
   address here and processor with address there.
   This particular example is for a linear array of
   processors.
*/

nextproc(here, there)
int here, there;
{
   if (there-here > 0)
      return(here + 1);
   else
      return(here - 1);
}

#     SPLIT HERE     FILENAME =  spproface.c                #

/* 
     DOMINO:spproface.c                            DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"

/* 
   PROFACE routines for single processor version.
   Since most of these routines have no effect in
   this case, they don't do anything.
*/

/*
   inoff blocks inbound data from arriving.
   Returns TRUE or FALSE depending on whether
   or not inbound data was already blocked.
*/

inoff(){}

/*
   inon unblocks inbound data when arg equals TRUE.
*/

inon(arg) int arg; {}

/*
   infree waits until any current inbound message has
   completely arrived, after which it block inbound
   data from arriving.
*/

infree(){}

/*
   reqinblock act like infree, except that it doesn't
   wait until the message has completely arrived. Instead
   it posts a flag indicating that once it has arrived
   inbound data is to be blocked.
*/

reqinblock(){}

/* 
   freeinblock unblocks inbound data, and resets flag set
   by reqinblock.
*/

freeinblock(){}

/* 
   initialize PROFACE and other machine dependent i/o.
*/

prostart()
{
   selfaddr = 1;
}

/*
   transmit sends message of size length, which 
   starts at location pointed to by mes to processor
   with address proc.
*/

transmit(proc, length, mes)
int proc, length, *mes;
{}

/*
   accburst allows data to be accepted faster
   during a transmition originated by sendp.
   It will put item in the location pointed to
   by pointer, decrease n, increase pointer
   and next will attempt to create a fast 
   connection.  Upon return it will have
   updated pointer and n according to how many
   items have arrived in the mean time. In
   case of a single processor accburst will never
   be called.
*/

accburst(pointer, n, item)
int **pointer, *n, item;
{}

#     SPLIT HERE     FILENAME =  boot.c                     #

/* 
     DOMINO:boot.c                                 DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"

/*
   boot is the (user provided) routine which is the nodeprogram
   for the utility node which "boots" the system.  It is intended
   to perform the following functions:

        1.  Create the queue pool, list pool.

        2.  Create a go node on the node table, with nodeprogram
            go(), and appropriate amount of space reserved for
            its aux and stack.

   This particular general purpose boot node is designed 
   for DOMINO on a single processor, rather than a true
   multi-processor.  For more examples see the documentation.
*/

extern int go();                    /* node program for go node         */
extern int inoff();                 /* Begin critical section           */
extern int inon();                  /* End critical section             */
extern int makenode();              /* Make new entry on node table     */
extern int finis();                 /* Detach node                      */
extern int error();                 /* Error routine                    */

boot(nd, sysp)
struct node *nd;             /* pointer to boot node       */
int *sysp;                   /* pointer to system var's    */
{
   int i;                    /* index                      */
   struct qentry *qstart;    /* used to init queue pool    */
   struct listentry *lstart; /* used to init list pool     */

   /* Initialize the queue pool. */

   inoff();        /* prevent incoming messages from using q's before ready */
                   /* not really necessary for 1-processor case */

      printf("\nEnter the number of queue entries: ");
      scanf("%d", &nqents);
      if (storex+nqents*QENTSIZE >= STORSIZE)
         error(71);
      qpoolp = qstart = (struct qentry *) &store[storex];
      for (i=1; i<=nqents; i++)
         if (i != nqents){
            qpoolp->nextent = qpoolp+1;
            qpoolp++;
         }
         else
            qpoolp->nextent = NULL;
      qpoolp = qstart;
      storex = storex + nqents*QENTSIZE;

      /* Initialize the list pool. */

      printf("\nEnter the number of list entries: ");
      scanf("%d", &nlents);
      if (storex+nlents*LENTSIZE >= STORSIZE)
         error(72);
      lpoolp = lstart = (struct listentry *) &store[storex];
      for (i=1; i<=nlents; i++)
         if (i != nlents){
            lpoolp->nextent = lpoolp+1;
            lpoolp++;
         }
         else
            lpoolp->nextent = NULL;
      lpoolp = lstart;
      storex = storex + nlents*LENTSIZE;

      printf("\nEnter the size of the auxiliary storage of go-node: ");
      scanf("%d", &goauxsize);
      printf("\nEnter the size of the stack of go-node: ");
      scanf("%d", &gostksize);

   inon(TRUE);   

   /* Make the go-node. */

   makenode(USER, 0, NULL, go, goauxsize, gostksize);
   finis();
}

#     SPLIT HERE     FILENAME =  brigade.c                  #

/* 
     DOMINO:brig.boot.c                            DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*************************************************************/
/*                                                           */
/*     The single processor boot-node program for the        */
/*     brigade example                                       */
/*                                                           */
/*************************************************************/


#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"

#define FLOATSIZE 1

/* Auxiliary storage for the brigade go-node                 */

#define PROCNO goap->procno
#define NP goap->np
#define LASTGO goap->lastgo
#define NEXTGO goap->nextgo
#define TESTING goap->testing

struct goaux{
   int procno;
   int np;
   int nextgo[3];
   int lastgo[3];
   int testing;
};

extern int error();                 /* Error routine                    */
extern int makenode();              /* Make new entry on node table     */
extern int finis();                 /* Detach node                      */
extern int go();                    /* node program for go node         */
extern int makeid();                /* Create nodeid                    */
boot(nd, init)
struct node *nd;
int *init;
{
   int n, i, np, go();
   struct qentry *qstart;
   struct listentry *lstart;
   struct goaux *goap;

   /* Initialize the queue pool. */

   nqents = 50;
   if (storex+nqents*QENTSIZE >= STORSIZE)
      error("\nboot: too many queue entries");
   qpoolp = qstart = (struct qentry *) &store[storex];
   n = nqents;
   for (i=1; i<=n; i++)
      if (i != n){
         qpoolp->nextent = qpoolp+1;
         qpoolp++;
      }
      else
         qpoolp->nextent = NULL;
   qpoolp = qstart;
   storex = storex + nqents*QENTSIZE;

   /* Initialize the list pool. */

   nlents = 50;
   if (storex+nlents*LENTSIZE >= STORSIZE)
      error("\nboot: too many list entries");
   lpoolp = lstart = (struct listentry *) &store[storex];
   n = nlents;
   for (i=1; i<=n; i++)
      if (i != n){
         lpoolp->nextent = lpoolp+1;
         lpoolp++;
      }
      else
         lpoolp->nextent = NULL;
   lpoolp = lstart;
   storex = storex + nlents*LENTSIZE;

   /* Make the go-node. */

   goauxsize = 10;
   gostksize = 300;

   /* Get the number of "processors" */

   printf("Enter number of processors: ");
   scanf("%d", &np);

   for (i=1; i<=np; i++){
      makenode (USER, 0, NULL, go, goauxsize, gostksize);
      goap = (struct goaux *) node[nnodes-1]->auxp;
      PROCNO = i;
      NP = np;
      TESTING = TRUE;
      makeid(selfaddr, nnodes-2, 0, NULL, LASTGO);
      makeid(selfaddr, nnodes%np, 0, NULL, NEXTGO);
   }
   finis();
}



/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:brig.go.c                               DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*************************************************************/
/*                                                           */
/*       The  go-node program for the brigade example        */
/*                                                           */
/*************************************************************/

/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

#define FLOATSIZE 1

/* Auxiliary storage for the brigade node program            */

#define MEMBER ap->member
#define N ap->n
#define NGAL ap->ngal
#define FRONT ap->front
#define BACK ap->back
#define FIRST ap->first
#define LAST ap->last

struct brigaux{
   int member;
   int n;
   int ngal;
   int front[5];
   int back[5];
   int first[5];
   int last[5];
};

/* Auxiliary storage for the brigade go-node                 */

#define PROCNO goap->procno
#define NP goap->np
#define LASTGO goap->lastgo
#define NEXTGO goap->nextgo
#define TESTING goap->testing

/*
struct goaux{
   int procno;
   int np;
   int nextgo[3];
   int lastgo[3];
   int testing;
};
*/

extern int makenode();              /* Make new entry on node table     */
extern int pause();                 /* Return to control until node is  */
                                    /* ready to be reawakened           */
extern int request();               /* Request data from another node   */
extern int sendn();                 /* Send data to another node        */
extern int finis();                 /* Detach node                      */
extern int makeid();                /* Create nodeid                    */

go(nd, sysp)
struct node *nd;
int *sysp;
{
   int n, ngal, q, r, nnds, firstnd, lastnd, 
          i, k, brigade();
   struct goaux *goap;
   struct brigaux *ap;

   goap = (struct goaux *) nd->auxp;

   /* Set up the brigade parameters                          */

   if (PROCNO == 1){
      printf("\nEnter the length of the brigade: ");
      scanf("%d", &n);
      if (n < NP){
         printf ("\nNot enough members in the brigade.\n");
         finis();
      }

      printf("\nHow many gallons to put this one out: ");
      scanf("%d", &ngal);
   }
   else{
      request(LASTGO, &n);
      request(LASTGO, &ngal);
      pause();
   }
   if (PROCNO != NP){
      sendn(NEXTGO, 1, &n);
      sendn(NEXTGO, 1, &ngal);
   }

   /* Decide what nodes are on the current processor         */

   q = n/NP;
   r = n%NP;
   nnds = q + (PROCNO<=r ? 1 : 0);
   firstnd = (PROCNO-1)*q + (PROCNO<=r ? PROCNO-1 : r) + 1;
   lastnd = firstnd + nnds - 1;

   /* Create the nodes                                       */

   for (i=firstnd; i<=lastnd; i++){
      makenode(USER, 1, &i, brigade, 20, 300);
      ap = (struct brigaux *) node[nnodes-1]->auxp;
      MEMBER = i;
      N = n;
      NGAL = ngal;
      k = i-1;
      makeid(i==firstnd ? LASTGO[0] : selfaddr, 0, 1, &k, BACK);
      k = i+1;
      makeid(i==lastnd ? NEXTGO[0] : selfaddr, 0, 1, &k, FRONT);
      k = 1;
      makeid(NEXTGO[0], 0, 1, &k, FIRST);
      makeid(LASTGO[0], 0, 1, &n, LAST);
   }
   finis();
}



/* $%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$%$% */

/* 
     DOMINO:brig.node.c                            DATE: 5-86   
     O'Leary, Stewart, Van de Geijn    University of Maryland

     Programmed by Stewart
*/

/*************************************************************/
/*                                                           */
/*   The  brigade-node program for the brigade example       */
/*                                                           */
/*************************************************************/



/*
#include "domparam.h"
#include "domstruct.h"
#include "domdec.h"
*/

#define FLOATSIZE 1

/* Auxiliary storage for the brigade node program            */

#define MEMBER ap->member
#define N ap->n
#define NGAL ap->ngal
#define FRONT ap->front
#define BACK ap->back
#define FIRST ap->first
#define LAST ap->last

/*
struct brigaux{
   int member;
   int n;
   int ngal;
   int front[5];
   int back[5];
   int first[5];
   int last[5];
}
*/

extern int pause();                 /* Return to control until node is  */
                                    /* ready to be reawakened           */
extern int request();               /* Request data from another node   */
extern int sendn();                 /* Send data to another node        */
extern int finis();                 /* Detach node                      */

brigade(nd, sysp)
struct node *nd;
int *sysp;
{
   int  bucket, still_burning;
   struct brigaux *ap;

   ap = (struct brigaux *) nd->auxp;

   bucket = 0;
   still_burning = TRUE;

   while (TRUE){

      if (MEMBER == N){

      /* Last member of the brigade. Pour the current bucket 
         on the fire and signal the first member about the
         status of the fire                                  */

         if (still_burning){
            NGAL = NGAL - bucket;
            still_burning = NGAL>0;
            sendn(FIRST, 1, &still_burning);
         }
         request(BACK, &bucket);
         pause();
         if (bucket < 0) finis();
      }

      if (MEMBER == 1){

      /* First member of the brigade. Get the status of the
         fire. If it is still burning, get a bucket and pass
         it on. Otherwise pass a messaage that the fire is 
         out.                                                */

         request(LAST, &still_burning);
         pause();
         if (still_burning){
            printf("\nFill my bucket: ");
            scanf("%d", &bucket);
            sendn(FRONT, 1, &bucket);
         }
         else{
            bucket = -1;
            sendn(FRONT, 1, &bucket);
            printf("\nFire out!\n");
            finis();
         }
      }

      if (MEMBER !=1 && MEMBER !=N){

      /* Intermediate members. Keep passing buckets until 
         the fire is out.                                    */

         sendn(FRONT, 1, &bucket);
         if (bucket < 0) finis();
         request(BACK, &bucket);
         pause();
      }
   }
}