pgpenumeratedset.c

PGP8.0源码 请认真阅读您的文件包然后写出其具体功能

/*____________________________________________________________________________
	Copyright (C) 2002 PGP Corporation
	All rights reserved.

	$Id: pgpEnumeratedSet.c,v 1.18 2002/08/06 20:11:00 dallen Exp $
____________________________________________________________________________*/
/*
 * pgpEnumeratedSet.c -- Arbitrary enumerated subset variant of pgpKeySet
 */
#include "pgpConfig.h"

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include <string.h>
#include <ctype.h>

#include "pgpKeyPriv.h"
#include "pgpDebug.h"
#include "pgpErrors.h"
#include "pgpTypes.h"
#include "pgpMem.h"
#include "pgpContext.h"


/* An entry representing an object in the set */
typedef struct ObjEntry
{
	PGPKeyDBObj		*obj;
	PGPInt32		numChildren;
} ObjEntry;
#define kAllChildren -1

/* Private data for KeySet of type: enumerated subset */
typedef struct EnumeratedSubsetPriv
{
	ObjEntry *		objArray;
	ObjEntry **		keyPointers;		/* Sorted by keyid */
	PGPUInt32		numKeys;
	PGPUInt32		numObjs;
} EnumeratedSubsetPriv;


static PGPError	NewEnumeratedSubsetInternal(PGPKeyDBRef		db,
											PGPKeySetRef *	newSet);


/*
 * Check to see if a (top level) key is a member of an enumerated subset
 * If so return ObjEntry pointer, else return NULL
 */
    static ObjEntry *
sFindKeyMemberOfEnumeratedSubset(
	PGPKeySetRef			set,
	PGPKeyDBObjRef			key)
{
	EnumeratedSubsetPriv *	priv = (EnumeratedSubsetPriv *)set->priv;
	PGPKeyID				keyID;
	PGPInt32				lowerBound;
	PGPInt32				upperBoundPlusOne;
	PGPInt32				indexOfEqualKeyID;
	PGPInt32				indexTry	= 0;
	PGPKeyDBObj *			keyObjTry;
	PGPKeyID				keyIDTry;
	int						comparison;

	pgpa((
		pgpaPGPKeySetValid(set),
		pgpaAddrValid(priv, EnumeratedSubsetPriv),
		pgpaAddrValid(key, char)));

	/* TBD assert object is key */

	/* Get the KeyID */
	pgpKeyID8( key, NULL, &keyID );

	/* Use binary search to find a key in the array with the same KeyID */
	lowerBound = 0;
	upperBoundPlusOne = priv->numKeys;
	while (lowerBound < upperBoundPlusOne)
	{
		indexTry = (lowerBound + upperBoundPlusOne) / 2;
		keyObjTry = priv->keyPointers[indexTry]->obj;
		if (keyObjTry == key)
			return priv->keyPointers[indexTry];	/* Found it! */

		pgpKeyID8( keyObjTry, NULL, &keyIDTry );
		comparison = PGPCompareKeyIDs(&keyID, &keyIDTry);
		if (comparison > 0)
			lowerBound = indexTry + 1;
		else if (comparison < 0)
			upperBoundPlusOne = indexTry;
		else
			break;
	}
	if (lowerBound >= upperBoundPlusOne)
		return NULL;	/* Binary search failed */
	
	/*
	 * We found a key with the same KeyID, but it's not the same key.
	 * Now we search the adjacent keys of equal KeyID looking for the key.
	 */
	indexOfEqualKeyID = indexTry;

	/* First search lower indices */
	while (--indexTry >= lowerBound)
	{
		keyObjTry = priv->keyPointers[indexTry]->obj;
		if (keyObjTry == key)
			return priv->keyPointers[indexTry];	/* Found it! */

		pgpKeyID8( keyObjTry, NULL, &keyIDTry );
		if (0 != PGPCompareKeyIDs(&keyID, &keyIDTry))
			break;
	}

	/* Then search higher indices */
	indexTry = indexOfEqualKeyID;
	while (++indexTry < upperBoundPlusOne)
	{
		keyObjTry = priv->keyPointers[indexTry]->obj;
		if (keyObjTry == key)
			return priv->keyPointers[indexTry];	/* Found it! */

		pgpKeyID8(keyObjTry, NULL, &keyIDTry);
		if (0 != PGPCompareKeyIDs(&keyID, &keyIDTry))
			break;
	}

	/* Now we know for sure it's not in the set */
	return NULL;
}


/*
 * Look for a child object below the specified key pointer.  Should only be
 * used if keyptr's children is not kAllChildren.  Returns the matched
 * child object, or its parent if it matched because of a kAllChildren at
 * the second level.  If object not found returns NULL.
 */
	static ObjEntry *
sFindChildOfKeyMember(
	ObjEntry *		keyptr,
	PGPKeyDBObj *	obj,
	PGPBoolean *	parentfound)
{
	PGPInt32		keychildren, keygrandchildren;
	ObjEntry *		objptr;

	keychildren = keyptr->numChildren;
	pgpAssert( keychildren != kAllChildren );

	objptr = keyptr + 1;

	while( keychildren-- > 0 ) {
		if (objptr->obj == obj) {
			*parentfound = FALSE;
			return objptr;
		}
		keygrandchildren = objptr->numChildren;
		if( keygrandchildren == kAllChildren ) {
			if( objptr->obj == obj->up ) {
				*parentfound = TRUE;
				return objptr;
			}
			++objptr;
		} else {
			++objptr;
			while( keygrandchildren-- > 0 ) {
				if( objptr->obj == obj ) {
					*parentfound = FALSE;
					return objptr;
				}
				++objptr;
			}
		}
	}
	*parentfound = FALSE;
	return NULL;
}


/*
 * Check to see if a keydbobj is a member of an enumerated subset
 */
	static PGPBoolean
IsMemberOfEnumeratedSubset(
	PGPKeySetRef			set,
	PGPKeyDBObjRef			obj)
{
	PGPKeyDBObj *			parent;
	ObjEntry *				keyptr;
	ObjEntry *				objptr;
	PGPBoolean				parentfound;

	if( PGPPeekKeyDBObjKeyDB( obj ) != set->keyDB )
		return FALSE;

	if( pgpObjectType( obj ) == RINGTYPE_KEY )
		return NULL != sFindKeyMemberOfEnumeratedSubset( set, obj );

	for( parent = obj->up; pgpObjectType( parent ) != RINGTYPE_KEY;
		 parent = parent->up )
		;

	keyptr = sFindKeyMemberOfEnumeratedSubset( set, parent );

	if( keyptr == NULL )
		return FALSE;

	if( keyptr->numChildren == kAllChildren )
		return TRUE;

	/*
	 * Here we have only a subset of the children in the set, so we must
	 * search for those.  Do a simple linear search since there usually
	 * aren't very many.
	 */

	objptr = sFindChildOfKeyMember( keyptr, obj, &parentfound );
	
	return objptr != NULL;
}

/* Check to see if the set is empty */
	static PGPBoolean
IsEmptyEnumeratedSubset(
	PGPKeySetRef			set )
{
	EnumeratedSubsetPriv *	priv = (EnumeratedSubsetPriv *)set->priv;
	return (priv->numKeys == 0);
}



/* Utility functions for unioning two enum keysets */

/* Copy key and all its children from given source to given offsets, update
 * offsets.  Return updated src pointer
 */
	static ObjEntry *
sCopyKeyAndChildren( ObjEntry *src, EnumeratedSubsetPriv *priv,
					 PGPUInt32 *objoff, PGPUInt32 *keyptroff )
{
	PGPInt32 numChildren;

	/* Copy first object */
	if( IsntNull( keyptroff ) )
		priv->keyPointers[(*keyptroff)++] = priv->objArray + *objoff;
	priv->objArray[(*objoff)].obj = src->obj;
	priv->objArray[(*objoff)++].numChildren = src->numChildren;

	/* Done if no children to copy */
	numChildren = src->numChildren;
	++src;
	if (numChildren == kAllChildren)
		return src;

	/* Else loop to copy children */
	while( numChildren-- > 0 )
		src = sCopyKeyAndChildren( src, priv, objoff, NULL );

	return src;
}

/* Merge the children of two identical keys.  Update offsets. */
/* Neither key has kAllChildren */
	static void
sMergeChildren( ObjEntry *key1, ObjEntry *key2, EnumeratedSubsetPriv *priv,
				PGPUInt32 *objoff, PGPUInt32 *keyptroff )
{
	PGPInt32 numChildren1, numChildren2;
	PGPInt32 numGrandchildren1, numGrandchildren2;
	PGPInt32 numChildren;
	ObjEntry *obj1, *obj2;
	PGPBoolean parentfound;
	PGPUInt32 childoff;

	pgpAssert( key1->numChildren != kAllChildren );
	pgpAssert( key2->numChildren != kAllChildren );

	obj1 = key1;
	obj2 = key2;

	priv->keyPointers[*keyptroff] = priv->objArray + *objoff;
	priv->objArray[(*objoff)++].obj = obj1->obj;

	numChildren1 = obj1->numChildren;
	numChildren2 = obj2->numChildren;
	numChildren = numChildren1;
	++obj1;

	while( numChildren1-- > 0 ) {
		obj2 = sFindChildOfKeyMember( key2, obj1->obj, &parentfound );
		/* Is this child in number 2? */
		if( IsNull( obj2 ) ) {
			/* Simple case, copy child and its children */
			obj1 = sCopyKeyAndChildren( obj1, priv, objoff, NULL );
		} else {
			/* parentfound is false else key2 would have had kAllChildren */
			pgpAssert( !parentfound );

			/* Now must check for merge at second level */
			/* Copy second level object */
			priv->objArray[(*objoff)].obj = obj1->obj;

			/* See if either one has kAllChildren */
			numGrandchildren1 = obj1->numChildren;
			numGrandchildren2 = obj2->numChildren;
			if( numGrandchildren1 == kAllChildren ) {
				priv->objArray[(*objoff)++].numChildren = kAllChildren;
				obj1++;
				if( numGrandchildren2 != kAllChildren )
					obj2 += numGrandchildren2;
				else
					obj2++;
			} else if( numGrandchildren2 == kAllChildren ) {
				priv->objArray[(*objoff)++].numChildren = kAllChildren;
				obj2++;
				obj1 += numGrandchildren1;
			} else {
				/* Must do item by item merge at third level */
				/* First copy all items from 1, then missing items from 2 */
				childoff = *objoff;
				++obj1;
				while( numGrandchildren1-- > 0 ) {
					priv->objArray[(*objoff)].obj = obj1->obj;
					priv->objArray[(*objoff)++].numChildren = 0;
					++obj1;
				}
				while( numGrandchildren2-- > 0 ) {
					++obj2;
					if( IsNull( sFindChildOfKeyMember( key1, obj2->obj,
													   &parentfound ) ) ) {
						/* Key2 grandchild not in key1, copy it */
						priv->objArray[(*objoff)].obj = obj2->obj;
						priv->objArray[(*objoff)++].numChildren = 0;
						++obj2;
					}
				}
				/* Update numChildren on childoff */
				priv->objArray[childoff].numChildren = (*objoff) - childoff;
			}
		}
	}

	/* Now copy remaining second level items from key2 that aren't in key1 */

	obj2 = key2 + 1;
	while( numChildren2-- > 0 ) {
		if( IsNull( sFindChildOfKeyMember( key1, obj2->obj, &parentfound ))) {
			obj2 = sCopyKeyAndChildren( obj2, priv, objoff, NULL );
			++numChildren;
		} else {
			/* Skip this, it has already been done */
			numGrandchildren2 = obj2->numChildren;
			if( numGrandchildren2 == kAllChildren )
				++obj2;
			else
				obj2 += numGrandchildren2;
		}
	}

	/* Update numChildren for top level merged key */
	priv->keyPointers[(*keyptroff)++]->numChildren = numChildren;
}


	static PGPError
MakeUnionOfEnumeratedSubsets(
	PGPKeySetRef		set1,
	PGPKeySetRef		set2,
	PGPKeySetRef *		newSet)
{
	PGPContextRef			context	= PGPPeekKeySetContext(set1);
	EnumeratedSubsetPriv *	priv1 = (EnumeratedSubsetPriv *)set1->priv;
	EnumeratedSubsetPriv *	priv2 = (EnumeratedSubsetPriv *)set2->priv;
	EnumeratedSubsetPriv *	priv;
	ObjEntry **				keyPtr1 = priv1->keyPointers;
	ObjEntry **				keyPtr2 = priv2->keyPointers;
	PGPKeyID				keyID1;
	PGPKeyID				keyID2;
	PGPKeySetRef			set;
	PGPUInt32				in1;