l_func.c

来自「一个简单的数据库管理工具」· C语言 代码 · 共 808 行 · 第 1/2 页

/*		info;
 */
int
liuascend( LNODE **first, LNODE **last, PFI cmp_f, void *info)
{
	register LNODE	*new, *n;
	register short	val;
	for( n= (*first); n!=NULL_LNODE; n=n->next) {
		if( (val=(*cmp_f)(n->info, info)) > 0 )
			break;
		else if( val==0 )
			return(2);
	}
	if( (new=(LNODE *)malloc( sizeof(LNODE) )) == NULL_LNODE )
		return(0);
	new->weight = 0;
	new->info = info;
	new->next = n;
	if(n) {
		if(n->prev)	n->prev->next = new;
		new->prev = n->prev;
		n->prev = new;
	} else {
		new->prev = (*last);
		if( (*last) )	(*last)->next = new;
		(*last) = new;
	}
	if( n == (*first))
		(*first) = new;
	return (1);
}
/* LINSASCEND -- Insert an Element into an ASCENDING List.
/*
/*	The compare function, 'cmp_f', must return >0 when the INFO
/*	Inserted is 'Greater Than' another INFO structure.  The 'cmp_f' must
/*	know what a user-malloc'd INFO structure is and what makes one
/*	'Less Than', 'Equal to', and 'Greater Than' another. 
/*
/*	'cmp_f' gets the new INFO struct as its second parameter.
/*	
/*	All Insert functions receive the following paramaters:
/*		*first, 
/*		*last,
/*		cmp_f,
/*		info;
 */
int
linsascend( LNODE **first, LNODE **last, PFI cmp_f, void *info)
{
	register LNODE	*new, *n;
	if( (new=(LNODE *)malloc( sizeof(LNODE) )) == NULL_LNODE )
		return(0);
	new->weight = 0;
	new->info = info;
	for( n= (*first); n!=NULL_LNODE; n=n->next) {
		if( (*cmp_f)(n->info, info) > 0 )
			break;
	}
	new->next = n;
	if(n) {
		if(n->prev)	n->prev->next = new;
		new->prev = n->prev;
		n->prev = new;
	} else {
		new->prev = (*last);
		if( (*last) )	(*last)->next = new;
		(*last) = new;
	}
	if( n == (*first))
		(*first) = new;
	return (1);
}
/* LINSQUEUE -- Insert an Element into a QUEUE.
/*
/*	A QUEUE --ALWAYS-- Inserts at LAST Element.  Thats what a QUEUE is.
/*
/*	All Insert functions receive the following paramaters:
/*		*first, 
/*		*last,
/*		cmp_f,
/*		info;
 */
int
linsq( LNODE **first, LNODE **last, PFI cmp_f, void *info)
{
	register LNODE	*new;
	if( (new=(LNODE *)malloc( sizeof(LNODE) )) == NULL_LNODE )
		return(0);
	new->weight	= 0;
	new->prev 	= (*last);
	if( new->prev )
		new->prev->next = new;
	new->next	= NULL_LNODE;
	new->info	= info;
	(*last)		= new;
	if( (*first) == NULL_LNODE )
		(*first)	= (*last);
	return(1);
}
/* LINSBTREE -- Insert an Element into a BTREE List.
/*
/*	The compare function, 'cmp_f', must return <0 when the INFO
/*	Inserted is 'Less Than' another INFO structure.  The 'cmp_f' must
/*	know what a user-malloc'd INFO structure is and what makes one
/*	'Less Than', 'Equal to', and 'Greater Than' another. 
/*
/*	'cmp_f' gets the new INFO struct as its second parameter.
/*
/*	All Insert functions receive the following paramaters:
/*		*first, 
/*		*last,
/*		cmp_f,
/*		info;
 */
int
linsbtree( LNODE **first, LNODE **last, PFI cmp_f, void *info)
{
	register int	ret;

	if((*first) == NULL_LNODE) {
		if( ((*first)=(LNODE *)malloc( sizeof(LNODE) )) == NULL_LNODE )
			return(0);
		(*first)->weight = 0;
		(*first)->info   = info;
		(*first)->prev   = NULL_LNODE;
		(*first)->next   = NULL_LNODE;
		return (1);
	}
	ret = (*cmp_f)((*first)->info, info);
	if(ret>0) {
		return(linsbtree( &((*first)->prev),last,cmp_f,info));
	}
	if(ret<0) {
		return(linsbtree( &((*first)->next),last,cmp_f,info));
	}
	/* DUPLICATE */
	return(-2);
}
void
rot_prev( LNODE **lnode )
{
	LNODE **tmp;

	tmp = &((*lnode)->next);
	(*lnode)->next = (*tmp)->prev;
	(*tmp)->prev   = *lnode;
	lnode          = tmp;
}

void
rot_next( LNODE **lnode )
{
	LNODE **tmp;

	tmp = &((*lnode)->prev);
	(*lnode)->prev = (*tmp)->next;
	(*tmp)->next   = *lnode;
	lnode          = tmp;
}

/* L SCAN LIST -- Scan a regular LINKED-LIST. Start at first,
/*	walk each next till end.
/*	Call scan_f at each NODE.
/*
/*	Break off scan if any scan_f returns a 0.
 */
int
lscanl(LNODE *first,int size,PFV scan_f)
{
	register LNODE	*tmp;
	for( tmp=first; tmp!=NULL_LNODE; tmp=tmp->next)
		if( ((*scan_f)(tmp->info)) == 0 )
			return(0);
	return(1);
}

/* SCAN BTREE -- Walk a BTREE LINKED-LIST.
/*	Call scan_f at each NODE.
/*
/*	Break off scan if any scan_f returns a 0.
 */
int
lscanbt(LNODE *first,int size,PFV scan_f)
{
	if(first==NULL_LNODE)
		return(1);	/* This is OK, will happen normally
				/* At each leaf.
				 */

	if(lscanbt(first->prev,size,scan_f) == 0)
		return(0);

	if( ((*scan_f)((first)->info)) == 0 )
		return(0);

	if(lscanbt(first->next,size,scan_f) == 0)
		return(0);
	return(1);
}

/*
/* HASH FUNCTIONS 
 */
#define HASHTABLESIZE 211
static int
GetHashKey(char *pKey)
{
    unsigned long g, h = 0;
    while(*pKey){
	h = (h << 4) + toupper(*pKey++);
	g = h & 0xF0000000L;
	if(g) { h ^=g >> 24; }
	h &= ~g;
    }
    return( h % HASHTABLESIZE);
}

int
linshash( LNODE **first, LNODE **last, PFI cmp_f, void *info)
{
    char *pKey; 
    int iHashIndex;
    LNODE **ppLnode;

    if( (*first)== NULL_LNODE) {
	(*first)= (LNODE*)calloc( HASHTABLESIZE, sizeof(LNODE*) );
		/* I know, I know this really points to an array
		/* of those, but this is the defined structure
		/* of the LIST, so....
		 */
    }
    ppLnode = (LNODE**)(*first);

    /* Get HASH KEY
     */
    pKey = (char *)(*cmp_f)(info);
			/* User supplied function returns the character
			/* string that represnts the HASH KEY
			 */
    if(pKey) {
	char *pKey2;
	register LNODE	*new,
			*pTmp;

	iHashIndex = GetHashKey(pKey);

	if( (new=(LNODE *)malloc( sizeof(LNODE) )) == NULL_LNODE )
		return(0);
	new->weight	= 0;
	new->info	= info;

	/*
	/* fprintf(stderr,"Adding:%s\n",pKey);
	/* fflush (stderr);
	 */

	/* Search the "prev" list for match
	 */ 
	for( new->next=NULL_LNODE, pTmp=ppLnode[iHashIndex]
	    ;pTmp
	    ;new->next=pTmp, pTmp=pTmp->prev)
	{
	    pKey2 = (char *)(*cmp_f)(pTmp->info);
	    /*
	    /* Install a Sibling using PUSH semantics
	     */
	    if(strcmp(pKey,pKey2)==0) {
		LNODE	*pTmp2=pTmp;
		while(pTmp2->next) {
		    pTmp2=pTmp2->next;
		}
		pTmp2->next = new;
		new->next = 0;
		new->prev = 0;

	    /*	fprintf(stderr,"S(%d,%s)\n",iHashIndex,pKey);
	    /*	fflush(stderr);
	     */
		return(1);
	    }
	}
	if(new->next)	/* new->next is last ELEMENT on "prev" list */
	     new->next->prev = new;
	else ppLnode[iHashIndex]=new; /* I'm first */
	new->next = NULL_LNODE;	/* I've got no Siblings/Dups */
	new->prev = NULL_LNODE;	/* I'm LAST on the LIST */
	
	/*
	/* fprintf(stderr,"C(%d,%s)\n",iHashIndex,pKey);
	/* fflush(stderr);
	 */

	return(1);
    }
    return(0);
}
void *
ldelhash(LNODE **first, LNODE **last,LNODE ** current)
{
    register LNODE *pTmp = (*current);
    register void *pInfo;

    if(!(*current))
	return( (void*)0 );
    /* If this node has a "sibling"
     */
    if( (*current)->next ) {
	if( (*current)->prev ) 
	    (*current)->prev = (*current)->next;
	(*current)= (*current)->next;
    } else if( (*current)->prev ) {
	(*current)= (*current)->prev;
    }
    pInfo = pTmp->info;
    free( (pTmp) );

    return(pInfo);
}
LNODE *
lfindhash(LNODE **first, LNODE **last, int size, PFI cmp_f, void *cmp_i)
{
    char *pKey, *pKey2; 
    int iHashIndex;
    LNODE **ppLnode, *pTmp;

    if( (*first)== NULL_LNODE) {
	return( NULL_LNODE );
    }
    ppLnode = (LNODE**)(*first);

    /* Get HASH KEY
     */
    pKey = (char *)(*cmp_f)(cmp_i);
			/* User supplied function returns the character
			/* string that represnts the HASH KEY
			 */
    if(pKey) {
	iHashIndex = GetHashKey(pKey);

	for( pTmp=ppLnode[iHashIndex]; pTmp!=NULL_LNODE; pTmp=pTmp->prev) {
	    pKey2 = (char *)(*cmp_f)(pTmp->info);
	    /* Collision Checking
	    /* fprintf(stderr,"L(%d,%s,%s)\n",iHashIndex,pKey,pKey2);
	    /* fflush(stderr);
	     */

	    if(strcasecmp(pKey,pKey2)==0) {
	    /* if(strcmp(pKey,pKey2)==0) 
	    /*	fprintf(stderr,"H(%d,%s)\n",iHashIndex,pKey2);
	    /*	fflush(stderr);
	     */
		return(pTmp);
	    }
	}
	return( NULL_LNODE );
    }
    return( NULL_LNODE);
}
int
lscanhash(LNODE *first,int size,PFV scan_f)
{
    int i;
    LNODE **ppLnode, *pInd, *pColl, *pSib;

    ppLnode = (LNODE**) first;
    for(i=0; i<HASHTABLESIZE;++i){
	pInd = ppLnode[i];

	if(!pInd)
	    continue;

	for(pColl=pInd; pColl; pColl = pColl->prev){
	    if( pColl->info && ((*scan_f)((pColl)->info)) == 0 ) {
		return(0);
	    }
	    for(pSib=pColl->next;pSib;pSib=pSib->next){
		if(pColl->info && ((*scan_f)((pSib)->info)) == 0 ) {
		    return(0);
		}
	    }
	}
    }
    
    return(0);
}

/* Place holder functions 
 */
int
lnullpfi()
{
	return(0);
}
void *
lnullpfv()
{
	return((void *)0);
}
LNODE *
lnullpfn()
{
	return(NULL_LNODE);
}