static int pack_vlv_response_control(
	Operation		*op,
	SlapReply		*rs,
	sort_op			*so,
	LDAPControl	**ctrlsp )
{
	LDAPControl			*ctrl;
	BerElementBuffer	berbuf;
	BerElement			*ber		= (BerElement *)&berbuf;
	struct berval		cookie, bv;
	int					rc;

	ber_init2( ber, NULL, LBER_USE_DER );
	ber_set_option( ber, LBER_OPT_BER_MEMCTX, &op->o_tmpmemctx );

	rc = ber_printf( ber, "{iie", so->so_vlv_target, so->so_nentries,
		so->so_vlv_rc );

	if ( rc != -1 && so->so_vcontext ) {
		cookie.bv_val = (char *)&so->so_vcontext;
		cookie.bv_len = sizeof(so->so_vcontext);
		rc = ber_printf( ber, "tO", LDAP_VLVCONTEXT_IDENTIFIER, &cookie );
	}

	if ( rc != -1 ) {
		rc = ber_printf( ber, "}" );
	}

	if ( rc != -1 ) {
		rc = ber_flatten2( ber, &bv, 0 );
	}

	if ( rc != -1 ) {
		ctrl = (LDAPControl *)op->o_tmpalloc( sizeof(LDAPControl)+
			bv.bv_len, op->o_tmpmemctx );
		ctrl->ldctl_oid			= LDAP_CONTROL_VLVRESPONSE;
		ctrl->ldctl_iscritical	= 0;
		ctrl->ldctl_value.bv_val = (char *)(ctrl+1);
		ctrl->ldctl_value.bv_len = bv.bv_len;
		AC_MEMCPY( ctrl->ldctl_value.bv_val, bv.bv_val, bv.bv_len );
		ctrlsp[0] = ctrl;
	} else {
		ctrlsp[0] = NULL;
		rs->sr_err = LDAP_OTHER;
	}

	ber_free_buf( ber );

	return rs->sr_err;
}

static char *cpy_addresses(
	char ***tgtio,
	char *buf,
	char **src,
	int len )
{
   	char **tgt=*tgtio;
	for( ; (*src) ; src++ ) {
		AC_MEMCPY( buf, *src, len );
		*tgt++=buf;
		buf+=len;
	}
	*tgtio=tgt;      
	return buf;
}

/* Append sorted list b to sorted list a. The result is unsorted but
 * a[1] is the min of the result and a[a[0]] is the max.
 */
int bdb_idl_append( ID *a, ID *b )
{
	ID ida, idb, tmp, swap = 0;

	if ( BDB_IDL_IS_ZERO( b ) ) {
		return 0;
	}

	if ( BDB_IDL_IS_ZERO( a ) ) {
		BDB_IDL_CPY( a, b );
		return 0;
	}

	ida = BDB_IDL_LAST( a );
	idb = BDB_IDL_LAST( b );
	if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
		a[0] + b[0] >= BDB_IDL_UM_MAX ) {
		a[2] = IDL_MAX( ida, idb );
		a[1] = IDL_MIN( a[1], b[1] );
		a[0] = NOID;
		return 0;
	}

	if ( b[0] > 1 && ida > idb ) {
		swap = idb;
		a[a[0]] = idb;
		b[b[0]] = ida;
	}

	if ( b[1] < a[1] ) {
		tmp = a[1];
		a[1] = b[1];
	} else {
		tmp = b[1];
	}
	a[0]++;
	a[a[0]] = tmp;

	if ( b[0] > 1 ) {
		int i = b[0] - 1;
		AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
		a[0] += i;
	}
	if ( swap ) {
		b[b[0]] = swap;
	}
	return 0;
}

static char *cpy_aliases(
	char ***tgtio,
	char *buf,
	char **src )
{
	int len;
	char **tgt=*tgtio;
	for( ; (*src) ; src++ ) {
		len = strlen( *src ) + 1;
		AC_MEMCPY( buf, *src, len );
		*tgt++=buf;
		buf+=len;
	}
	*tgtio=tgt;   
	return buf;
}

int
rewrite_var_replace(
		struct rewrite_var *var,
		const char *value,
		int flags
)
{
	ber_len_t	len;

	assert( value != NULL );

	len = strlen( value );

	if ( var->lv_flags & REWRITE_VAR_COPY_VALUE ) {
		if ( flags & REWRITE_VAR_COPY_VALUE ) {
			if ( len <= var->lv_value.bv_len ) {
				AC_MEMCPY(var->lv_value.bv_val, value, len + 1);

			} else {
				free( var->lv_value.bv_val );
				var->lv_value.bv_val = strdup( value );
			}

		} else {
			free( var->lv_value.bv_val );
			var->lv_value.bv_val = (char *)value;
			var->lv_flags &= ~REWRITE_VAR_COPY_VALUE;
		}

	} else {
		if ( flags & REWRITE_VAR_COPY_VALUE ) {
			var->lv_value.bv_val = strdup( value );
			var->lv_flags |= REWRITE_VAR_COPY_VALUE;

		} else {
			var->lv_value.bv_val = (char *)value;
		}
	}

	if ( var->lv_value.bv_val == NULL ) {
		return -1;
	}

	var->lv_value.bv_len = len;

	return 0;
}

static int
dupent_response_done( Operation *op, SlapReply *rs )
{
	BerElementBuffer	berbuf;
	BerElement			*ber = (BerElement *) &berbuf;
	struct berval		ctrlval;
	LDAPControl			*ctrl, *ctrlsp[2];

	ber_init2( ber, NULL, LBER_USE_DER );

	/*

      DuplicateEntryResponseDone ::= SEQUENCE { 
         resultCode,     -- From [RFC2251] 
         errorMessage    [0] LDAPString OPTIONAL, 
         attribute       [1] AttributeDescription OPTIONAL } 

	 */

	ber_printf( ber, "{i}", rs->sr_err );
	if ( ber_flatten2( ber, &ctrlval, 0 ) == -1 ) {
		ber_free_buf( ber );
		if ( op->o_dupent == SLAP_CONTROL_CRITICAL ) {
			return LDAP_CONSTRAINT_VIOLATION;
		}
		return SLAP_CB_CONTINUE;
	}

	ctrl = op->o_tmpcalloc( 1,
		sizeof( LDAPControl ) + ctrlval.bv_len + 1,
		op->o_tmpmemctx );
	ctrl->ldctl_value.bv_val = (char *)&ctrl[ 1 ];
	ctrl->ldctl_oid = LDAP_CONTROL_DUPENT_RESPONSE;
	ctrl->ldctl_iscritical = 0;
	ctrl->ldctl_value.bv_len = ctrlval.bv_len;
	AC_MEMCPY( ctrl->ldctl_value.bv_val, ctrlval.bv_val, ctrlval.bv_len );
	ctrl->ldctl_value.bv_val[ ctrl->ldctl_value.bv_len ] = '\0';

	ber_free_buf( ber );

	ctrlsp[0] = ctrl;
	ctrlsp[1] = NULL;
	slap_add_ctrls( op, rs, ctrlsp );

	return SLAP_CB_CONTINUE;
}

static void
add_lower(ac_uint4 code)
{
    ac_uint4 i, j;

    /*
     * Always map the code to itself.
     */
    cases[1] = code;

    /*
     * If the title case character is empty, then make it the same as the
     * upper case.
     */
    if (cases[2] == 0)
      cases[2] = cases[0];

    if (lower_used == lower_size) {
        if (lower_size == 0)
          lower = (_case_t *) malloc(sizeof(_case_t) << 3);
        else
          lower = (_case_t *) realloc((char *) lower,
                                      sizeof(_case_t) * (lower_size + 8));
        lower_size += 8;
    }

    /*
     * Locate the insertion point.
     */
    for (i = 0; i < lower_used && code > lower[i].key; i++) ;

    if (i < lower_used) {
        /*
         * Shift the array up by one.
         */
        for (j = lower_used; j > i; j--)
          (void) AC_MEMCPY((char *) &lower[j], (char *) &lower[j - 1],
                        sizeof(_case_t));
    }

    lower[i].key = cases[1];    /* Lower */
    lower[i].other1 = cases[0]; /* Upper */
    lower[i].other2 = cases[2]; /* Title */

    lower_used++;
}

int
bdb_dn2id_children(
	Operation *op,
	DB_TXN *txn,
	Entry *e )
{
	DBT		key, data;
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	ID		id;
	int		rc;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
		e->e_nname.bv_val, 0, 0 );
	DBTzero( &key );
	key.size = e->e_nname.bv_len + 2;
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	((char *)key.data)[0] = DN_ONE_PREFIX;
	AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );

	if ( bdb->bi_idl_cache_size ) {
		rc = bdb_idl_cache_get( bdb, db, &key, NULL );
		if ( rc != LDAP_NO_SUCH_OBJECT ) {
			op->o_tmpfree( key.data, op->o_tmpmemctx );
			return rc;
		}
	}
	/* we actually could do a empty get... */
	DBTzero( &data );
	data.data = &id;
	data.ulen = sizeof(id);
	data.flags = DB_DBT_USERMEM;
	data.doff = 0;
	data.dlen = sizeof(id);

	rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
	op->o_tmpfree( key.data, op->o_tmpmemctx );

	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n",
		e->e_nname.bv_val,
		rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
			db_strerror(rc) ), rc );

	return rc;
}

int
ldap_get_entry_controls(
	LDAP *ld,
	LDAPMessage *entry, 
	LDAPControl ***sctrls )
{
	int rc;
	BerElement be;

	assert( ld != NULL );
	assert( LDAP_VALID( ld ) );
	assert( entry != NULL );
	assert( sctrls != NULL );

	if ( entry->lm_msgtype != LDAP_RES_SEARCH_ENTRY ) {
		return LDAP_PARAM_ERROR;
	}

	/* make a local copy of the BerElement */
	AC_MEMCPY(&be, entry->lm_ber, sizeof(be));

	if ( ber_scanf( &be, "{xx" /*}*/ ) == LBER_ERROR ) {
		rc = LDAP_DECODING_ERROR;
		goto cleanup_and_return;
	}

	rc = ldap_pvt_get_controls( &be, sctrls );

cleanup_and_return:
	if( rc != LDAP_SUCCESS ) {
		ld->ld_errno = rc;

		if( ld->ld_matched != NULL ) {
			LDAP_FREE( ld->ld_matched );
			ld->ld_matched = NULL;
		}

		if( ld->ld_error != NULL ) {
			LDAP_FREE( ld->ld_error );
			ld->ld_error = NULL;
		}
	}

	return rc;
}

int
bdb_dn2id(
	Operation *op,
	struct berval	*dn,
	EntryInfo *ei,
	DB_TXN *txn,
	DBC **cursor )
{
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	int		rc;
	DBT		key, data;
	ID		nid;

	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );

	DBTzero( &key );
	key.size = dn->bv_len + 2;
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
	((char *)key.data)[0] = DN_BASE_PREFIX;
	AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );

	/* store the ID */
	DBTzero( &data );
	data.data = &nid;
	data.ulen = sizeof(ID);
	data.flags = DB_DBT_USERMEM;

	rc = db->cursor( db, txn, cursor, bdb->bi_db_opflags );

	/* fetch it */
	if ( !rc )
		rc = (*cursor)->c_get( *cursor, &key, &data, DB_SET );

	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
	} else {
		BDB_DISK2ID( &nid, &ei->bei_id );
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
			ei->bei_id, 0, 0 );
	}
	op->o_tmpfree( key.data, op->o_tmpmemctx );
	return rc;
}

static Datum
ldbm_get_next( LDBM ldbm, kvpair (*fptr)(MDBM *, kvpair) ) 
{
	kvpair	out;
	kvpair	in;
	Datum	ret;
	size_t	sz = MDBM_PAGE_SIZE(ldbm);
#ifdef NO_NULL_KEY
	int	delta = 1;
#else
	int	delta = 0;
#endif

	/* LDBM_RLOCK; */

	in.key.dsize = sz;	/* Assume first key in one pg */
	in.key.dptr = malloc(sz);
	
	in.val.dptr = NULL;	/* Don't need data just key */ 
	in.val.dsize = 0;

	ret.dptr = NULL;
	ret.dsize = NULL;

	out = fptr( ldbm, in );

	if (out.key.dsize > 0) {
		ret.dsize = out.key.dsize - delta;

		if ((ret.dptr = (char *)malloc(ret.dsize)) == NULL) { 
			ret.dsize = 0;
			ret.dptr = NULL;

		} else {
			AC_MEMCPY(ret.dptr, (void *)(out.key.dptr + delta),
				ret.dsize );
	    }
	}

	/* LDBM_RUNLOCK; */
	
	free(in.key.dptr);
	return ret;
}

static char *v2ref( BerVarray ref, const char *text )
{
	size_t len = 0, i = 0;
	char *v2;

	if(ref == NULL) {
		if (text) {
			return ch_strdup(text);
		} else {
			return NULL;
		}
	}
	
	if ( text != NULL ) {
		len = strlen( text );
		if (text[len-1] != '\n') {
		    i = 1;
		}
	}

	v2 = ch_malloc( len+i+sizeof("Referral:") );

	if( text != NULL ) {
		strcpy(v2, text);
		if( i ) {
			v2[len++] = '\n';
		}
	}
	strcpy( v2+len, "Referral:" );
	len += sizeof("Referral:");

	for( i=0; ref[i].bv_val != NULL; i++ ) {
		v2 = ch_realloc( v2, len + ref[i].bv_len + 1 );
		v2[len-1] = '\n';
		AC_MEMCPY(&v2[len], ref[i].bv_val, ref[i].bv_len );
		len += ref[i].bv_len;
		if (ref[i].bv_val[ref[i].bv_len-1] != '/') {
			++len;
		}
	}

	v2[len-1] = '\0';
	return v2;
}

static int
parse_paged_cookie( Operation *op, SlapReply *rs )
{
	int		rc = LDAP_SUCCESS;
	PagedResultsState *ps = op->o_pagedresults_state;

	/* this function must be invoked only if the pagedResults
	 * control has been detected, parsed and partially checked
	 * by the frontend */
	assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );

	/* cookie decoding/checks deferred to backend... */
	if ( ps->ps_cookieval.bv_len ) {
		PagedResultsCookie reqcookie;
		if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) {
			/* bad cookie */
			rs->sr_text = "paged results cookie is invalid";
			rc = LDAP_PROTOCOL_ERROR;
			goto done;
		}

		AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));

		if ( reqcookie > ps->ps_cookie ) {
			/* bad cookie */
			rs->sr_text = "paged results cookie is invalid";
			rc = LDAP_PROTOCOL_ERROR;
			goto done;

		} else if ( reqcookie < ps->ps_cookie ) {
			rs->sr_text = "paged results cookie is invalid or old";
			rc = LDAP_UNWILLING_TO_PERFORM;
			goto done;
		}

	} else {
		/* we're going to use ps_cookie */
		op->o_conn->c_pagedresults_state.ps_cookie = 0;
	}

done:;

	return rc;
}

static int
ainfo_insert( struct mdb_info *mdb, AttrInfo *a )
{
	int x;
	int i = mdb_attr_slot( mdb, a->ai_desc, &x );

	/* Is it a dup? */
	if ( i >= 0 )
		return -1;

	mdb->mi_attrs = ch_realloc( mdb->mi_attrs, ( mdb->mi_nattrs+1 ) * 
		sizeof( AttrInfo * ));
	if ( x < mdb->mi_nattrs )
		AC_MEMCPY( &mdb->mi_attrs[x+1], &mdb->mi_attrs[x],
			( mdb->mi_nattrs - x ) * sizeof( AttrInfo *));
	mdb->mi_attrs[x] = a;
	mdb->mi_nattrs++;
	return 0;
}

		/* insert id */
		AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
		ids[x] = id;
	}

#if IDL_DEBUG > 1
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	return 0;
}

#if 0	/* unused */
static int idl_delete( ID *ids, ID id )
{
	unsigned x = bdb_idl_search( ids, id );

#if IDL_DEBUG > 1
#ifdef NEW_LOGGING
	LDAP_LOG( INDEX, DETAIL1, "delete: %04lx at %d\n", (long) id, x, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
	idl_dump( ids );
#endif
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	assert( x > 0 );

	if( x <= 0 ) {
		/* internal error */
		return -2;
	}

	if( x > ids[0] || ids[x] != id ) {
		/* not found */
		return -1;

	} else if ( --ids[0] == 0 ) {
		if( x != 1 ) {
			return -3;
		}

	} else {
		AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
	}

#if IDL_DEBUG > 1
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	return 0;
}

int
ldbm_store( LDBM ldbm, Datum key, Datum data, int flags )
{
	int	rc;
	Datum	int_key;	/* Internal key */

#ifdef MDBM_DEBUG
	fprintf( stdout,
		 "==>(mdbm)ldbm_store(db=%p, key(dptr=%p,sz=%d), data(dptr=%p,sz=%d), flags=%x)\n",
		 ldbm, key.dptr, key.dsize, data.dptr, data.dsize, flags );
	fflush( stdout );
#endif

	/* LDBM_WLOCK; */

#ifdef NO_NULL_KEY
	int_key.dsize = key.dsize + 1;
	int_key.dptr = malloc( int_key.dsize );
	*(int_key.dptr) = 'l';	/* Must not be NULL !*/
	AC_MEMCPY( (void *)(int_key.dptr + 1), key.dptr, key.dsize );
#else
	int_key = key;
#endif

	rc = mdbm_store( ldbm, int_key, data, flags );
	if ( flags & LDBM_SYNC ) {
		mdbm_sync( ldbm );
	}

	/* LDBM_WUNLOCK; */

#ifdef MDBM_DEBUG
	fprintf( stdout, "<==(mdbm)ldbm_store(rc=%d)\n", rc );
	fflush( stdout );
#endif

#ifdef NO_NULL_KEY
	free(int_key.dptr);
#endif

	return( rc );
}

static int 
OpenLDAPaciNormalizeRights(
	struct berval	*actions,
	struct berval	*nactions,
	void		*ctx )

{
	struct berval	bv = BER_BVNULL;
	int		i;

	BER_BVZERO( nactions );
	for ( i = 0; acl_get_part( actions, i, '$', &bv ) >= 0; i++ ) {
		int		rc;
		struct berval	nbv;

		rc = OpenLDAPaciNormalizeRight( &bv, &nbv, ctx );
		if ( rc != LDAP_SUCCESS ) {
			ber_memfree_x( nactions->bv_val, ctx );
			BER_BVZERO( nactions );
			return LDAP_INVALID_SYNTAX;
		}

		if ( i == 0 ) {
			*nactions = nbv;

		} else {
			nactions->bv_val = ber_memrealloc_x( nactions->bv_val,
				nactions->bv_len + STRLENOF( "$" )
				+ nbv.bv_len + 1,
				ctx );
			nactions->bv_val[ nactions->bv_len ] = '$';
			AC_MEMCPY( &nactions->bv_val[ nactions->bv_len + 1 ],
				nbv.bv_val, nbv.bv_len + 1 );
			ber_memfree_x( nbv.bv_val, ctx );
			nactions->bv_len += STRLENOF( "$" ) + nbv.bv_len;
		}
		BER_BVZERO( &nbv );
	}

	return LDAP_SUCCESS;
}

/* Drop a processed packet from the input buffer */
static void
sb_sasl_generic_drop_packet (
	struct sb_sasl_generic_data *p,
	int debuglevel )
{
	ber_slen_t			len;

	len = p->sec_buf_in.buf_ptr - p->sec_buf_in.buf_end;
	if ( len > 0 )
		AC_MEMCPY( p->sec_buf_in.buf_base, p->sec_buf_in.buf_base +
			p->sec_buf_in.buf_end, len );

	if ( len >= 4 ) {
		p->sec_buf_in.buf_end = sb_sasl_generic_pkt_length(p,
			(unsigned char *) p->sec_buf_in.buf_base, debuglevel);
	}
	else {
		p->sec_buf_in.buf_end = 0;
	}
	p->sec_buf_in.buf_ptr = len;
}

Datum
ldbm_datum_dup( LDBM ldbm, Datum data )
{
	Datum	dup;

	ldbm_datum_init( dup );

	if ( data.dsize == 0 ) {
		dup.dsize = 0;
		dup.dptr = NULL;

		return( dup );
	}
	dup.dsize = data.dsize;

	if ( (dup.dptr = (char *) malloc( data.dsize )) != NULL ) {
		AC_MEMCPY( dup.dptr, data.dptr, data.dsize );
	}

	return( dup );
}

/*
 * Read from the ber buffer.  The caller must maintain ber->ber_tag.
 * Do not use to read whole tags.  See ber_get_tag() and ber_skip_data().
 */
ber_slen_t
ber_read(
	BerElement *ber,
	char *buf,
	ber_len_t len )
{
	ber_len_t	actuallen, nleft;

	assert( ber != NULL );
	assert( buf != NULL );
	assert( LBER_VALID( ber ) );

	nleft = ber_pvt_ber_remaining( ber );
	actuallen = nleft < len ? nleft : len;

	AC_MEMCPY( buf, ber->ber_ptr, actuallen );

	ber->ber_ptr += actuallen;

	return( (ber_slen_t) actuallen );
}