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));
}
}