Category : C Source Code
Archive   : CXRF.ZIP
Filename : XRF2.C

Output of file : XRF2.C contained in archive : CXRF.ZIP


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
Version V1.8 13-Dec-89 SMB Modified for Turbo C conpatibility
26-Dec-89 Added MYALLOC macro
#include "xrf.h"

#define MYALLOC 1024 /* Size of allocated memory blocks */

struct my_alloc {
struct my_alloc *my_next;
static struct my_alloc *my_link = NULL; /* Link of free space buffers */
static char *my_free = NULL; /* Free byte pointer in buffer */
static int my_left = 0; /* Bytes left in local buffer */

Function: myalloc

Prototype In: Local to this module.

Description: Storage allocation. If space can be gotten locally,
get it. Otherwise request a "large" chunk of memory
and update my_free, my_left.

my_link links chunks of memory allocated by system.

Usage: myalloc(int amount)

Returns: Pointer to beginning of allocated memory.
static void *myalloc(int amount)
register char *new;
register int needed;

needed = (amount + 1) & 0xFFFE; /* Round up to word boundary */
if (needed > my_left) { /* Grab memory from system as needed */
if ((my_free = (char *)malloc(MYALLOC)) == NULL)
fatal("Out of memory\n");
my_left = MYALLOC - (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)
fatal("Trying to get too much: %d\n", needed);
new = my_free;
my_free += needed;

Function: newref

Prototype In: Local to this module.

Description: Initialize a line number reference.

Returns: Pointer to the node.
static struct ref *newref(void)
register struct ref *r;

r = (struct ref *)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 */

Function: search

Prototype In: xrf.h

Description: Tree search and insertion. This function returns a
pointer to the new node if created. This may require
xome 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 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 and lower case symbols appear
together instead of being separated in the collating
sequence. Also the source name is present for
file concatanation.

The id (*kp) comes from XRF0.C as

KEYactualNNN where:

KEY is the symbol as lower case
length CPS characters.
actual is the symbol as she appears
length CPS characters.
NNN is the program name
length 12 characters.

Returns: Pointer to new node if created.
struct idt *search(char *kp, /* Pointer to key string */
struct idt *link) /* Pointer to id node in tree */
register struct idt *l; /* Fast tree pointer */
register struct ref *r; /* Fast list pointer */
register int cond; /* Condition from strcmp */

l = link; /* Copy link into register */
if (l == NULL) { /* Not found, insert new id node */
l = (struct idt *)myalloc(sizeof(struct idt));
l->keyp = myalloc(strlen(kp) + 1);
/* Fill in pointer to stashed key string */
strcpy(l->keyp, kp);
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);

Function: myfree

Prototype In: xrf.h

Description: Return all storage to the pool.

Returns: void
void myfree(void)
register struct my_alloc *link;
register struct my_alloc *next;

next = my_link;
while ((link = next) != NULL) {
next = link->my_next;
my_link = NULL;
my_free = NULL;
my_left = 0;

/* End XRF2.C */