Examples

           *************************************
          * Hashing, Linked Lists, Trees, Forking * 
           *************************************

                  **** Hashing ****
(From R.K. Irvine)
I have used many hash functions.  Each one has advantages
and disadvantages.  Here is a powerful but simple one.
It simply does a crc16 on the character string.  The crc16 is
a great hash function since it is designed to produce a
unique code for different character strings.  So for "reasonable"
text it gives a good distribution of hash numbers (a big problem
to solve in general).  The crc16 function I list below uses nibbles
to build the crc from each byte, this is faster than a bit by bit and
less room than a 256 entry table needed for a byte by byte (fits
in cache).  So, it is fast (no multiply, just shifts and masks),
well behaved and simple.  If you have a VAX you could even use the
"crc" instruction instead of the crc16 function - what a CISC.
To use, do a crc16 on the string and the truncate the 16 bit
result to the size you need (this should be a power of 2).


/*	crc16 - crc16 routine
 *
 *	R.K. Irvine
 *
 *	This routine returns the crc16 for the string pointed
 *	to by "in".
 *	crc16 is given by:  x^16 + x^15 + x^2 + 1
 */
unsigned short
crc16(register char *in) {
	register unsigned int	n, crc;

	static unsigned short crc16l[] = {
		0x0000,0xc0c1,0xc181,0x0140,
		0xc301,0x03c0,0x0280,0xc241,
		0xc601,0x06c0,0x0780,0xc741,
		0x0500,0xc5c1,0xc481,0x0440,
	};

	static unsigned short crc16h[] = {
		0x0000,0xcc01,0xd801,0x1400,
		0xf001,0x3c00,0x2800,0xe401,
		0xa001,0x6c00,0x7800,0xb401,
		0x5000,0x9c01,0x8801,0x4400,
	};

	crc = 0;
	while (n = (unsigned char)(*in++)) {	
		n ^= crc;
		crc = crc16l[n&0x0f] ^ crc16h[(n>>4)&0x0f] ^ (crc>>8);
	}
	return(crc);
}


                **** Linked Lists ****
/********************************** 
 * Linked Linear List Trial Program
 **********************************
 */
#include <stdio.h>

typedef struct _list_item {
  int               val;
  struct _list_item *next;
} list_item;


list_item *add_list_item();
list_item *head=NULL;
list_item *tail=NULL;

main()
{
  tail=add_list_item(tail,20);
  tail=add_list_item(tail,25);
  tail=add_list_item(tail,30);

  print_list_items();
}

list_item *add_list_item(entry, value)
     list_item *entry;
     int value;
{
  list_item *new_list_item;

  new_list_item=(list_item*)malloc(sizeof(list_item));
  if (entry==NULL){
    head=new_list_item;
    printf("First list_item in list\n");
  }
  else {
    entry->next = new_list_item;
    printf("Adding %d to list. Last value was %d \n",value,entry->val);
  }
  new_list_item->val  = value;
  new_list_item->next = NULL;
  return new_list_item;
}

print_list_items()
{
  list_item *ptr_to_list_item;

  for (ptr_to_list_item= head;ptr_to_list_item!= NULL; ptr_to_list_item=ptr_to_list_item->next) {
    printf("Value is %d \n", ptr_to_list_item->val);
  }
}



                    *** Trees ***
/*compile using gcc */
#include <stdio.h>
#include <stdlib.h>

#define TRUE	1
#define FALSE	0

struct node {
   int key;
   int count;
   struct node *left;
   struct node *right;
   int bal;
};

int search(int x, struct node **p)
{
   struct node *p1, *p2;
   int h;

   if (*p == NULL) {
      *p          = (struct node *) malloc(sizeof (struct node));
      (*p)->key   = x;
      (*p)->count = 1;
      (*p)->left  = NULL;
      (*p)->right = NULL;
      (*p)->bal   = 0;
      return(TRUE);
   };
   if (x == (*p)->key) {
      (*p)->count++;
      return(FALSE);
   };
   if (x < (*p)->key) {
      if ((h=search(x, &((*p)->left))) == TRUE)
	 switch ((*p)->bal) {
	    case 1:  (*p)->bal = 0;
		     return(FALSE);
	    case 0:  (*p)->bal = -1;
		     return(h);
	    case -1: p1 = (*p)->left;
		     if (p1->bal == -1) {
			(*p)->left = p1->right;
			p1->right  = *p;
			(*p)->bal  = 0;
			*p         = p1;
		     } else {
			p2         = p1->right;
			p1->right  = p2->left;
			p2->left   = p1;
			(*p)->left = p2->right;
			p2->right  = *p;
			(*p)->bal  = (p2->bal == -1?  1 : 0);
			p1->bal    = (p2->bal ==  1? -1 : 0);
			*p         = p2;
		     }
		     (*p)->bal = 0;
		     return(FALSE);
	 };
   } else {
      if ( (h=search(x, &((*p)->right))) == TRUE)
	 switch ((*p)->bal) {
	    case -1: (*p)->bal = 0;
		     return(FALSE);
	    case 0:  (*p)->bal = 1;
		     return(h);
	    case 1:  p1 = (*p)->right;
		     if (p1->bal == 1) {
			(*p)->right = p1->left;
			p1->left    = *p;
			(*p)->bal   = 0;
			*p          = p1;
		     } else {
			p2          = p1->left;
			p1->left    = p2->right;
			p2->right   = p1;
			(*p)->right = p2->left;
			p2->left    = *p;
			(*p)->bal   = (p2->bal ==  1? -1 : 0);
			p1->bal     = (p2->bal == -1?  1 : 0);
			*p          = p2;
		     }
		     (*p)->bal = 0;
		     return(FALSE);
	 }
   }
}

void visit(struct node *p)
{
   if (p != NULL) {
      printf("%d(%d)", p->key, p->bal);
      if (p->left != NULL)
	 printf("\tl:%d", p->left->key);
      if (p->right != NULL)
	 printf("\tr:%d", p->right->key);
      printf("\n");
      visit(p->left);
      visit(p->right);
   }
}

main()
{
   int i, j;
   struct node *root;
   root = (struct node *) NULL;
   for (i = 0; i < 20; i++) {
      j = rand() % 100;
      printf("-----%d-----\n", j);
      search(j, &root);
      visit(root);
   }
}





                    *** Forking ***

main(){
   int pid, status, died;
   switch(pid=fork()){
      case -1: printf("can't fork\n");
               exit(-1);
      case 0 : printf("I'm the child.\n");
               exit(3);
      default: printf("I'm the parent.\n");
               died= wait(&status);
               printf("The child, pid= %d, has returned %d.\n",pid,status>>8);
               printf("It sent a %d signal to parent\n",(status & 0xff));

  }
}