home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / c / xrf.arc / XRF2.C < prev    next >
Encoding:
C/C++ Source or Header  |  1985-02-06  |  6.0 KB  |  194 lines
  1.  
  2.  
  3. /*
  4.  *                      ***************
  5.  *                      * X R F 2 . C *
  6.  *                      ***************
  7.  *
  8.  * This file contains the identifier tree and reference list management
  9.  * things. It uses a simple binary tree to store the identifiers for
  10.  * lookup and later sorted printing. Each node in the id tree has a
  11.  * pointer to the id string, left and right links and pointers to the
  12.  * beginning and end of the linked list of reference nodes for that
  13.  * id. Only the root of the tree is global, it is used by the sorted
  14.  * index printing function 'prtree'.
  15.  *
  16.  * Version V1.3          9-May-80
  17.  * Version V1.4        10-Jul-80 MM    Bummed code
  18.  * Version V1.5        23-Jul-80 MM    Redid storage code
  19.  * Version V1.6        23-Dec-80 RBD    Fixed bug in myalloc()
  20.  * Version V1.7         8-Jan-85 MC    Document key change for non 
  21.  *                    case-sensitive keys/concatanation.
  22.  */
  23.  
  24. #include <stdio.h>
  25. #include "xrf.h"
  26.  
  27.  
  28. /*
  29.  * Tree search and insertion. This function returns a pointer to
  30.  * the new node if created. This may require some head scratching
  31.  * (I had to!). Look particularly at the significance of the pointer
  32.  * that is returned and how it is used by the recursive caller. If
  33.  * you want more, read "Algorithms + Data Structures = Programs"
  34.  * by Niklaus Wirth (Prentice Hall ISBN 0-13-022418-9) Chapter 4.
  35.  *
  36.  * It searches through the tree for a match to the supplied id (*kp).
  37.  * If it is found, a new reference node is linked into the list for
  38.  * that id. If no match is found, a new is node is inserted into the
  39.  * tree and appropriately initialized, including a first reference
  40.  * node.
  41.  *
  42.  * The node is now positioned in the tree in case non-sensitive order.
  43.  * This means that in the final list mixed, upper & lower case symbols
  44.  * appear togethor instead of being separated in the collating sequence.
  45.  * Also the source name is present for file concatanation.
  46.  *
  47.  * The id (*kp) now comes as <KEYactualNNNNNNNN> from XRF0.C where:-
  48.  *                      KEY                is the symbol as lower case
  49.  *                                                  length CPS characters.
  50.  *                               actual          is the symbol as she appears
  51.  *                                                  length CPS characters.
  52.  *                           NNNNNNNN  is the program name
  53.  *                                                  length 8 chars
  54.  *
  55.  
  56.  */
  57.  
  58. struct idt *search(kp, link)            /* Function "search" */
  59. struct idt *link;                       /* Pointer to id node in tree */
  60. char *kp;                               /* Pointer to key string */
  61.    {
  62.    register struct idt *l;              /* Fast tree pointer */
  63.    register struct ref *r;              /* Fast list pointer */
  64.    register int cond;                   /* Condition from strcmp */
  65.    struct ref *newref();        /* Make reference function */
  66.  
  67.    l = link;                            /* Copy link into register */
  68.    if(l == NULL)                        /* Not found, insert new id node */
  69.       {
  70.       l = myalloc(sizeof(struct idt));    /* Make a new ident node */
  71.       l->keyp = myalloc(strlen(kp)+1);    /* Get string space */
  72.                                         /* Fill in pointer to ... */
  73.       strcpy(l->keyp, kp);              /* ... stashed key string */
  74.       l->left = l->right = NULL;        /* No children */
  75.       l->first = l->last = newref();    /* Attach it to the id node */
  76.       }
  77.    else if((cond = strcmp(kp, l->keyp)) == 0) /* Match if true */
  78.       {
  79.       r = newref();            /* Get a new ref. node */
  80.       l->last->next = r;        /* Hook new node into the list */
  81.       l->last = r;
  82.       }
  83.    else if(cond < 0)                    /* Look left */
  84.       l->left = search(kp, l->left);
  85.    else                                 /* Look right */
  86.       l->right = search(kp, l->right);
  87.    return(l);
  88.    }
  89.  
  90.  
  91. /*
  92.  * Initialize a line number referece
  93.  */
  94.  
  95. static struct ref *
  96. newref()
  97. {
  98.    register struct ref *r;
  99.  
  100.    r = myalloc(sizeof(struct ref));    /* Make a reference node */
  101.    r->lno = lineno;                     /* Fill in line no. of ref. */
  102.    r->next = NULL;                      /* This is the end for now */
  103.    return(r);                /* Return pointer to the node */
  104. }
  105.  
  106. /*
  107.  * Storage allocation:
  108.  *
  109.  * my_free        Free byte pointer in local buffer
  110.  * my_left        Number of bytes left in local buffer
  111.  * my_link        Link of free space buffers (from malloc())
  112.  *
  113.  * If space can be gotten locally, get it.  If not, request a "large"
  114.  * chunk of memory and update my_free, my_left.
  115.  *
  116.  * My_link links chunks from monitor, myfree() returns them (called
  117.  * at a new input file).
  118.  */
  119.  
  120. struct my_alloc {
  121.     struct my_alloc    *my_next;
  122. };
  123.  
  124. static struct my_alloc    *my_link    = NULL;
  125. static char        *my_free    = NULL;
  126. static int        my_left        = 0;
  127.  
  128. myalloc(amount)
  129. int        amount;
  130. /*
  131.  * Allocate amount bytes.
  132.  */
  133. {
  134.     register char    *new;
  135.     register int    needed;
  136.     char        *malloc();
  137.  
  138.     needed = (amount + 1) & 0177776;  /* Round up to a word bound */
  139.     if (needed > my_left) {
  140.         /*
  141.          * Gotta get storage
  142.          */
  143.         if ((my_free = malloc(512)) == NULL)
  144.             quit();
  145.         my_left = 512 - (sizeof (struct my_alloc));
  146.         ((struct my_alloc *)my_free)->my_next = my_link;
  147.         my_link = (struct my_alloc *)my_free;
  148.         my_free += sizeof (struct my_alloc);
  149.     }
  150.     my_left -= needed;
  151.     if (my_left < 0)
  152.         abort("Trying to get too much: %d\n", needed);
  153.     new = my_free;
  154.     my_free += needed;
  155.     return(new);
  156. }
  157.  
  158. myfree()
  159. /*
  160.  * Return all storage to the pool
  161.  */
  162. {
  163.     register struct my_alloc    *link;
  164.     register struct my_alloc    *next;
  165.  
  166.     next = my_link;
  167.     while ((link = next) != NULL) {
  168.         next = link->my_next;
  169.         free(link);
  170.     }
  171.     my_link = NULL;
  172.     my_free = NULL;
  173.     my_left = 0;
  174. }
  175.  
  176.  
  177. /*
  178.  * 'quit' handles dynamic memory deficit. (Sounds like U.S. Government!).
  179.  * It issues a polite message to the user, marks the list file for delete
  180.  * and exits to RSX.
  181.  *
  182.  */
  183.  
  184. quit()
  185.    {
  186.    char workbuf[40];
  187.  
  188.    abort("Not enough memory space, sorry.\n");
  189. /*   puts("Not enough memory space, sorry.\n");
  190.    fgetname(lst, workbuf);
  191.    fclose(lst);
  192.    delete(workbuf);
  193.    exit(1);*/
  194.    }