idl.c

开放源码的ldap系统

				/* FALL */

			case 2:		/* id already there - how? */
			case 0:		/* id inserted: this can never be
					 * the result of idl_insert, because
					 * we guaranteed that idl_change_first
					 * will always be called.
					 */
				if ( rc == 2 ) {
					Debug( LDAP_DEBUG_ANY,
					    "idl_insert_key: id %ld already in next block\n",
					    id, 0, 0 );
				}

				idl_free( tmp );
				idl_free( tmp2 );
				idl_free( idl );
				return( 0 );

			case 3:		/* split the original block */
				break;
			}

			idl_free( tmp2 );
		}

split:
		/*
		 * must split the block, write both new blocks + update
		 * and write the indirect header block.
		 */

		rc = 0;	/* optimistic */


		/* count how many indirect blocks *//* XXX linear count XXX */
		for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
			;	/* NULL */

		/* check it against all-id thresholed */
		if ( j + 1 > db->dbc_maxindirect ) {
			/*
			 * we've passed the all-id threshold, meaning
			 * that this set of blocks should be replaced
			 * by a single "all-id" block.  our job: delete
			 * all the indirect blocks, and replace the header
			 * block by an all-id block.
			 */

			/* delete all indirect blocks */
			for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) {
				cont_id( &k2, ID_BLOCK_ID(idl, j) );

				rc = ldbm_cache_delete( db, k2 );
			}

			/* store allid block in place of header block */
			idl_free( idl );
			idl = idl_allids( be );
			rc = idl_store( be, db, key, idl );

			cont_free( &k2 );
			idl_free( idl );
			idl_free( tmp );
			return( rc );
		}

		idl_split_block( tmp, id, &tmp2, &tmp3 );
		idl_free( tmp );

		/* create a new updated indirect header block */
		tmp = idl_alloc( ID_BLOCK_NMAX(idl) + 1 );
		ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE;
		/* everything up to the split block */
		AC_MEMCPY(
			(char *) &ID_BLOCK_ID(tmp, 0),
			(char *) &ID_BLOCK_ID(idl, 0),
		    i * sizeof(ID) );
		/* the two new blocks */
		ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0);
		ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0);
		/* everything after the split block */
		AC_MEMCPY(
			(char *) &ID_BLOCK_ID(tmp, i + 2),
			(char *) &ID_BLOCK_ID(idl, i + 1),
			(ID_BLOCK_NMAX(idl) - i - 1) * sizeof(ID) );

		/* store the header block */
		rc = idl_store( be, db, key, tmp );

		/* store the first id block */
		cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
		rc = idl_store( be, db, k2, tmp2 );

		/* store the second id block */
		cont_id( &k2, ID_BLOCK_ID(tmp3, 0) );
		rc = idl_store( be, db, k2, tmp3 );

		idl_free( tmp2 );
		idl_free( tmp3 );
		break;
	}

	cont_free( &k2 );
	idl_free( tmp );
	idl_free( idl );
	return( rc );
}


/*
 * idl_insert - insert an id into an id list.
 *
 *	returns
 * 		0	id inserted
 *		1	id inserted, first id in block has changed
 *		2	id not inserted, already there
 *		3	id not inserted, block must be split
 */
int
idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids )
{
	unsigned int	i;

	if ( ID_BLOCK_ALLIDS( *idl ) ) {
		return( 2 );	/* already there */
	}

	/* is it already there? *//* XXX linear search XXX */
	for ( i = 0; i < ID_BLOCK_NIDS(*idl) && id > ID_BLOCK_ID(*idl, i); i++ ) {
		;	/* NULL */
	}
	if ( i < ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) == id ) {
		return( 2 );	/* already there */
	}

	/* do we need to make room for it? */
	if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAX(*idl) ) {
		/* make room or indicate block needs splitting */
		if ( ID_BLOCK_NMAX(*idl) >= maxids ) {
			return( 3 );	/* block needs splitting */
		}

		ID_BLOCK_NMAX(*idl) *= 2;
		if ( ID_BLOCK_NMAX(*idl) > maxids ) {
			ID_BLOCK_NMAX(*idl) = maxids;
		}
		*idl = (ID_BLOCK *) ch_realloc( (char *) *idl,
		    (ID_BLOCK_NMAX(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
	}

	/* make a slot for the new id */
	AC_MEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i),
	            (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) );

	ID_BLOCK_ID(*idl, i) = id;
	ID_BLOCK_NIDS(*idl)++;
	(void) memset(
		(char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)),
		'\0',
	    (ID_BLOCK_NMAX(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) );

#ifdef LDBM_DEBUG_IDL
	idl_check(*idl);
#endif

	return( i == 0 ? 1 : 0 );	/* inserted - first id changed or not */
}


int
idl_delete_key (
	Backend         *be,
	DBCache  *db,
	Datum           key,
	ID              id
)
{
	Datum  data;
	ID_BLOCK *idl;
	unsigned i;
	int j, nids;

	if ( (idl = idl_fetch_one( be, db, key ) ) == NULL )
	{
		/* It wasn't found.  Hmm... */
		return -1;
	}

	if ( ID_BLOCK_ALLIDS( idl ) ) {
		idl_free( idl );
		return 0;
	}

	if ( ! ID_BLOCK_INDIRECT( idl ) ) {
		for ( i=0; i < ID_BLOCK_NIDS(idl); i++ ) {
			if ( ID_BLOCK_ID(idl, i) == id ) {
				if( --ID_BLOCK_NIDS(idl) == 0 ) {
					ldbm_cache_delete( db, key );

				} else {
					AC_MEMCPY(
						&ID_BLOCK_ID(idl, i),
						&ID_BLOCK_ID(idl, i+1),
						(ID_BLOCK_NIDS(idl)-i) * sizeof(ID) );

					ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID;

					idl_store( be, db, key, idl );
				}

				idl_free( idl );
				return 0;
			}
			/*  We didn't find the ID.  Hmmm... */
		}
		idl_free( idl );
		return -1;
	}
	
	/* We have to go through an indirect block and find the ID
	   in the list of IDL's
	   */
	for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ )
		;	/* NULL */

	cont_alloc( &data, &key );

	for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) 
	{
		ID_BLOCK *tmp;
		cont_id( &data, ID_BLOCK_ID(idl, j) );

		if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) {
			Debug( LDAP_DEBUG_ANY,
			    "idl_delete_key: idl_fetch of returned NULL\n", 0, 0, 0 );
			continue;
		}
		/*
		   Now try to find the ID in tmp
		*/
		for ( i=0; i < ID_BLOCK_NIDS(tmp); i++ )
		{
			if ( ID_BLOCK_ID(tmp, i) == id )
			{
				AC_MEMCPY(
					&ID_BLOCK_ID(tmp, i),
					&ID_BLOCK_ID(tmp, i+1),
					(ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID));
				ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID;
				ID_BLOCK_NIDS(tmp)--;

				if ( ID_BLOCK_NIDS(tmp) ) {
					idl_store ( be, db, data, tmp );

				} else {
					ldbm_cache_delete( db, data );
					AC_MEMCPY(
						&ID_BLOCK_ID(idl, j),
						&ID_BLOCK_ID(idl, j+1),
						(nids-(j+1)) * sizeof(ID));
					ID_BLOCK_ID(idl, nids-1) = NOID;
					nids--;
					if ( ! nids )
						ldbm_cache_delete( db, key );
					else
						idl_store( be, db, key, idl );
				}
				idl_free( tmp );
				cont_free( &data );
				idl_free( idl );
				return 0;
			}
		}
		idl_free( tmp );
	}

	cont_free( &data );
	idl_free( idl );
	return -1;
}


/* return a duplicate of a single ID_BLOCK */
static ID_BLOCK *
idl_dup( ID_BLOCK *idl )
{
	ID_BLOCK	*new;

	if ( idl == NULL ) {
		return( NULL );
	}

	new = idl_alloc( ID_BLOCK_NMAX(idl) );

	AC_MEMCPY(
		(char *) new,
		(char *) idl,
		(ID_BLOCK_NMAX(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );

#ifdef LDBM_DEBUG_IDL
	idl_check(new);
#endif

	return( new );
}


/* return the smaller ID_BLOCK */
static ID_BLOCK *
idl_min( ID_BLOCK *a, ID_BLOCK *b )
{
	return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a );
}


/*
 * idl_intersection - return a intersection b
 */
ID_BLOCK *
idl_intersection(
    Backend	*be,
    ID_BLOCK	*a,
    ID_BLOCK	*b
)
{
	unsigned int	ai, bi, ni;
	ID_BLOCK		*n;

	if ( a == NULL || b == NULL ) {
		return( NULL );
	}
	if ( ID_BLOCK_ALLIDS( a ) ) {
		return( idl_dup( b ) );
	}
	if ( ID_BLOCK_ALLIDS( b ) ) {
		return( idl_dup( a ) );
	}

	n = idl_dup( idl_min( a, b ) );

#ifdef LDBM_DEBUG_IDL
	idl_check(a);
	idl_check(b);
#endif

	for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
		for ( ;
			bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
			bi++ )
		{
			;	/* NULL */
		}

		if ( bi == ID_BLOCK_NIDS(b) ) {
			break;
		}

		if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
		}
	}

	if ( ni == 0 ) {
		idl_free( n );
		return( NULL );
	}
	ID_BLOCK_NIDS(n) = ni;

#ifdef LDBM_DEBUG_IDL
	idl_check(n);
#endif

	return( n );
}


/*
 * idl_union - return a union b
 */
ID_BLOCK *
idl_union(
    Backend	*be,
    ID_BLOCK	*a,
    ID_BLOCK	*b
)
{
	unsigned int	ai, bi, ni;
	ID_BLOCK		*n;

	if ( a == NULL ) {
		return( idl_dup( b ) );
	}
	if ( b == NULL ) {
		return( idl_dup( a ) );
	}
	if ( ID_BLOCK_ALLIDS( a ) || ID_BLOCK_ALLIDS( b ) ) {
		return( idl_allids( be ) );
	}

#ifdef LDBM_DEBUG_IDL
	idl_check(a);
	idl_check(b);
#endif

	if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) {
		n = a;
		a = b;
		b = n;
	}

	n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) );

	for ( ni = 0, ai = 0, bi = 0;
		ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b);
		)
	{
		if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++);

		} else if ( ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi++);

		} else {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
			ai++, bi++;
		}
	}

	for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
		ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
	}
	for ( ; bi < ID_BLOCK_NIDS(b); bi++ ) {
		ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi);
	}
	ID_BLOCK_NIDS(n) = ni;

#ifdef LDBM_DEBUG_IDL
	idl_check(n);
#endif

	return( n );
}


/*
 * idl_notin - return a intersection ~b (or a minus b)
 */
ID_BLOCK *
idl_notin(
    Backend	*be,
    ID_BLOCK 	*a,
    ID_BLOCK 	*b
)
{
	unsigned int	ni, ai, bi;
	ID_BLOCK		*n;

	if ( a == NULL ) {
		return( NULL );
	}
	if ( b == NULL || ID_BLOCK_ALLIDS( b )) {
		return( idl_dup( a ) );
	}

	if ( ID_BLOCK_ALLIDS( a ) ) {
		n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
		ni = 0;

		for ( ai = 1, bi = 0;
			ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n) && bi < ID_BLOCK_NMAX(b);
			ai++ )
		{
			if ( ID_BLOCK_ID(b, bi) == ai ) {
				bi++;
			} else {
				ID_BLOCK_ID(n, ni++) = ai;
			}
		}

		for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n); ai++ ) {
			ID_BLOCK_ID(n, ni++) = ai;
		}

		if ( ni == ID_BLOCK_NMAX(n) ) {
			idl_free( n );
			return( idl_allids( be ) );
		} else {
			ID_BLOCK_NIDS(n) = ni;
			return( n );
		}
	}

	n = idl_dup( a );

	ni = 0;
	for ( ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
		for ( ;
			bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
		    bi++ )
		{
			;	/* NULL */
		}

		if ( bi == ID_BLOCK_NIDS(b) ) {
			break;
		}

		if ( ID_BLOCK_ID(b, bi) != ID_BLOCK_ID(a, ai) ) {
			ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
		}
	}

	for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
		ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
	}
	ID_BLOCK_NIDS(n) = ni;

#ifdef LDBM_DEBUG_IDL
	idl_check(n);
#endif

	return( n );
}

/*	return the first ID in the block
 *	if ALLIDS block
 *		NIDS > 1 return 1
 *		otherwise return NOID 
 *	otherwise return first ID
 *
 *	cursor is set to 1
 */         
ID
idl_firstid( ID_BLOCK *idl, ID *cursor )
{
	*cursor = 1;

	if ( idl == NULL || ID_BLOCK_NIDS(idl) == 0 ) {
		return( NOID );
	}

	if ( ID_BLOCK_ALLIDS( idl ) ) {
		return( ID_BLOCK_NIDS(idl) > 1 ? 1 : NOID );
	}

	return( ID_BLOCK_ID(idl, 0) );
}

/*	return next ID
 *	if ALLIDS block, cursor is id.
 *		increment id
 *		if id < NIDS return id
 *		otherwise NOID.
 *	otherwise cursor is index into block
 *		if index < nids
 *			return id at index then increment
 */ 
ID
idl_nextid( ID_BLOCK *idl, ID *cursor )
{
	if ( ID_BLOCK_ALLIDS( idl ) ) {
		if( ++(*cursor) < ID_BLOCK_NIDS(idl) ) {
			return *cursor;
		} else {
			return NOID;
		}
	}

	if ( *cursor < ID_BLOCK_NIDS(idl) ) {
		return( ID_BLOCK_ID(idl, (*cursor)++) );
	}

	return( NOID );
}