⟦064530319⟧

TextFile

/* turbo_load.c - Quickly check for duplicate RDN's (from Tim Howes) */

#ifndef	lint
static char *rcsid = "$Header: /f/osi/quipu/RCS/turbo_load.c,v 7.0 89/11/23 22:20:57 mrose Rel $";
#endif

/* 
 * $Header: /f/osi/quipu/RCS/turbo_load.c,v 7.0 89/11/23 22:20:57 mrose Rel $
 *
 *
 * $Log:	turbo_load.c,v $
 * Revision 7.0  89/11/23  22:20:57  mrose
 * Release 6.0
 * 
 */

/*
 *				  NOTICE
 *
 *    Acquisition, use, and distribution of this module and related
 *    materials are subject to the restrictions of a license agreement.
 *    Consult the Preface in the User's Manual for the full terms of
 *    this agreement.
 *
 */



#include <sys/types.h>
#include <sys/stat.h>

#include "quipu/util.h"
#include "quipu/entry.h"
#include "quipu/malloc.h"

extern LLog * log_dsap;

extern int turbo_size;
extern int turbo_name_size;

static struct node {
	char *name;
	struct node *left;
	struct node *right;
	int bf;
};

static struct node *node_heap;
static struct node *node_next;

static char *name_heap;
static char *name_next;

static struct node *root;
static long count;
static long comparisons;
static long entries;

turbo_start(file)
FILE *file;
{
	struct stat buf;
	int save_heap;

	if ( fstat(fileno(file), &buf) != 0 ) {
		LLOG (log_dsap, LLOG_EXCEPTIONS,("turbo: could not get filesize"));
		return FALSE;
	}

	/* 
	 * This is a heuristic based on some edb file sizes at
	 * UM.  If you find this isn't enough, try using
	 * a smaller turbo_size (in quiputailor).  This should
	 * eventually be fixed to malloc more if the heuristic
	 * turns out not to be enough.
	*/
	entries = (buf.st_size) / turbo_size;
	if ( entries < 100 ) entries = 100;

	save_heap = mem_heap;
	GENERAL_HEAP
	node_heap = (struct node *) calloc( (unsigned)entries, sizeof(struct node) );
	node_next = node_heap;
	name_heap = (char *) calloc( (unsigned)entries, (unsigned)turbo_name_size );
	name_next = name_heap;
	mem_heap = save_heap;
	root = 0;
	count = 0;
	comparisons = 0;

	return TRUE;
}

turbo_insert(name)
RDN name;
{
	int taller;

	if ( ++count >= entries ) {
		if (count == entries)
			LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - decrease turbo_size (currently %d - %d entries read)",turbo_size,entries));
		/* should realloc */
		return OK;
	}

	if (strlen ((char *) name->rdn_av.av_struct) >= turbo_name_size) {
		LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - increase turbo_name_size (%d required for '%s', currently %d)",
			strlen ((char *) name->rdn_av.av_struct),
			(char *)name->rdn_av.av_struct, turbo_name_size));
		/* should realloc */
		return OK;
	}

	return (avl_insert(&root, (char *) name->rdn_av.av_struct, &taller));
}

#define LH 	-1
#define EH 	0
#define RH 	1
#define ROTATERIGHT(x)	{ struct node *tmp;\
	if ( *x == NULL || (*x)->left == NULL ) {\
		(void) printf("RR error\n"); exit(1); \
	}\
	tmp = (*x)->left;\
	(*x)->left = tmp->right;\
	tmp->right = *x;\
	*x = tmp;\
}
#define ROTATELEFT(x)	{ struct node *tmp;\
	if ( *x == NULL || (*x)->right == NULL ) {\
		(void) printf("RL error\n"); exit(1); \
	}\
	tmp = (*x)->right;\
	(*x)->right = tmp->left;\
	tmp->left = *x;\
	*x = tmp;\
}


static avl_insert(iroot, name, taller)
struct node **iroot;
char *name;
int *taller;
{
	int rc, cmp, tallersub;
	struct node *l, *r;

	comparisons++;
	if ( *iroot == 0 ) {
		*iroot = node_next++;
		(*iroot)->left = 0;
		(*iroot)->right = 0;
		(*iroot)->bf = 0;
		(*iroot)->name = name_next;
		while ( *(name_next++) = *(name++) );
		*taller = 1;
		return (OK);
	}

	cmp = strcmp(name, (*iroot)->name);
	/* equal - duplicate name */
	if ( cmp == 0 ) {
		 *taller = 0;
		return (NOTOK);
	}
	/* go right */
	else if ( cmp > 0 ) {
		rc = avl_insert(&((*iroot)->right), name, &tallersub);
		if (tallersub)
			switch ((*iroot)->bf) {
			case LH	: /* left high - balance is restored */
				(*iroot)->bf = EH;
				*taller = 0;
				break;
			case EH	: /* equal height - now right heavy */
				(*iroot)->bf = RH;
				*taller = 1;
				break;
			case RH	: /* right heavy to start - right balance */
				r = (*iroot)->right;
				switch (r->bf) {
				case LH	: /* double rotation left */
					l = r->left;
					switch (l->bf) {
					case LH	: (*iroot)->bf = EH;
						  r->bf = RH;
						  break;
					case EH	: (*iroot)->bf = EH;
						  r->bf = EH;
						  break;
					case RH	: (*iroot)->bf = LH;
						  r->bf = EH;
						  break;
					}
					l->bf = EH;
					ROTATERIGHT((&r))
					(*iroot)->right = r;
					ROTATELEFT(iroot)
					*taller = 0;
					break;
				case EH	: /* This should never happen */
					break;
				case RH	: /* single rotation left */
					(*iroot)->bf = EH;
					r->bf = EH;
					ROTATELEFT(iroot)
					*taller = 0;
					break;
				}
				break;
			}
		else
			*taller = 0;
	}
	/* go left */
	else {
		rc = avl_insert(&((*iroot)->left), name, &tallersub);
		if (tallersub)
			switch ((*iroot)->bf) {
			case LH	: /* left high to start - left balance */
				l = (*iroot)->left;
				switch (l->bf) {
				case LH	: /* single rotation right */
					(*iroot)->bf = EH;
					l->bf = EH;
					ROTATERIGHT(iroot)
					*taller = 0;
					break;
				case EH	: /* this should never happen */
					break;
				case RH	: /* double rotation right */
					r = l->right;
					switch (r->bf) {
					case LH	: (*iroot)->bf = RH;
						  l->bf = EH;
						  break;
					case EH	: (*iroot)->bf = EH;
						  l->bf = EH;
						  break;
					case RH	: (*iroot)->bf = EH;
						  l->bf = LH;
						  break;
					}
					r->bf = EH;
					ROTATELEFT((&l))
					(*iroot)->left = l;
					ROTATERIGHT(iroot)
					*taller = 0;
					break;
				}
				break;
			case EH	: /* equal height - now left heavy */
				(*iroot)->bf = LH;
				*taller = 1;
				break;
			case RH	: /* right high - balance is restored */
				(*iroot)->bf = EH;
				*taller = 0;
				break;
			}
		else
			*taller = 0;
	}
	return(rc);
}

turbo_end()
{
	DLOG (log_dsap,LLOG_DEBUG,("turbo %d entries unused",entries - count));
	free(name_heap);
	free((char *)node_heap);
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦064530319⟧ TextFile

Derivation

TextFile
