home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
c
/
xrf.arc
/
XRF2.C
< prev
next >
Wrap
C/C++ Source or Header
|
1985-02-05
|
6KB
|
194 lines
/*
* ***************
* * X R F 2 . C *
* ***************
*
* This file contains the identifier tree and reference list management
* things. It uses a simple binary tree to store the identifiers for
* lookup and later sorted printing. Each node in the id tree has a
* pointer to the id string, left and right links and pointers to the
* beginning and end of the linked list of reference nodes for that
* id. Only the root of the tree is global, it is used by the sorted
* index printing function 'prtree'.
*
* Version V1.3 9-May-80
* Version V1.4 10-Jul-80 MM Bummed code
* Version V1.5 23-Jul-80 MM Redid storage code
* Version V1.6 23-Dec-80 RBD Fixed bug in myalloc()
* Version V1.7 8-Jan-85 MC Document key change for non
* case-sensitive keys/concatanation.
*/
#include <stdio.h>
#include "xrf.h"
/*
* Tree search and insertion. This function returns a pointer to
* the new node if created. This may require some head scratching
* (I had to!). Look particularly at the significance of the pointer
* that is returned and how it is used by the recursive caller. If
* you want more, read "Algorithms + Data Structures = Programs"
* by Niklaus Wirth (Prentice Hall ISBN 0-13-022418-9) Chapter 4.
*
* It searches through the tree for a match to the supplied id (*kp).
* If it is found, a new reference node is linked into the list for
* that id. If no match is found, a new is node is inserted into the
* tree and appropriately initialized, including a first reference
* node.
*
* The node is now positioned in the tree in case non-sensitive order.
* This means that in the final list mixed, upper & lower case symbols
* appear togethor instead of being separated in the collating sequence.
* Also the source name is present for file concatanation.
*
* The id (*kp) now comes as <KEYactualNNNNNNNN> from XRF0.C where:-
* KEY is the symbol as lower case
* length CPS characters.
* actual is the symbol as she appears
* length CPS characters.
* NNNNNNNN is the program name
* length 8 chars
*
*/
struct idt *search(kp, link) /* Function "search" */
struct idt *link; /* Pointer to id node in tree */
char *kp; /* Pointer to key string */
{
register struct idt *l; /* Fast tree pointer */
register struct ref *r; /* Fast list pointer */
register int cond; /* Condition from strcmp */
struct ref *newref(); /* Make reference function */
l = link; /* Copy link into register */
if(l == NULL) /* Not found, insert new id node */
{
l = myalloc(sizeof(struct idt)); /* Make a new ident node */
l->keyp = myalloc(strlen(kp)+1); /* Get string space */
/* Fill in pointer to ... */
strcpy(l->keyp, kp); /* ... stashed key string */
l->left = l->right = NULL; /* No children */
l->first = l->last = newref(); /* Attach it to the id node */
}
else if((cond = strcmp(kp, l->keyp)) == 0) /* Match if true */
{
r = newref(); /* Get a new ref. node */
l->last->next = r; /* Hook new node into the list */
l->last = r;
}
else if(cond < 0) /* Look left */
l->left = search(kp, l->left);
else /* Look right */
l->right = search(kp, l->right);
return(l);
}
/*
* Initialize a line number referece
*/
static struct ref *
newref()
{
register struct ref *r;
r = myalloc(sizeof(struct ref)); /* Make a reference node */
r->lno = lineno; /* Fill in line no. of ref. */
r->next = NULL; /* This is the end for now */
return(r); /* Return pointer to the node */
}
/*
* Storage allocation:
*
* my_free Free byte pointer in local buffer
* my_left Number of bytes left in local buffer
* my_link Link of free space buffers (from malloc())
*
* If space can be gotten locally, get it. If not, request a "large"
* chunk of memory and update my_free, my_left.
*
* My_link links chunks from monitor, myfree() returns them (called
* at a new input file).
*/
struct my_alloc {
struct my_alloc *my_next;
};
static struct my_alloc *my_link = NULL;
static char *my_free = NULL;
static int my_left = 0;
myalloc(amount)
int amount;
/*
* Allocate amount bytes.
*/
{
register char *new;
register int needed;
char *malloc();
needed = (amount + 1) & 0177776; /* Round up to a word bound */
if (needed > my_left) {
/*
* Gotta get storage
*/
if ((my_free = malloc(512)) == NULL)
quit();
my_left = 512 - (sizeof (struct my_alloc));
((struct my_alloc *)my_free)->my_next = my_link;
my_link = (struct my_alloc *)my_free;
my_free += sizeof (struct my_alloc);
}
my_left -= needed;
if (my_left < 0)
abort("Trying to get too much: %d\n", needed);
new = my_free;
my_free += needed;
return(new);
}
myfree()
/*
* Return all storage to the pool
*/
{
register struct my_alloc *link;
register struct my_alloc *next;
next = my_link;
while ((link = next) != NULL) {
next = link->my_next;
free(link);
}
my_link = NULL;
my_free = NULL;
my_left = 0;
}
/*
* 'quit' handles dynamic memory deficit. (Sounds like U.S. Government!).
* It issues a polite message to the user, marks the list file for delete
* and exits to RSX.
*
*/
quit()
{
char workbuf[40];
abort("Not enough memory space, sorry.\n");
/* puts("Not enough memory space, sorry.\n");
fgetname(lst, workbuf);
fclose(lst);
delete(workbuf);
exit(1);*/
}