mccarrol@athos.rutgers.edu (Mark C. Carroll <MC>) (12/08/89)
Here's a quick example of a way to use minimal OO techniques in a
non-OO language. Not that there is no way to insure that the user
doesn't break the rules and intrude into internals, you basically
assume that any bozo who does gets what's coming to him.
#--------------------CUT HERE--------------------
# This is a shell archive.
# Remove everything above this line and
# run the following text with /bin/sh to create:
# Makefile
# README
# btree.c
# btree.h
# This archive created: Thu Dec 7 13:24:04 1989
cat << 'SHAR_EOF' > Makefile
all: btree
btree.o: btree.c
@echo "********* Compiling *********"
@echo "**This will give 4 warnings**"
cc -c btree.c
btree: btree.o
@echo "********** Linking **********"
cc -o btree btree.o
SHAR_EOF
cat << 'SHAR_EOF' > README
This is the CS435 assignment for Mark C. Carroll, Student Number 299288.
This was posted to comp.object as an example of minimal OO techniques
used in C. I don't claim it to be a terrible good example, but it
shows an example of how it could be done.
<MC>
*****************************************************************************
The enclosed files are:
README: this file.
Makefile: a makefile to compile the program. Just type "make", and sit back
and enjoy!
btree.c: the actual C code for the program.
btree.h: the header file for btree.c.
SHAR_EOF
cat << 'SHAR_EOF' > btree.c
/******************************
** Computer Science 435
** Programming Assignment 1
** B-Tree Insertion
******************************
B-tree code file
<MC> */
#include "btree.h"
int TreeOrder = 0;
/************************************************************
** The Main Program
**/
main()
{
char input[80];
btree bt;
int i;
printf("\n");
printf("Computer Science 435 --- B-Tree Insertion Program\n");
printf("Written by Mark C. Carroll\n");
printf("========================================\n");
(void)gets(input);
printf("\n");
TreeOrder=atoi(input);
if (TreeOrder < 3) {
printf("The TreeOrder must be greater than 2\n");
exit(-1);
}
bt = btree_New();
while (!feof(stdin)) {
(void)gets(input);
i = atoi(input);
if (feof(stdin)) break;
if (i==-1) {
btree_Print(bt);
printf("========================================\n");
}
else
bt = btree_InsertNewKey(bt,i);
}
}
/************************************************************
** The Btree Functions
**/
btree btree_InsertNewKey(bt,key)
btree bt;
val key;
{
btree where;
where = btree_Find(bt,key);
return btree_Insert(where,key,(btree)NULL);
}
btree btree_New()
/* Create a completely empty btree node, and
* return its pionter
*/
{
btree bt;
int lo;
bt = (btree)malloc(sizeof(struct btree_struct));
bt->parent = NULL;
bt->num_entries = 0;
bt->child = (btree *)calloc(TreeOrder,sizeof(btree));
for (lo=0;lo<TreeOrder;lo++) bt->child[lo]=NULL;
bt->values = (val *)calloc(TreeOrder-1,sizeof(val));
for (lo=0;lo<TreeOrder-1;lo++) bt->values[lo]=0;
return bt;
}
btree btree_Find(bt,key)
btree bt;
val key;
{
int lo;
/* if the node has no children, then we have reached a leaf, so this
* is the desired location of the key
*/
if (bt->child[0] ==NULL)
return bt;
/* if there are children, search the values for the proper position */
for (lo = 0;lo<bt->num_entries;lo++)
if (key<bt->values[lo])
return btree_Find(bt->child[lo],key); /* and search the child */
/* If it's bigger than any, search the largest child. */
return btree_Find(bt->child[bt->num_entries],key);
}
btree btree_Insert(bt,key,ptr)
/* Insert the key/ptr pair into the current node. This
* assumes that we have already used btree_Find() to
* locate the proper node to insert into
*/
btree bt;
val key;
btree ptr;
{
if (bt->num_entries == (TreeOrder-1)) /* If node is full */
return btree_Split(bt,key,ptr); /* split */
else { /* else insert into place */
int posorig;
val pivot=key;
btree pivotptr=ptr;
for (posorig=0;posorig<bt->num_entries;posorig++) {
if (bt->values[posorig]>pivot) {
swapval(&pivot,&(bt->values[posorig]));
swappointer(&pivotptr,&(bt->child[posorig+1]));
}
}
/* By the above loop, pivot will always be the
* largest value after the last iteration, so put it
* into the last place */
bt->values[bt->num_entries]=pivot;
bt->child[bt->num_entries+1]=pivotptr;
bt->num_entries++;
}
{
/* Find the root of the tree using parent pointers, and return it */
btree retbt=bt;
while (retbt->parent != NULL)
retbt=retbt->parent;
return retbt;
}
}
btree btree_Split(bt,key,ptr)
btree bt;
val key;
btree ptr;
{
btree newnode=btree_New(); /* The new node */
iterator it=it_New(bt,key,ptr); /* init the iterator */
int lo,count=0;
val median;
/* Put lower half of keys into old node */
for (lo=0;lo<=(TreeOrder-1)/2-1;lo++) {
it_Next(it,&bt->values[lo],&bt->child[lo+1]); /* low half */
count++;
}
/* Store the median, set the low pointer of the new node */
it_Next(it,&median,&newnode->child[0]); /* median */
/* put upper half of keys into new node */
for (lo=0;lo<=(TreeOrder-count-2);lo++)
it_Next(it,&newnode->values[lo],&newnode->child[lo+1]);
/* Set up numentries in each node */
bt->num_entries=count;
newnode->num_entries = TreeOrder-count-1;
/* Set backpointers */
newnode->parent = bt->parent;
it_Kill(it); /* Kill the iterator */
/* If we are splitting the root, build a new root */
if (bt->parent == NULL)
return btree_SplitRoot(median,bt,newnode);
else
/* Otherwise, insert the median and the pointer to the new node
* into the parent node
*/
return btree_Insert(bt->parent,median,newnode);
}
btree btree_SplitRoot(key,old,new)
/* Build a new root node */
val key;
btree old,new;
{
btree bt;
bt = btree_New();
bt->num_entries=1;
bt->values[0]=key;
bt->child[0]=old;
bt->child[1]=new;
old->parent=bt;
new->parent=bt;
bt->parent=0;
return bt;
}
void btree_Print(bt)
/* A simple interface to the actual print routine. The real print
* uses two variables to keep track of visit order, and indentation
* level. This is a top level interface that creates the initial value
* of those two values.
*/
{
int visit=0,level=0;
printf("Depth\tVisit\tKeys\n ");
btree_Print1(bt,&visit,level);
}
void btree_Print1(bt,visit,level)
btree bt;
int *visit,level;
{
int i;
if(bt==NULL) /* if we've come to a null pointer, just return */
return;
(*visit)++; /* increase the counter for visit order */
printf("%3d\t%3d\t",level,*visit);
for (i=0;i<level;i++) printf(" "); /* indent */
printf("(");
for (i=0;i<bt->num_entries;i++) /* and the keys in the node */
printf("%d%s ",bt->values[i],(i==bt->num_entries-1)?")\n":",");
for (i=0;i<bt->num_entries+1;i++) /* print all of the subtrees,
* with increased indent
*/
btree_Print1(bt->child[i],visit,level+1);
}
/************************************************************
** Iterator Functions
**
** The iterator functions just provide a clean way
** to get the value/ptr pairs in order. it_New()
** creates a data structure used to order the pairs,
** and it_Next() provides an iterative method for
** getting the next pair in order.
**/
iterator it_New(bt,key,ptr)
btree bt;
val key;
btree ptr;
{
int lo;
iterator it=(iterator)malloc(sizeof(struct it_struct));
it->keys=(val *)calloc(TreeOrder,sizeof(val));
it->ptrs=(generic *)calloc(TreeOrder,sizeof(generic));
/* This rest of the code to this function is basically a
* single step from an insertion sort
*/
for (lo=0;lo<TreeOrder-1;lo++) {
if (key < bt->values[lo]) {
it->keys[lo] = key;
it->ptrs[lo] = (generic)ptr;
key = bt->values[lo];
ptr = bt->child[lo+1];
}
else {
it->keys[lo] = bt->values[lo];
it->ptrs[lo] = (generic)bt->child[lo+1];
}
}
it->keys[TreeOrder-1] = key;
it->ptrs[TreeOrder-1] = (generic)ptr;
/* Set the initial position in the list to zero */
it->pos = 0;
return it;
}
void it_Next(it,key,ptr)
iterator it;
val *key;
btree *ptr;
{
/* Return the value/ptr pair in the current position in the list */
*key = it->keys[it->pos];
*ptr = (btree)it->ptrs[it->pos];
it->pos++; /* and advance the pointer to the next */
if (it->pos == TreeOrder)
it->pos = 0;
}
void it_Kill(it)
/* Free the memory used by the iterator once we're done with it */
iterator it;
{
free(it->ptrs);
free(it->keys);
free(it);
}
/****************************************
** Swap Functions for btree_Insert()
**/
void swapval(a,b)
val *a,*b;
{
val c;
c = *a;
*a = *b;
*b = c;
}
void swappointer(a,b)
generic *a;
generic *b;
{
generic c;
c = *a;
*a = *b;
*b = c;
}
SHAR_EOF
cat << 'SHAR_EOF' > btree.h
/******************************
** Computer Science 435
** Programming Assignment 1
** B-Tree Insertion
******************************
Header File
<MC> */
#include <stdio.h>
/* First, my standard generics that I like to have *
* available if I chose to use them: */
typedef enum { False=0, True=(-1) } boolean;
typedef char *generic; /* The Dreaded Generic Datatype */
extern char *malloc();
extern char *calloc();
extern char *gets();
/* Now, the data structures specific to the program: */
typedef int val; /* typedef'd so that I can change the meaning
* of what a val is simply.
*/
/*
* The data structure that I've created represents a btree
* as a quadruple: ( parent, numentries, child, value )
* where:
* parent is a pointer to the parent node
* numentries is the number of values in the node
* child is an array of children nodes [0..numentries]
* value is an array of values. [0..numentries-1]
*/
typedef struct btree_struct {
struct btree_struct *parent;
int num_entries;
struct btree_struct *(*child); /* pointer to an array of pointers to btree */
val *values; /* pointer to array of values */
} *btree;
/* Prototypes for btree functions: */
btree btree_New();
btree btree_Find();
btree btree_Insert();
btree btree_Split();
btree btree_SplitRoot();
btree btree_InsertNewKey();
/* See the comments by it_New(), it_Next() for an explanation
* of the iterator
*/
typedef struct it_struct {
val *keys;
generic *(*ptrs);
int pos;
} *iterator;
/* Prototypes for Iterator functions */
iterator it_New();
void it_Next();
void it_Kill();
/* Prototypes */
void swapval();
void swappointer();
/*
* The only functions that the User is allowed to see are:
btree btree_New();
btree btree_Find();
btree btree_Insert();
void btree_Print();
*/
SHAR_EOF
# End of shell archive
exit 0
--
\ Mark Craig Carroll: <MC> \ "Don't ever think that you can't
\ Student Systems Programmer - LCSR \ change the past and the future"
\ Rutgers University \ -Kate Bush
\ mccarrol@topaz.rutgers.edu \ (standard disclaimer applies)