xref: /titanic_41/usr/src/lib/libldap5/sources/ldap/common/memcache.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)

/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */
#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*
 * The contents of this file are subject to the Netscape Public
 * License Version 1.1 (the "License"); you may not use this file
 * except in compliance with the License. You may obtain a copy of
 * the License at http://www.mozilla.org/NPL/
 *
 * Software distributed under the License is distributed on an "AS
 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * rights and limitations under the License.
 *
 * The Original Code is Mozilla Communicator client code, released
 * March 31, 1998.
 *
 * The Initial Developer of the Original Code is Netscape
 * Communications Corporation. Portions created by Netscape are
 * Copyright (C) 1998-1999 Netscape Communications Corporation. All
 * Rights Reserved.
 *
 * Contributor(s):
 */
/*
 *
 *  memcache.c - routines that implement an in-memory cache.
 *
 *  To Do:  1) ber_dup_ext().
 *	    2) referrals and reference?
 */

#include <assert.h>
#include "ldap-int.h"

/*
 * Extra size allocated to BerElement.
 * XXXmcs: must match EXBUFSIZ in liblber/io.c?
 */
#define EXTRA_SIZE		    1024

/* Mode constants for function memcache_access() */
#define MEMCACHE_ACCESS_ADD	    0
#define MEMCACHE_ACCESS_APPEND	    1
#define MEMCACHE_ACCESS_APPEND_LAST 2
#define MEMCACHE_ACCESS_FIND	    3
#define MEMCACHE_ACCESS_DELETE	    4
#define MEMCACHE_ACCESS_DELETE_ALL  5
#define MEMCACHE_ACCESS_UPDATE	    6
#define MEMCACHE_ACCESS_FLUSH	    7
#define MEMCACHE_ACCESS_FLUSH_ALL   8
#define MEMCACHE_ACCESS_FLUSH_LRU   9

/* Mode constants for function memcache_adj_size */
#define MEMCACHE_SIZE_DEDUCT	    0
#define MEMCACHE_SIZE_ADD	    1

#define MEMCACHE_SIZE_ENTRIES       1
#define MEMCACHE_SIZE_NON_ENTRIES   2

/* Size used for calculation if given size of cache is 0 */
#define MEMCACHE_DEF_SIZE	    131072		/* 128K bytes */

/* Index into different list structure */
#define LIST_TTL		    0
#define LIST_LRU		    1
#define LIST_TMP		    2
#define LIST_TOTAL		    3


static char *emptyStr = "";

/* Macros to make code more readable */
#define NSLDAPI_VALID_MEMCACHE_POINTER( cp )	( (cp) != NULL )
#define NSLDAPI_STR_NONNULL( s )		( (s) ? (s) : emptyStr )
#define NSLDAPI_SAFE_STRLEN( s )		( (s) ? strlen((s)) + 1 : 1 )

/* Macros dealing with mutex */
#define LDAP_MEMCACHE_MUTEX_LOCK( c ) \
	if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_lock ) { \
	    ((c)->ldmemc_lock_fns).ltf_mutex_lock( (c)->ldmemc_lock ); \
	}

#define LDAP_MEMCACHE_MUTEX_UNLOCK( c ) \
	if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_unlock ) { \
	    ((c)->ldmemc_lock_fns).ltf_mutex_unlock( (c)->ldmemc_lock ); \
	}

#define LDAP_MEMCACHE_MUTEX_ALLOC( c ) \
	((c) && ((c)->ldmemc_lock_fns).ltf_mutex_alloc ? \
	    ((c)->ldmemc_lock_fns).ltf_mutex_alloc() : NULL)

#define LDAP_MEMCACHE_MUTEX_FREE( c ) \
	if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_free ) { \
	    ((c)->ldmemc_lock_fns).ltf_mutex_free( (c)->ldmemc_lock ); \
	}

/* Macros used for triming unnecessary spaces in a basedn */
#define NSLDAPI_IS_SPACE( c ) \
	(((c) == ' ') || ((c) == '\t') || ((c) == '\n'))

#define NSLDAPI_IS_SEPARATER( c ) \
	((c) == ',')

/* Hash table callback function pointer definition */
typedef int (*HashFuncPtr)(int table_size, void *key);
typedef int (*PutDataPtr)(void **ppTableData, void *key, void *pData);
typedef int (*GetDataPtr)(void *pTableData, void *key, void **ppData);
typedef int (*RemoveDataPtr)(void **ppTableData, void *key, void **ppData);
typedef int (*MiscFuncPtr)(void **ppTableData, void *key, void *pData);
typedef void (*ClrTableNodePtr)(void **ppTableData, void *pData);

/* Structure of a node in a hash table */
typedef struct HashTableNode_struct {
    void *pData;
} HashTableNode;

/* Structure of a hash table */
typedef struct HashTable_struct {
    HashTableNode   *table;
    int		    size;
    HashFuncPtr	    hashfunc;
    PutDataPtr	    putdata;
    GetDataPtr	    getdata;
    MiscFuncPtr     miscfunc;
    RemoveDataPtr   removedata;
    ClrTableNodePtr clrtablenode;
} HashTable;

/* Structure uniquely identifies a search request */
typedef struct ldapmemcacheReqId_struct {
    LDAP				*ldmemcrid_ld;
    int					ldmemcrid_msgid;
} ldapmemcacheReqId;

/* Structure representing a ldap handle associated to memcache */
typedef struct ldapmemcacheld_struct {
    LDAP		    		*ldmemcl_ld;
    struct ldapmemcacheld_struct	*ldmemcl_next;
} ldapmemcacheld;

/* Structure representing header of a search result */
typedef struct ldapmemcacheRes_struct {
    char				*ldmemcr_basedn;
    unsigned long			ldmemcr_crc_key;
    unsigned long			ldmemcr_resSize;
    unsigned long			ldmemcr_timestamp;
    LDAPMessage				*ldmemcr_resHead;
    LDAPMessage				*ldmemcr_resTail;
    ldapmemcacheReqId			ldmemcr_req_id;
    struct ldapmemcacheRes_struct	*ldmemcr_next[LIST_TOTAL];
    struct ldapmemcacheRes_struct	*ldmemcr_prev[LIST_TOTAL];
    struct ldapmemcacheRes_struct	*ldmemcr_htable_next;
} ldapmemcacheRes;

/* Structure for memcache statistics */
typedef struct ldapmemcacheStats_struct {
    unsigned long			ldmemcstat_tries;
    unsigned long			ldmemcstat_hits;
} ldapmemcacheStats;

/* Structure of a memcache object */
struct ldapmemcache {
    unsigned long			ldmemc_ttl;
    unsigned long			ldmemc_size;
    unsigned long			ldmemc_size_used;
    unsigned long			ldmemc_size_entries;
    char				**ldmemc_basedns;
    void				*ldmemc_lock;
    ldapmemcacheld			*ldmemc_lds;
    HashTable				*ldmemc_resTmp;
    HashTable				*ldmemc_resLookup;
    ldapmemcacheRes			*ldmemc_resHead[LIST_TOTAL];
    ldapmemcacheRes			*ldmemc_resTail[LIST_TOTAL];
    struct ldap_thread_fns		ldmemc_lock_fns;
    ldapmemcacheStats			ldmemc_stats;
};

/* Function prototypes */
static int memcache_exist(LDAP *ld);
static int memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg);
static int memcache_compare_dn(const char *main_dn, const char *dn, int scope);
static int memcache_dup_message(LDAPMessage *res, int msgid, int fromcache,
				LDAPMessage **ppResCopy, unsigned long *pSize);
static BerElement* memcache_ber_dup(BerElement* pBer, unsigned long *pSize);

static void memcache_trim_basedn_spaces(char *basedn);
static int memcache_validate_basedn(LDAPMemCache *cache, const char *basedn);
static int memcache_get_ctrls_len(LDAPControl **ctrls);
static void memcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
				  LDAPControl **clientCtrls);
static int memcache_adj_size(LDAPMemCache *cache, unsigned long size,
                             int usageFlags, int bAdd);
static int memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes);
static int memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes,
			    unsigned long curTime);
static int memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes,
				int index);
static int memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg,
				    unsigned long size);
static int memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes,
				   int index);
static int memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes);
static int memcache_add(LDAP *ld, unsigned long key, int msgid,
			const char *basedn);
static int memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes);
static int memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes);
static int memcache_remove(LDAP *ld, int msgid);
#if 0	/* function not used */
static int memcache_remove_all(LDAP *ld);
#endif /* 0 */
static int memcache_access(LDAPMemCache *cache, int mode,
			   void *pData1, void *pData2, void *pData3);
#ifdef LDAP_DEBUG
static void memcache_print_list( LDAPMemCache *cache, int index );
static void memcache_report_statistics( LDAPMemCache *cache );
#endif /* LDAP_DEBUG */

static int htable_calculate_size(int sizelimit);
static int htable_sizeinbytes(HashTable *pTable);
static int htable_put(HashTable *pTable, void *key, void *pData);
static int htable_get(HashTable *pTable, void *key, void **ppData);
static int htable_misc(HashTable *pTable, void *key, void *pData);
static int htable_remove(HashTable *pTable, void *key, void **ppData);
static int htable_removeall(HashTable *pTable, void *pData);
static int htable_create(int size_limit, HashFuncPtr hashf,
                         PutDataPtr putDataf, GetDataPtr getDataf,
			 RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
			 MiscFuncPtr miscOpf, HashTable **ppTable);
static int htable_free(HashTable *pTable);

static int msgid_hashf(int table_size, void *key);
static int msgid_putdata(void **ppTableData, void *key, void *pData);
static int msgid_getdata(void *pTableData, void *key, void **ppData);
static int msgid_removedata(void **ppTableData, void *key, void **ppData);
static int msgid_clear_ld_items(void **ppTableData, void *key, void *pData);
static void msgid_clearnode(void **ppTableData, void *pData);

static int attrkey_hashf(int table_size, void *key);
static int attrkey_putdata(void **ppTableData, void *key, void *pData);
static int attrkey_getdata(void *pTableData, void *key, void **ppData);
static int attrkey_removedata(void **ppTableData, void *key, void **ppData);
static void attrkey_clearnode(void **ppTableData, void *pData);

static unsigned long crc32_convert(char *buf, int len);

/* Create a memcache object. */
int
LDAP_CALL
ldap_memcache_init( unsigned long ttl, unsigned long size,
                    char **baseDNs, struct ldap_thread_fns *thread_fns,
		    LDAPMemCache **cachep )
{
    unsigned long total_size = 0;

    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init\n", 0, 0, 0 );

    if ( cachep == NULL ) {
	return( LDAP_PARAM_ERROR );
    }

    if ((*cachep = (LDAPMemCache*)NSLDAPI_CALLOC(1,
	    sizeof(LDAPMemCache))) == NULL) {
	return ( LDAP_NO_MEMORY );
    }

    total_size += sizeof(LDAPMemCache);

    (*cachep)->ldmemc_ttl = ttl;
    (*cachep)->ldmemc_size = size;
    (*cachep)->ldmemc_lds = NULL;

    /* Non-zero default size needed for calculating size of hash tables */
    size = (size ? size : MEMCACHE_DEF_SIZE);

    if (thread_fns) {
	memcpy(&((*cachep)->ldmemc_lock_fns), thread_fns,
           sizeof(struct ldap_thread_fns));
    } else {
	memset(&((*cachep)->ldmemc_lock_fns), 0,
	   sizeof(struct ldap_thread_fns));
    }

    (*cachep)->ldmemc_lock = LDAP_MEMCACHE_MUTEX_ALLOC( *cachep );

    /* Cache basedns */
    if (baseDNs != NULL) {

	int i;

	for (i = 0; baseDNs[i]; i++) {
		;
	}

	(*cachep)->ldmemc_basedns = (char**)NSLDAPI_CALLOC(i + 1,
		sizeof(char*));

	if ((*cachep)->ldmemc_basedns == NULL) {
    	    ldap_memcache_destroy(*cachep);
	    *cachep = NULL;
	    return ( LDAP_NO_MEMORY );
	}

	total_size += (i + 1) * sizeof(char*);

	for (i = 0; baseDNs[i]; i++) {
	    (*cachep)->ldmemc_basedns[i] = nsldapi_strdup(baseDNs[i]);
	    if ((*cachep)->ldmemc_basedns[i] == NULL)
			return ( LDAP_NO_MEMORY );
	    total_size += strlen(baseDNs[i]) + 1;
	}

	(*cachep)->ldmemc_basedns[i] = NULL;
    }

    /* Create hash table for temporary cache */
    if (htable_create(size, msgid_hashf, msgid_putdata, msgid_getdata,
                      msgid_removedata, msgid_clearnode, msgid_clear_ld_items,
		      &((*cachep)->ldmemc_resTmp)) != LDAP_SUCCESS) {
	ldap_memcache_destroy(*cachep);
	*cachep = NULL;
	return( LDAP_NO_MEMORY );
    }

    total_size += htable_sizeinbytes((*cachep)->ldmemc_resTmp);

    /* Create hash table for primary cache */
    if (htable_create(size, attrkey_hashf, attrkey_putdata,
	              attrkey_getdata, attrkey_removedata, attrkey_clearnode,
		      NULL, &((*cachep)->ldmemc_resLookup)) != LDAP_SUCCESS) {
	ldap_memcache_destroy(*cachep);
	*cachep = NULL;
	return( LDAP_NO_MEMORY );
    }

    total_size += htable_sizeinbytes((*cachep)->ldmemc_resLookup);

    /* See if there is enough room so far */
    if (memcache_adj_size(*cachep, total_size, MEMCACHE_SIZE_NON_ENTRIES,
	                  MEMCACHE_SIZE_ADD) != LDAP_SUCCESS) {
	ldap_memcache_destroy(*cachep);
	*cachep = NULL;
	return( LDAP_SIZELIMIT_EXCEEDED );
    }

    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_init new cache 0x%x\n",
	    *cachep, 0, 0 );

    return( LDAP_SUCCESS );
}

/* Associates a ldap handle to a memcache object. */
int
LDAP_CALL
ldap_memcache_set( LDAP *ld, LDAPMemCache *cache )
{
    int nRes = LDAP_SUCCESS;

    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_set\n", 0, 0, 0 );

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) )
	return( LDAP_PARAM_ERROR );

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );

    if (ld->ld_memcache != cache) {

        LDAPMemCache *c = ld->ld_memcache;
	ldapmemcacheld *pCur = NULL;
	ldapmemcacheld *pPrev = NULL;

	/* First dissociate handle from old cache */

	LDAP_MEMCACHE_MUTEX_LOCK( c );

	pCur = (c ? c->ldmemc_lds : NULL);
	for (; pCur; pCur = pCur->ldmemcl_next) {
	    if (pCur->ldmemcl_ld == ld)
		break;
	    pPrev = pCur;
	}

	if (pCur) {

	    ldapmemcacheReqId reqid;

	    reqid.ldmemcrid_ld = ld;
	    reqid.ldmemcrid_msgid = -1;
	    htable_misc(c->ldmemc_resTmp, (void*)&reqid, (void*)c);

	    if (pPrev)
		pPrev->ldmemcl_next = pCur->ldmemcl_next;
	    else
		c->ldmemc_lds = pCur->ldmemcl_next;
	    NSLDAPI_FREE(pCur);
	    pCur = NULL;

	    memcache_adj_size(c, sizeof(ldapmemcacheld),
	                MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
	}

	LDAP_MEMCACHE_MUTEX_UNLOCK( c );

	ld->ld_memcache = NULL;

	/* Exit if no new cache is specified */
	if (cache == NULL) {
	    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
	    return( LDAP_SUCCESS );
	}

	/* Then associate handle with new cache */

        LDAP_MEMCACHE_MUTEX_LOCK( cache );

	if ((nRes = memcache_adj_size(cache, sizeof(ldapmemcacheld),
	       MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_ADD)) != LDAP_SUCCESS) {
	    LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
	    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
	    return nRes;
	}

	pCur = (ldapmemcacheld*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheld));
	if (pCur == NULL) {
	    memcache_adj_size(cache, sizeof(ldapmemcacheld),
		              MEMCACHE_SIZE_NON_ENTRIES, MEMCACHE_SIZE_DEDUCT);
	    nRes = LDAP_NO_MEMORY;
	} else {
	    pCur->ldmemcl_ld = ld;
	    pCur->ldmemcl_next = cache->ldmemc_lds;
	    cache->ldmemc_lds = pCur;
	    ld->ld_memcache = cache;
	}

	LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
    }

    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return nRes;
}

/* Retrieves memcache with which the ldap handle has been associated. */
int
LDAP_CALL
ldap_memcache_get( LDAP *ld, LDAPMemCache **cachep )
{
    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_get ld: 0x%x\n", ld, 0, 0 );

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cachep == NULL ) {
	return( LDAP_PARAM_ERROR );
    }

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
    *cachep = ld->ld_memcache;
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return( LDAP_SUCCESS );
}

/*
 * Function that stays inside libldap and proactively expires items from
 * the given cache.  This should be called from a newly created thread since
 * it will not return until after ldap_memcache_destroy() is called.
 */
void
LDAP_CALL
ldap_memcache_update( LDAPMemCache *cache )
{
    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_update: cache 0x%x\n",
	    cache, 0, 0 );

    if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
	return;
    }

    LDAP_MEMCACHE_MUTEX_LOCK( cache );
    memcache_access(cache, MEMCACHE_ACCESS_UPDATE, NULL, NULL, NULL);
    LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
}

/* Removes specified entries from given memcache. */
void
LDAP_CALL
ldap_memcache_flush( LDAPMemCache *cache, char *dn, int scope )
{
    LDAPDebug( LDAP_DEBUG_TRACE,
	    "ldap_memcache_flush( cache: 0x%x, dn: %s, scope: %d)\n",
	    cache, ( dn == NULL ) ? "(null)" : dn, scope );

    if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
	return;
    }

    LDAP_MEMCACHE_MUTEX_LOCK( cache );

    if (!dn) {
	memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
    } else {
	memcache_access(cache, MEMCACHE_ACCESS_FLUSH,
	                (void*)dn, (void*)(uintptr_t)scope, NULL);
    }

    LDAP_MEMCACHE_MUTEX_UNLOCK( cache );
}

/* Destroys the given memcache. */
void
LDAP_CALL
ldap_memcache_destroy( LDAPMemCache *cache )
{
    int i = 0;
    unsigned long size = sizeof(LDAPMemCache);
    ldapmemcacheld *pNode = NULL, *pNextNode = NULL;

    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_destroy( 0x%x )\n",
	    cache, 0, 0 );

    if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
	return;
    }

    /* Dissociate all ldap handes from this cache. */
    LDAP_MEMCACHE_MUTEX_LOCK( cache );

    for (pNode = cache->ldmemc_lds; pNode; pNode = pNextNode, i++) {
        LDAP_MUTEX_LOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
	cache->ldmemc_lds = pNode->ldmemcl_next;
	pNode->ldmemcl_ld->ld_memcache = NULL;
        LDAP_MUTEX_UNLOCK( pNode->ldmemcl_ld, LDAP_MEMCACHE_LOCK );
	pNextNode = pNode->ldmemcl_next;
	NSLDAPI_FREE(pNode);
    }

    size += i * sizeof(ldapmemcacheld);

    LDAP_MEMCACHE_MUTEX_UNLOCK( cache );

    /* Free array of basedns */
    if (cache->ldmemc_basedns) {
	for (i = 0; cache->ldmemc_basedns[i]; i++) {
	    size += strlen(cache->ldmemc_basedns[i]) + 1;
	    NSLDAPI_FREE(cache->ldmemc_basedns[i]);
	}
	size += (i + 1) * sizeof(char*);
	NSLDAPI_FREE(cache->ldmemc_basedns);
    }

    /* Free hash table used for temporary cache */
    if (cache->ldmemc_resTmp) {
	size += htable_sizeinbytes(cache->ldmemc_resTmp);
	memcache_access(cache, MEMCACHE_ACCESS_DELETE_ALL, NULL, NULL, NULL);
	htable_free(cache->ldmemc_resTmp);
    }

    /* Free hash table used for primary cache */
    if (cache->ldmemc_resLookup) {
	size += htable_sizeinbytes(cache->ldmemc_resLookup);
	memcache_access(cache, MEMCACHE_ACCESS_FLUSH_ALL, NULL, NULL, NULL);
	htable_free(cache->ldmemc_resLookup);
    }

    memcache_adj_size(cache, size, MEMCACHE_SIZE_NON_ENTRIES,
	              MEMCACHE_SIZE_DEDUCT);

    LDAP_MEMCACHE_MUTEX_FREE( cache );

    NSLDAPI_FREE(cache);
}

/************************* Internal API Functions ****************************/

/* Creates an integer key by applying the Cyclic Reduntency Check algorithm on
   a long string formed by concatenating all the search parameters plus the
   current bind DN.  The key is used in the cache for looking up cached
   entries.  It is assumed that the CRC algorithm will generate
   different integers from different byte strings. */
int
ldap_memcache_createkey(LDAP *ld, const char *base, int scope,
			const char *filter, char **attrs,
                        int attrsonly, LDAPControl **serverctrls,
                        LDAPControl **clientctrls, unsigned long *keyp)
{
    int nRes, i, j, i_smallest;
    int len;
    int defport;
    char buf[50];
    char *tmp, *defhost, *binddn, *keystr, *tmpbase;

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (keyp == NULL) )
	return( LDAP_PARAM_ERROR );

    *keyp = 0;

    if (!memcache_exist(ld))
	return( LDAP_LOCAL_ERROR );

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
    LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
    nRes = memcache_validate_basedn(ld->ld_memcache, base);
    LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    if (nRes != LDAP_SUCCESS)
	return nRes;

    defhost = NSLDAPI_STR_NONNULL(ld->ld_defhost);
    defport = ld->ld_defport;
    tmpbase = nsldapi_strdup(NSLDAPI_STR_NONNULL(base));
	if (tmpbase == NULL)
		return( LDAP_LOCAL_ERROR );
    memcache_trim_basedn_spaces(tmpbase);

    if ((binddn = nsldapi_get_binddn(ld)) == NULL)
	binddn = "";

    sprintf(buf, "%i\n%i\n%i\n", defport, scope, (attrsonly ? 1 : 0));
    len = NSLDAPI_SAFE_STRLEN(buf) + NSLDAPI_SAFE_STRLEN(tmpbase) +
	  NSLDAPI_SAFE_STRLEN(filter) + NSLDAPI_SAFE_STRLEN(defhost) +
	  NSLDAPI_SAFE_STRLEN(binddn);

    if (attrs) {
	for (i = 0; attrs[i]; i++) {

	    for (i_smallest = j = i; attrs[j]; j++) {
		if (strcasecmp(attrs[i_smallest], attrs[j]) > 0)
		    i_smallest = j;
	    }

	    if (i != i_smallest) {
		tmp = attrs[i];
		attrs[i] = attrs[i_smallest];
		attrs[i_smallest] = tmp;
	    }

	    len += NSLDAPI_SAFE_STRLEN(attrs[i]);
	}
    } else {
	len += 1;
    }

    len += memcache_get_ctrls_len(serverctrls) +
	   memcache_get_ctrls_len(clientctrls) + 1;

    if ((keystr = (char*)NSLDAPI_CALLOC(len, sizeof(char))) == NULL) {
	if (defhost != emptyStr)
		NSLDAPI_FREE(defhost);
	NSLDAPI_FREE(tmpbase);
	return( LDAP_NO_MEMORY );
    }

    sprintf(keystr, "%s\n%s\n%s\n%s\n%s\n", binddn, tmpbase,
	    NSLDAPI_STR_NONNULL(defhost), NSLDAPI_STR_NONNULL(filter),
	    NSLDAPI_STR_NONNULL(buf));

    if (attrs) {
	for (i = 0; attrs[i]; i++) {
	    strcat(keystr, NSLDAPI_STR_NONNULL(attrs[i]));
	    strcat(keystr, "\n");
	}
    } else {
	strcat(keystr, "\n");
    }

    for (tmp = keystr; *tmp;
         *tmp += (*tmp >= 'a' && *tmp <= 'z' ? 'A'-'a' : 0), tmp++) {
		;
	}

    memcache_append_ctrls(keystr, serverctrls, clientctrls);

    /* CRC algorithm */
    *keyp = crc32_convert(keystr, len);

    NSLDAPI_FREE(keystr);
    NSLDAPI_FREE(tmpbase);

    return LDAP_SUCCESS;
}

/* Searches the cache for the right cached entries, and if found, attaches
   them to the given ldap handle.  This function relies on locking by the
   caller. */
int
ldap_memcache_result(LDAP *ld, int msgid, unsigned long key)
{
    int nRes;
    LDAPMessage *pMsg = NULL;

    LDAPDebug( LDAP_DEBUG_TRACE,
	    "ldap_memcache_result( ld: 0x%x, msgid: %d, key: 0x%8.8lx)\n",
	    ld, msgid, key );

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
	return( LDAP_PARAM_ERROR );
    }

    if (!memcache_exist(ld)) {
	return( LDAP_LOCAL_ERROR );
    }

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );
    LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );

    /* Search the cache and append the results to ld if found */
    ++ld->ld_memcache->ldmemc_stats.ldmemcstat_tries;
    if ((nRes = memcache_search(ld, key, &pMsg)) == LDAP_SUCCESS) {
	nRes = memcache_add_to_ld(ld, msgid, pMsg);
	++ld->ld_memcache->ldmemc_stats.ldmemcstat_hits;
	LDAPDebug( LDAP_DEBUG_TRACE,
		"ldap_memcache_result: key 0x%8.8lx found in cache\n",
		key, 0, 0 );
    } else {
	LDAPDebug( LDAP_DEBUG_TRACE,
		"ldap_memcache_result: key 0x%8.8lx not found in cache\n",
		key, 0, 0 );
    }

#ifdef LDAP_DEBUG
    memcache_print_list( ld->ld_memcache, LIST_LRU );
    memcache_report_statistics( ld->ld_memcache );
#endif /* LDAP_DEBUG */

    LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return nRes;
}

/* Creates a new header in the cache so that entries arriving from the
   directory server can later be cached under the header. */
int
ldap_memcache_new(LDAP *ld, int msgid, unsigned long key, const char *basedn)
{
    int nRes;

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) {
	return( LDAP_PARAM_ERROR );
    }

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );

    if (!memcache_exist(ld)) {
        LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
	return( LDAP_LOCAL_ERROR );
    }

    LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
    nRes = memcache_add(ld, key, msgid, basedn);
    LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return nRes;
}

/* Appends a chain of entries to an existing cache header.  Parameter "bLast"
   indicates whether there will be more entries arriving for the search in
   question. */
int
ldap_memcache_append(LDAP *ld, int msgid, int bLast, LDAPMessage *result)
{
    int nRes = LDAP_SUCCESS;

    LDAPDebug( LDAP_DEBUG_TRACE, "ldap_memcache_append( ld: 0x%x, ", ld, 0, 0 );
    LDAPDebug( LDAP_DEBUG_TRACE, "msgid %d, bLast: %d, result: 0x%x)\n",
	    msgid, bLast, result );

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || !result ) {
	return( LDAP_PARAM_ERROR );
    }

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );

    if (!memcache_exist(ld)) {
        LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
	return( LDAP_LOCAL_ERROR );
    }

    LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );

    if (!bLast)
	nRes = memcache_append(ld, msgid, result);
    else
	nRes = memcache_append_last(ld, msgid, result);

    LDAPDebug( LDAP_DEBUG_TRACE,
	    "ldap_memcache_append: %s result for msgid %d\n",
	    ( nRes == LDAP_SUCCESS ) ? "added" : "failed to add", msgid , 0 );

    LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return nRes;
}

/* Removes partially cached results for a search as a result of calling
   ldap_abandon() by the client. */
int
ldap_memcache_abandon(LDAP *ld, int msgid)
{
    int nRes;

    if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || (msgid < 0) ) {
	return( LDAP_PARAM_ERROR );
    }

    LDAP_MUTEX_LOCK( ld, LDAP_MEMCACHE_LOCK );

    if (!memcache_exist(ld)) {
        LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );
	return( LDAP_LOCAL_ERROR );
    }

    LDAP_MEMCACHE_MUTEX_LOCK( ld->ld_memcache );
    nRes = memcache_remove(ld, msgid);
    LDAP_MEMCACHE_MUTEX_UNLOCK( ld->ld_memcache );
    LDAP_MUTEX_UNLOCK( ld, LDAP_MEMCACHE_LOCK );

    return nRes;
}

/*************************** helper functions *******************************/

/* Removes extraneous spaces in a basedn so that basedns differ by only those
   spaces will be treated as equal.  Extraneous spaces are those that
   precedes the basedn and those that follow a comma. */
/*
 * XXXmcs: this is a bit too agressive... we need to deal with the fact that
 * commas and spaces may be quoted, in which case it is wrong to remove them.
 */
static void
memcache_trim_basedn_spaces(char *basedn)
{
    char *pRead, *pWrite;

    if (!basedn)
	return;

    for (pWrite = pRead = basedn; *pRead; ) {
	for (; *pRead && NSLDAPI_IS_SPACE(*pRead); pRead++) {
		;
	}
	for (; *pRead && !NSLDAPI_IS_SEPARATER(*pRead);
	    *(pWrite++) = *(pRead++)) {
	    ;
	}
	*(pWrite++) = (*pRead ? *(pRead++) : *pRead);
    }
}

/* Verifies whether the results of a search should be cached or not by
   checking if the search's basedn falls under any of the basedns for which
   the memcache is responsible. */
static int
memcache_validate_basedn(LDAPMemCache *cache, const char *basedn)
{
    int i;

    if ( cache->ldmemc_basedns == NULL ) {
	return( LDAP_SUCCESS );
    }

#if 1
    if (basedn == NULL) {
	basedn = "";
    }
#else
    /* XXXmcs: I do not understand this code... */
    if (basedn == NULL)
	return (cache->ldmemc_basedns && cache->ldmemc_basedns[0] ?
	                             LDAP_OPERATIONS_ERROR : LDAP_SUCCESS);
    }
#endif

    for (i = 0; cache->ldmemc_basedns[i]; i++) {
	if (memcache_compare_dn(basedn, cache->ldmemc_basedns[i],
	                        LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) {
	    return( LDAP_SUCCESS );
	}
    }

    return( LDAP_OPERATIONS_ERROR );
}

/* Calculates the length of the buffer needed to concatenate the contents of
   a ldap control. */
static int
memcache_get_ctrls_len(LDAPControl **ctrls)
{
    int len = 0, i;

    if (ctrls) {
	for (i = 0; ctrls[i]; i++) {
	    len += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) +
	           (ctrls[i]->ldctl_value).bv_len + 4;
	}
    }

    return len;
}

/* Contenates the contents of client and server controls to a buffer. */
static void
memcache_append_ctrls(char *buf, LDAPControl **serverCtrls,
				  LDAPControl **clientCtrls)
{
    int i, j;
    char *pCh = buf + strlen(buf);
    LDAPControl **ctrls;

    for (j = 0; j < 2; j++) {

	if ((ctrls = (j ? clientCtrls : serverCtrls)) == NULL)
	    continue;

	for (i = 0; ctrls[i]; i++) {
	    sprintf(pCh, "%s\n", NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid));
	    pCh += strlen(NSLDAPI_STR_NONNULL(ctrls[i]->ldctl_oid)) + 1;
	    if ((ctrls[i]->ldctl_value).bv_len > 0) {
		memcpy(pCh, (ctrls[i]->ldctl_value).bv_val,
		       (ctrls[i]->ldctl_value).bv_len);
		pCh += (ctrls[i]->ldctl_value).bv_len;
	    }
	    sprintf(pCh, "\n%i\n", (ctrls[i]->ldctl_iscritical ? 1 : 0));
	    pCh += 3;
	}
    }
}

/* Increases or decreases the size (in bytes) the given memcache currently
   uses.  If the size goes over the limit, the function returns an error. */
static int
memcache_adj_size(LDAPMemCache *cache, unsigned long size,
                  int usageFlags, int bAdd)
{
    LDAPDebug( LDAP_DEBUG_TRACE,
	    "memcache_adj_size: attempting to %s %ld %s bytes...\n",
	    bAdd ? "add" : "remove", size,
	    ( usageFlags & MEMCACHE_SIZE_ENTRIES ) ? "entry" : "non-entry" );

    if (bAdd) {
	cache->ldmemc_size_used += size;
	if ((cache->ldmemc_size > 0) &&
	    (cache->ldmemc_size_used > cache->ldmemc_size)) {

	    if (size > cache->ldmemc_size_entries) {
	        cache->ldmemc_size_used -= size;
		LDAPDebug( LDAP_DEBUG_TRACE,
			"memcache_adj_size: failed (size > size_entries %ld).\n",
			cache->ldmemc_size_entries, 0, 0 );
		return( LDAP_SIZELIMIT_EXCEEDED );
	    }

	    while (cache->ldmemc_size_used > cache->ldmemc_size) {
		if (memcache_access(cache, MEMCACHE_ACCESS_FLUSH_LRU,
		                    NULL, NULL, NULL) != LDAP_SUCCESS) {
	            cache->ldmemc_size_used -= size;
		    LDAPDebug( LDAP_DEBUG_TRACE,
			    "memcache_adj_size: failed (LRU flush failed).\n",
			    0, 0, 0 );
		    return( LDAP_SIZELIMIT_EXCEEDED );
	        }
	    }
	}
	if (usageFlags & MEMCACHE_SIZE_ENTRIES)
	    cache->ldmemc_size_entries += size;
    } else {
	cache->ldmemc_size_used -= size;
	assert(cache->ldmemc_size_used >= 0);
	if (usageFlags & MEMCACHE_SIZE_ENTRIES)
	    cache->ldmemc_size_entries -= size;
    }

#ifdef LDAP_DEBUG
    if ( cache->ldmemc_size == 0 ) {	/* no size limit */
	LDAPDebug( LDAP_DEBUG_TRACE,
		"memcache_adj_size: succeeded (new size: %ld bytes).\n",
		cache->ldmemc_size_used, 0, 0 );
    } else {
	LDAPDebug( LDAP_DEBUG_TRACE,
		"memcache_adj_size: succeeded (new size: %ld bytes, "
		"free space: %ld bytes).\n", cache->ldmemc_size_used,
		cache->ldmemc_size - cache->ldmemc_size_used, 0 );
    }
#endif /* LDAP_DEBUG */

    return( LDAP_SUCCESS );
}

/* Searches the cache for results for a particular search identified by
   parameter "key", which was generated ldap_memcache_createkey(). */
static int
memcache_search(LDAP *ld, unsigned long key, LDAPMessage **ppRes)
{
    int nRes;
    ldapmemcacheRes *pRes;

    *ppRes = NULL;

    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    nRes = memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_FIND,
	                   (void*)&key, (void*)(&pRes), NULL);

    if (nRes != LDAP_SUCCESS)
	return nRes;

    *ppRes = pRes->ldmemcr_resHead;
    assert((pRes->ldmemcr_req_id).ldmemcrid_msgid == -1);

    return( LDAP_SUCCESS );
}

/* Adds a new header into the cache as a place holder for entries
   arriving later. */
static int
memcache_add(LDAP *ld, unsigned long key, int msgid,
			const char *basedn)
{
    ldapmemcacheReqId reqid;

    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    reqid.ldmemcrid_msgid = msgid;
    reqid.ldmemcrid_ld = ld;

    return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_ADD,
	                   (void*)&key, (void*)&reqid, (void*)basedn);
}

/* Appends search entries arriving from the dir server to the cache. */
static int
memcache_append(LDAP *ld, int msgid, LDAPMessage *pRes)
{
    ldapmemcacheReqId reqid;

    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    reqid.ldmemcrid_msgid = msgid;
    reqid.ldmemcrid_ld = ld;

    return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND,
	                   (void*)&reqid, (void*)pRes, NULL);
}

/* Same as memcache_append(), but the entries being appended are the
   last from the dir server.  Once all entries for a search have arrived,
   the entries are moved from secondary to primary cache, and a time
   stamp is given to the entries. */
static int
memcache_append_last(LDAP *ld, int msgid, LDAPMessage *pRes)
{
    ldapmemcacheReqId reqid;

    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    reqid.ldmemcrid_msgid = msgid;
    reqid.ldmemcrid_ld = ld;

    return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_APPEND_LAST,
	                   (void*)&reqid, (void*)pRes, NULL);
}

/* Removes entries from the temporary cache. */
static int
memcache_remove(LDAP *ld, int msgid)
{
    ldapmemcacheReqId reqid;

    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    reqid.ldmemcrid_msgid = msgid;
    reqid.ldmemcrid_ld = ld;

    return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE,
	                   (void*)&reqid, NULL, NULL);
}

#if 0 /* this function is not used */
/* Wipes out everything in the temporary cache directory. */
static int
memcache_remove_all(LDAP *ld)
{
    if (!memcache_exist(ld))
        return LDAP_LOCAL_ERROR;

    return memcache_access(ld->ld_memcache, MEMCACHE_ACCESS_DELETE_ALL,
	                   NULL, NULL, NULL);
}
#endif /* 0 */

/* Returns TRUE or FALSE */
static int
memcache_exist(LDAP *ld)
{
    return (ld->ld_memcache != NULL);
}

/* Attaches cached entries to an ldap handle. */
static int
memcache_add_to_ld(LDAP *ld, int msgid, LDAPMessage *pMsg)
{
    int nRes = LDAP_SUCCESS;
    LDAPMessage **r;
    LDAPMessage *pCopy;

    nRes = memcache_dup_message(pMsg, msgid, 1, &pCopy, NULL);
    if (nRes != LDAP_SUCCESS)
	return nRes;

    for (r = &(ld->ld_responses); *r; r = &((*r)->lm_next))
	if ((*r)->lm_msgid == msgid)
	    break;

    if (*r)
	for (r = &((*r)->lm_chain); *r; r = &((*r)->lm_chain)) {
		;
	}

    *r = pCopy;

    return nRes;
}

/* Check if main_dn is included in {dn, scope} */
static int
memcache_compare_dn(const char *main_dn, const char *dn, int scope)
{
    int nRes;
    char **components = NULL;
    char **main_components = NULL;

    components = ldap_explode_dn(dn, 0);
    main_components = ldap_explode_dn(main_dn, 0);

    if (!components || !main_components) {
	nRes = LDAP_COMPARE_TRUE;
    }
    else {

	int i, main_i;

	main_i = ldap_count_values(main_components) - 1;
	i = ldap_count_values(components) - 1;

	for (; i >= 0 && main_i >= 0; i--, main_i--) {
	    if (strcasecmp(main_components[main_i], components[i]))
		break;
	}

	if (i >= 0 && main_i >= 0) {
	    nRes = LDAP_COMPARE_FALSE;
	}
	else if (i < 0 && main_i < 0) {
	    if (scope != LDAP_SCOPE_ONELEVEL)
		nRes = LDAP_COMPARE_TRUE;
	    else
		nRes = LDAP_COMPARE_FALSE;
	}
	else if (main_i < 0) {
	    nRes = LDAP_COMPARE_FALSE;
	}
	else {
	    if (scope == LDAP_SCOPE_BASE)
		nRes = LDAP_COMPARE_FALSE;
	    else if (scope == LDAP_SCOPE_SUBTREE)
		nRes = LDAP_COMPARE_TRUE;
	    else if (main_i == 0)
		nRes = LDAP_COMPARE_TRUE;
	    else
		nRes = LDAP_COMPARE_FALSE;
	}
    }

    if (components)
	ldap_value_free(components);

    if (main_components)
	ldap_value_free(main_components);

    return nRes;
}

/* Dup a complete separate copy of a berelement, including the buffers
   the berelement points to. */
static BerElement*
memcache_ber_dup(BerElement* pBer, unsigned long *pSize)
{
    BerElement *p = ber_dup(pBer);

    *pSize = 0;

    if (p) {

	*pSize += sizeof(BerElement) + EXTRA_SIZE;

	if (p->ber_len <= EXTRA_SIZE) {
	    p->ber_flags |= LBER_FLAG_NO_FREE_BUFFER;
	    p->ber_buf = (char*)p + sizeof(BerElement);
	} else {
	    p->ber_flags &= ~LBER_FLAG_NO_FREE_BUFFER;
	    p->ber_buf = (char*)NSLDAPI_CALLOC(1, p->ber_len);
	    *pSize += (p->ber_buf ? p->ber_len : 0);
	}

	if (p->ber_buf) {
	    p->ber_ptr = p->ber_buf + (pBer->ber_ptr - pBer->ber_buf);
	    p->ber_end = p->ber_buf + p->ber_len;
	    memcpy(p->ber_buf, pBer->ber_buf, p->ber_len);
	} else {
	    ber_free(p, 0);
	    p = NULL;
	    *pSize = 0;
	}
    }

    return p;
}

/* Dup a entry or a chain of entries. */
static int
memcache_dup_message(LDAPMessage *res, int msgid, int fromcache,
				LDAPMessage **ppResCopy, unsigned long *pSize)
{
    int nRes = LDAP_SUCCESS;
    unsigned long ber_size;
    LDAPMessage *pCur;
    LDAPMessage **ppCurNew;

    *ppResCopy = NULL;

    if (pSize)
	*pSize = 0;

    /* Make a copy of res */
    for (pCur = res, ppCurNew = ppResCopy; pCur;
         pCur = pCur->lm_chain, ppCurNew = &((*ppCurNew)->lm_chain)) {

	if ((*ppCurNew = (LDAPMessage*)NSLDAPI_CALLOC(1,
	                                     sizeof(LDAPMessage))) == NULL) {
	    nRes = LDAP_NO_MEMORY;
	    break;
	}

	memcpy(*ppCurNew, pCur, sizeof(LDAPMessage));
	(*ppCurNew)->lm_next = NULL;
	(*ppCurNew)->lm_ber = memcache_ber_dup(pCur->lm_ber, &ber_size);
	(*ppCurNew)->lm_msgid = msgid;
	(*ppCurNew)->lm_fromcache = (fromcache != 0);

	if (pSize)
	    *pSize += sizeof(LDAPMessage) + ber_size;
    }

    if ((nRes != LDAP_SUCCESS) && (*ppResCopy != NULL)) {
	ldap_msgfree(*ppResCopy);
	*ppResCopy = NULL;
	if (pSize)
	    *pSize = 0;
    }

    return nRes;
}

/************************* Cache Functions ***********************/

/* Frees a cache header. */
static int
memcache_free_entry(LDAPMemCache *cache, ldapmemcacheRes *pRes)
{
    if (pRes) {

	unsigned long size = sizeof(ldapmemcacheRes);

	if (pRes->ldmemcr_basedn) {
	    size += strlen(pRes->ldmemcr_basedn) + 1;
	    NSLDAPI_FREE(pRes->ldmemcr_basedn);
	}

	if (pRes->ldmemcr_resHead) {
	    size += pRes->ldmemcr_resSize;
	    ldap_msgfree(pRes->ldmemcr_resHead);
	}

	NSLDAPI_FREE(pRes);

	memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
	                  MEMCACHE_SIZE_DEDUCT);
    }

    return( LDAP_SUCCESS );
}

/* Detaches a cache header from the list of headers. */
static int
memcache_free_from_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
{
    if (pRes->ldmemcr_prev[index])
	pRes->ldmemcr_prev[index]->ldmemcr_next[index] =
	                                     pRes->ldmemcr_next[index];

    if (pRes->ldmemcr_next[index])
	pRes->ldmemcr_next[index]->ldmemcr_prev[index] =
	                                     pRes->ldmemcr_prev[index];

    if (cache->ldmemc_resHead[index] == pRes)
	cache->ldmemc_resHead[index] = pRes->ldmemcr_next[index];

    if (cache->ldmemc_resTail[index] == pRes)
	cache->ldmemc_resTail[index] = pRes->ldmemcr_prev[index];

    pRes->ldmemcr_prev[index] = NULL;
    pRes->ldmemcr_next[index] = NULL;

    return( LDAP_SUCCESS );
}

/* Inserts a new cache header to a list of headers. */
static int
memcache_add_to_list(LDAPMemCache *cache, ldapmemcacheRes *pRes, int index)
{
    if (cache->ldmemc_resHead[index])
	cache->ldmemc_resHead[index]->ldmemcr_prev[index] = pRes;
    else
	cache->ldmemc_resTail[index] = pRes;

    pRes->ldmemcr_prev[index] = NULL;
    pRes->ldmemcr_next[index] = cache->ldmemc_resHead[index];
    cache->ldmemc_resHead[index] = pRes;

    return( LDAP_SUCCESS );
}

/* Appends a chain of entries to the given cache header. */
static int
memcache_add_res_to_list(ldapmemcacheRes *pRes, LDAPMessage *pMsg,
				    unsigned long size)
{
    if (pRes->ldmemcr_resTail)
	pRes->ldmemcr_resTail->lm_chain = pMsg;
    else
	pRes->ldmemcr_resHead = pMsg;

    for (pRes->ldmemcr_resTail = pMsg;
         pRes->ldmemcr_resTail->lm_chain;
         pRes->ldmemcr_resTail = pRes->ldmemcr_resTail->lm_chain) {
		;
	}

    pRes->ldmemcr_resSize += size;

    return( LDAP_SUCCESS );
}


#ifdef LDAP_DEBUG
static void
memcache_print_list( LDAPMemCache *cache, int index )
{
    char		*name;
    ldapmemcacheRes	*restmp;

    switch( index ) {
    case LIST_TTL:
	name = "TTL";
	break;
    case LIST_LRU:
	name = "LRU";
	break;
    case LIST_TMP:
	name = "TMP";
	break;
    case LIST_TOTAL:
	name = "TOTAL";
	break;
    default:
	name = "unknown";
    }

    LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x %s list:\n",
	    cache, name, 0 );
    for ( restmp = cache->ldmemc_resHead[index]; restmp != NULL;
	    restmp = restmp->ldmemcr_next[index] ) {
	LDAPDebug( LDAP_DEBUG_TRACE,
		"    key: 0x%8.8lx, ld: 0x%x, msgid: %d\n",
		restmp->ldmemcr_crc_key,
		restmp->ldmemcr_req_id.ldmemcrid_ld,
		restmp->ldmemcr_req_id.ldmemcrid_msgid );
    }
    LDAPDebug( LDAP_DEBUG_TRACE, "memcache 0x%x end of %s list.\n",
	    cache, name, 0 );
}
#endif /* LDAP_DEBUG */

/* Tells whether a cached result has expired. */
static int
memcache_expired(LDAPMemCache *cache, ldapmemcacheRes *pRes,
                 unsigned long curTime)
{
    if (!cache->ldmemc_ttl)
	return 0;

    return ((unsigned long)difftime(
	                     (time_t)curTime,
			     (time_t)(pRes->ldmemcr_timestamp)) >=
			                          cache->ldmemc_ttl);
}

/* Operates the cache in a central place. */
static int
memcache_access(LDAPMemCache *cache, int mode,
			   void *pData1, void *pData2, void *pData3)
{
    int nRes = LDAP_SUCCESS;
    unsigned long size = 0;

    /* Add a new cache header to the cache. */
    if (mode == MEMCACHE_ACCESS_ADD) {
	unsigned long key = *((unsigned long*)pData1);
	char *basedn = (char*)pData3;
	ldapmemcacheRes *pRes = NULL;

	nRes = htable_get(cache->ldmemc_resTmp, pData2, (void**)&pRes);
	if (nRes == LDAP_SUCCESS)
	    return( LDAP_ALREADY_EXISTS );

	pRes = (ldapmemcacheRes*)NSLDAPI_CALLOC(1, sizeof(ldapmemcacheRes));
	if (pRes == NULL)
	    return( LDAP_NO_MEMORY );

	pRes->ldmemcr_crc_key = key;
	pRes->ldmemcr_req_id = *((ldapmemcacheReqId*)pData2);
	pRes->ldmemcr_basedn = (basedn ? nsldapi_strdup(basedn) : NULL);

	size += sizeof(ldapmemcacheRes) + strlen(basedn) + 1;
	nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
	                         MEMCACHE_SIZE_ADD);
	if (nRes == LDAP_SUCCESS)
	    nRes = htable_put(cache->ldmemc_resTmp, pData2, (void*)pRes);
	if (nRes == LDAP_SUCCESS)
	    memcache_add_to_list(cache, pRes, LIST_TMP);
	else
	    memcache_free_entry(cache, pRes);
    }
    /* Append entries to an existing cache header. */
    else if ((mode == MEMCACHE_ACCESS_APPEND) ||
	     (mode == MEMCACHE_ACCESS_APPEND_LAST)) {

	LDAPMessage *pMsg = (LDAPMessage*)pData2;
	LDAPMessage *pCopy = NULL;
	ldapmemcacheRes *pRes = NULL;

	nRes = htable_get(cache->ldmemc_resTmp, pData1, (void**)&pRes);
	if (nRes != LDAP_SUCCESS)
	    return nRes;

	nRes = memcache_dup_message(pMsg, pMsg->lm_msgid, 0, &pCopy, &size);
	if (nRes != LDAP_SUCCESS) {
	    nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
	    assert(nRes == LDAP_SUCCESS);
	    memcache_free_from_list(cache, pRes, LIST_TMP);
	    memcache_free_entry(cache, pRes);
	    return nRes;
	}

	nRes = memcache_adj_size(cache, size, MEMCACHE_SIZE_ENTRIES,
	                         MEMCACHE_SIZE_ADD);
	if (nRes != LDAP_SUCCESS) {
	    ldap_msgfree(pCopy);
	    nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
	    assert(nRes == LDAP_SUCCESS);
	    memcache_free_from_list(cache, pRes, LIST_TMP);
	    memcache_free_entry(cache, pRes);
	    return nRes;
	}

	memcache_add_res_to_list(pRes, pCopy, size);

	if (mode == MEMCACHE_ACCESS_APPEND)
	    return( LDAP_SUCCESS );

	nRes = htable_remove(cache->ldmemc_resTmp, pData1, NULL);
	assert(nRes == LDAP_SUCCESS);
	memcache_free_from_list(cache, pRes, LIST_TMP);
	(pRes->ldmemcr_req_id).ldmemcrid_ld = NULL;
	(pRes->ldmemcr_req_id).ldmemcrid_msgid = -1;
	pRes->ldmemcr_timestamp = (unsigned long)time(NULL);

	if ((nRes = htable_put(cache->ldmemc_resLookup,
	                       (void*)&(pRes->ldmemcr_crc_key),
                               (void*)pRes)) == LDAP_SUCCESS) {
	    memcache_add_to_list(cache, pRes, LIST_TTL);
	    memcache_add_to_list(cache, pRes, LIST_LRU);
	} else {
	    memcache_free_entry(cache, pRes);
	}
    }
    /* Search for cached entries for a particular search. */
    else if (mode == MEMCACHE_ACCESS_FIND) {

	ldapmemcacheRes **ppRes = (ldapmemcacheRes**)pData2;

	nRes = htable_get(cache->ldmemc_resLookup, pData1, (void**)ppRes);
	if (nRes != LDAP_SUCCESS)
	    return nRes;

	if (!memcache_expired(cache, *ppRes, (unsigned long)time(0))) {
	    memcache_free_from_list(cache, *ppRes, LIST_LRU);
	    memcache_add_to_list(cache, *ppRes, LIST_LRU);
	    return( LDAP_SUCCESS );
	}

	nRes = htable_remove(cache->ldmemc_resLookup, pData1, NULL);
	assert(nRes == LDAP_SUCCESS);
	memcache_free_from_list(cache, *ppRes, LIST_TTL);
	memcache_free_from_list(cache, *ppRes, LIST_LRU);
	memcache_free_entry(cache, *ppRes);
	nRes = LDAP_NO_SUCH_OBJECT;
	*ppRes = NULL;
    }
    /* Remove cached entries in the temporary cache. */
    else if (mode == MEMCACHE_ACCESS_DELETE) {

	ldapmemcacheRes *pCurRes = NULL;

	if ((nRes = htable_remove(cache->ldmemc_resTmp, pData1,
	                          (void**)&pCurRes)) == LDAP_SUCCESS) {
	    memcache_free_from_list(cache, pCurRes, LIST_TMP);
	    memcache_free_entry(cache, pCurRes);
	}
    }
    /* Wipe out the temporary cache. */
    else if (mode == MEMCACHE_ACCESS_DELETE_ALL) {

	nRes = htable_removeall(cache->ldmemc_resTmp, (void*)cache);
    }
    /* Remove expired entries from primary cache. */
    else if (mode == MEMCACHE_ACCESS_UPDATE) {

	ldapmemcacheRes *pCurRes = cache->ldmemc_resTail[LIST_TTL];
	unsigned long curTime = (unsigned long)time(NULL);

	for (; pCurRes; pCurRes = cache->ldmemc_resTail[LIST_TTL]) {

	    if (!memcache_expired(cache, pCurRes, curTime))
		break;

	    nRes = htable_remove(cache->ldmemc_resLookup,
		          (void*)&(pCurRes->ldmemcr_crc_key), NULL);
	    assert(nRes == LDAP_SUCCESS);
	    memcache_free_from_list(cache, pCurRes, LIST_TTL);
	    memcache_free_from_list(cache, pCurRes, LIST_LRU);
	    memcache_free_entry(cache, pCurRes);
	}
    }
    /* Wipe out the primary cache. */
    else if (mode == MEMCACHE_ACCESS_FLUSH_ALL) {

	ldapmemcacheRes *pCurRes = cache->ldmemc_resHead[LIST_TTL];

	nRes = htable_removeall(cache->ldmemc_resLookup, (void*)cache);

	for (; pCurRes; pCurRes = cache->ldmemc_resHead[LIST_TTL]) {
	    memcache_free_from_list(cache, pCurRes, LIST_LRU);
	    cache->ldmemc_resHead[LIST_TTL] =
		      cache->ldmemc_resHead[LIST_TTL]->ldmemcr_next[LIST_TTL];
	    memcache_free_entry(cache, pCurRes);
	}
	cache->ldmemc_resTail[LIST_TTL] = NULL;
    }
    /* Remove cached entries in both primary and temporary cache. */
    else if (mode == MEMCACHE_ACCESS_FLUSH) {

	int i, list_id, bDone;
	int scope = (int)(uintptr_t)pData2;
	char *dn = (char*)pData1;
	char *dnTmp;
	BerElement ber;
	LDAPMessage *pMsg;
	ldapmemcacheRes *pRes;

	if (cache->ldmemc_basedns) {
	    for (i = 0; cache->ldmemc_basedns[i]; i++) {
		if ((memcache_compare_dn(cache->ldmemc_basedns[i], dn,
			    LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) ||
		    (memcache_compare_dn(dn, cache->ldmemc_basedns[i],
			    LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE))
		    break;
	    }
	    if (cache->ldmemc_basedns[i] == NULL)
		return( LDAP_SUCCESS );
	}

	for (i = 0; i < 2; i++) {

	    list_id = (i == 0 ? LIST_TTL : LIST_TMP);

	    for (pRes = cache->ldmemc_resHead[list_id]; pRes != NULL;
		 pRes = pRes->ldmemcr_next[list_id]) {

		if ((memcache_compare_dn(pRes->ldmemcr_basedn, dn,
				 LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE) &&
		    (memcache_compare_dn(dn, pRes->ldmemcr_basedn,
				 LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE))
		    continue;

		for (pMsg = pRes->ldmemcr_resHead, bDone = 0;
		     !bDone && pMsg; pMsg = pMsg->lm_chain) {

		    if (!NSLDAPI_IS_SEARCH_ENTRY( pMsg->lm_msgtype ))
			continue;

		    ber = *(pMsg->lm_ber);
		    if (ber_scanf(&ber, "{a", &dnTmp) != LBER_ERROR) {
			bDone = (memcache_compare_dn(dnTmp, dn, scope) ==
							    LDAP_COMPARE_TRUE);
			ldap_memfree(dnTmp);
		    }
		}

		if (!bDone)
		    continue;

		if (list_id == LIST_TTL) {
		    nRes = htable_remove(cache->ldmemc_resLookup,
			  	 (void*)&(pRes->ldmemcr_crc_key), NULL);
		    assert(nRes == LDAP_SUCCESS);
		    memcache_free_from_list(cache, pRes, LIST_TTL);
		    memcache_free_from_list(cache, pRes, LIST_LRU);
		} else {
		    nRes = htable_remove(cache->ldmemc_resTmp,
				  (void*)&(pRes->ldmemcr_req_id), NULL);
		    assert(nRes == LDAP_SUCCESS);
		    memcache_free_from_list(cache, pRes, LIST_TMP);
		}
		memcache_free_entry(cache, pRes);
	    }
	}
    }
    /* Flush least recently used entries from cache */
    else if (mode == MEMCACHE_ACCESS_FLUSH_LRU) {

	ldapmemcacheRes *pRes = cache->ldmemc_resTail[LIST_LRU];

	if (pRes == NULL)
	    return LDAP_NO_SUCH_OBJECT;

	LDAPDebug( LDAP_DEBUG_TRACE,
		"memcache_access FLUSH_LRU: removing key 0x%8.8lx\n",
		pRes->ldmemcr_crc_key, 0, 0 );
	nRes = htable_remove(cache->ldmemc_resLookup,
	              (void*)&(pRes->ldmemcr_crc_key), NULL);
	assert(nRes == LDAP_SUCCESS);
	memcache_free_from_list(cache, pRes, LIST_TTL);
	memcache_free_from_list(cache, pRes, LIST_LRU);
	memcache_free_entry(cache, pRes);
    }
    /* Unknown command */
    else {
	nRes = LDAP_PARAM_ERROR;
    }

    return nRes;
}


#ifdef LDAP_DEBUG
static void
memcache_report_statistics( LDAPMemCache *cache )
{
    unsigned long	hitrate;

    if ( cache->ldmemc_stats.ldmemcstat_tries == 0 ) {
	hitrate = 0;
    } else {
	hitrate = ( 100L * cache->ldmemc_stats.ldmemcstat_hits ) /
	    cache->ldmemc_stats.ldmemcstat_tries;
    }
    LDAPDebug( LDAP_DEBUG_STATS, "memcache 0x%x:\n", cache, 0, 0 );
    LDAPDebug( LDAP_DEBUG_STATS, "    tries: %ld  hits: %ld  hitrate: %ld%%\n",
	    cache->ldmemc_stats.ldmemcstat_tries,
	    cache->ldmemc_stats.ldmemcstat_hits, hitrate );
    if ( cache->ldmemc_size <= 0 ) {	/* no size limit */
	LDAPDebug( LDAP_DEBUG_STATS, "    memory bytes used: %ld\n",
		cache->ldmemc_size_used, 0, 0 );
    } else {
	LDAPDebug( LDAP_DEBUG_STATS, "    memory bytes used: %ld free: %ld\n",
		cache->ldmemc_size_used,
		cache->ldmemc_size - cache->ldmemc_size_used, 0 );
    }
}
#endif /* LDAP_DEBUG */

/************************ Hash Table Functions *****************************/

/* Calculates size (# of entries) of hash table given the size limit for
   the cache. */
static int
htable_calculate_size(int sizelimit)
{
    int i, j;
    int size = (int)(((double)sizelimit /
	                (double)(sizeof(BerElement) + EXTRA_SIZE)) / 1.5);

    /* Get a prime # */
    size = (size & 0x1 ? size : size + 1);
    for (i = 3, j = size / 2; i < j; i++) {
	if ((size % i) == 0) {
	    size += 2;
	    i = 3;
	    j = size / 2;
	}
    }

    return size;
}

/* Returns the size in bytes of the given hash table. */
static int
htable_sizeinbytes(HashTable *pTable)
{
    if (!pTable)
	return 0;

    return (pTable->size * sizeof(HashTableNode));
}

/* Inserts an item into the hash table. */
static int
htable_put(HashTable *pTable, void *key, void *pData)
{
    int index = pTable->hashfunc(pTable->size, key);

    if (index >= 0 && index < pTable->size)
	return pTable->putdata(&(pTable->table[index].pData), key, pData);

    return( LDAP_OPERATIONS_ERROR );
}

/* Retrieves an item from the hash table. */
static int
htable_get(HashTable *pTable, void *key, void **ppData)
{
    int index = pTable->hashfunc(pTable->size, key);

    *ppData = NULL;

    if (index >= 0 && index < pTable->size)
	return pTable->getdata(pTable->table[index].pData, key, ppData);

    return( LDAP_OPERATIONS_ERROR );
}

/* Performs a miscellaneous operation on a hash table entry. */
static int
htable_misc(HashTable *pTable, void *key, void *pData)
{
    if (pTable->miscfunc) {
	int index = pTable->hashfunc(pTable->size, key);
	if (index >= 0 && index < pTable->size)
	    return pTable->miscfunc(&(pTable->table[index].pData), key, pData);
    }

    return( LDAP_OPERATIONS_ERROR );
}

/* Removes an item from the hash table. */
static int
htable_remove(HashTable *pTable, void *key, void **ppData)
{
    int index = pTable->hashfunc(pTable->size, key);

    if (ppData)
	*ppData = NULL;

    if (index >= 0 && index < pTable->size)
	return pTable->removedata(&(pTable->table[index].pData), key, ppData);

    return( LDAP_OPERATIONS_ERROR );
}

/* Removes everything in the hash table. */
static int
htable_removeall(HashTable *pTable, void *pData)
{
    int i;

    for (i = 0; i < pTable->size; i++)
	pTable->clrtablenode(&(pTable->table[i].pData), pData);

    return( LDAP_SUCCESS );
}

/* Creates a new hash table. */
static int
htable_create(int size_limit, HashFuncPtr hashf,
			 PutDataPtr putDataf, GetDataPtr getDataf,
			 RemoveDataPtr removeDataf, ClrTableNodePtr clrNodef,
			 MiscFuncPtr miscOpf, HashTable **ppTable)
{
    size_limit = htable_calculate_size(size_limit);

    if ((*ppTable = (HashTable*)NSLDAPI_CALLOC(1, sizeof(HashTable))) == NULL)
	return( LDAP_NO_MEMORY );

    (*ppTable)->table = (HashTableNode*)NSLDAPI_CALLOC(size_limit,
	                                       sizeof(HashTableNode));
    if ((*ppTable)->table == NULL) {
	NSLDAPI_FREE(*ppTable);
	*ppTable = NULL;
	return( LDAP_NO_MEMORY );
    }

    (*ppTable)->size = size_limit;
    (*ppTable)->hashfunc = hashf;
    (*ppTable)->putdata = putDataf;
    (*ppTable)->getdata = getDataf;
    (*ppTable)->miscfunc = miscOpf;
    (*ppTable)->removedata = removeDataf;
    (*ppTable)->clrtablenode = clrNodef;

    return( LDAP_SUCCESS );
}

/* Destroys a hash table. */
static int
htable_free(HashTable *pTable)
{
    NSLDAPI_FREE(pTable->table);
    NSLDAPI_FREE(pTable);
    return( LDAP_SUCCESS );
}

/**************** Hash table callbacks for temporary cache ****************/

/* Hash function */
static int
msgid_hashf(int table_size, void *key)
{
    uint_t code = (uint_t)(uintptr_t)((ldapmemcacheReqId*)key)->ldmemcrid_ld;
    return (((code << 20) + (code >> 12)) % table_size);
}

/* Called by hash table to insert an item. */
static int
msgid_putdata(void **ppTableData, void *key, void *pData)
{
    ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
    ldapmemcacheRes *pRes = (ldapmemcacheRes*)pData;
    ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
    ldapmemcacheRes *pCurRes = *ppHead;
    ldapmemcacheRes *pPrev = NULL;

    for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
	if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
	    break;
	pPrev = pCurRes;
    }

    if (pCurRes) {
	for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
	    if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
		                               pReqId->ldmemcrid_msgid)
		return( LDAP_ALREADY_EXISTS );
	    pPrev = pCurRes;
	}
	pPrev->ldmemcr_next[LIST_TTL] = pRes;
	pRes->ldmemcr_prev[LIST_TTL] = pPrev;
	pRes->ldmemcr_next[LIST_TTL] = NULL;
    } else {
	if (pPrev)
	    pPrev->ldmemcr_htable_next = pRes;
	else
	    *ppHead = pRes;
	pRes->ldmemcr_htable_next = NULL;
    }

    return( LDAP_SUCCESS );
}

/* Called by hash table to retrieve an item. */
static int
msgid_getdata(void *pTableData, void *key, void **ppData)
{
    ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;
    ldapmemcacheRes *pCurRes = (ldapmemcacheRes*)pTableData;

    *ppData = NULL;

    for (; pCurRes; pCurRes = pCurRes->ldmemcr_htable_next) {
	if ((pCurRes->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
	    break;
    }

    if (!pCurRes)
	return( LDAP_NO_SUCH_OBJECT );

    for (; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
	if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
	                                  pReqId->ldmemcrid_msgid) {
	    *ppData = (void*)pCurRes;
	    return( LDAP_SUCCESS );
	}
    }

    return( LDAP_NO_SUCH_OBJECT );
}

/* Called by hash table to remove an item. */
static int
msgid_removedata(void **ppTableData, void *key, void **ppData)
{
    ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
    ldapmemcacheRes *pCurRes = NULL;
    ldapmemcacheRes *pPrev = NULL;
    ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;

    if (ppData)
	*ppData = NULL;

    for (; pHead; pHead = pHead->ldmemcr_htable_next) {
	if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
	    break;
	pPrev = pHead;
    }

    if (!pHead)
	return( LDAP_NO_SUCH_OBJECT );

    for (pCurRes = pHead; pCurRes; pCurRes = pCurRes->ldmemcr_next[LIST_TTL]) {
	if ((pCurRes->ldmemcr_req_id).ldmemcrid_msgid ==
	                                        pReqId->ldmemcrid_msgid)
	    break;
    }

    if (!pCurRes)
	return( LDAP_NO_SUCH_OBJECT );

    if (ppData) {
	pCurRes->ldmemcr_next[LIST_TTL] = NULL;
	pCurRes->ldmemcr_prev[LIST_TTL] = NULL;
	pCurRes->ldmemcr_htable_next = NULL;
	*ppData = (void*)pCurRes;
    }

    if (pCurRes != pHead) {
	if (pCurRes->ldmemcr_prev[LIST_TTL])
	    pCurRes->ldmemcr_prev[LIST_TTL]->ldmemcr_next[LIST_TTL] =
	                                     pCurRes->ldmemcr_next[LIST_TTL];
	if (pCurRes->ldmemcr_next[LIST_TTL])
	    pCurRes->ldmemcr_next[LIST_TTL]->ldmemcr_prev[LIST_TTL] =
	                                     pCurRes->ldmemcr_prev[LIST_TTL];
	return( LDAP_SUCCESS );
    }

    if (pPrev) {
	if (pHead->ldmemcr_next[LIST_TTL]) {
	    pPrev->ldmemcr_htable_next = pHead->ldmemcr_next[LIST_TTL];
	    pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next =
			                   pHead->ldmemcr_htable_next;
	} else {
	    pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
	}
    } else {
	if (pHead->ldmemcr_next[LIST_TTL]) {
	    *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_next[LIST_TTL];
	    pHead->ldmemcr_next[LIST_TTL]->ldmemcr_htable_next =
			                   pHead->ldmemcr_htable_next;
	} else {
	    *((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;
	}
    }

    return( LDAP_SUCCESS );
}

/* Called by hash table to remove all cached entries associated to searches
   being performed using the given ldap handle. */
static int
msgid_clear_ld_items(void **ppTableData, void *key, void *pData)
{
    LDAPMemCache *cache = (LDAPMemCache*)pData;
    ldapmemcacheRes *pHead = *((ldapmemcacheRes**)ppTableData);
    ldapmemcacheRes *pPrev = NULL;
    ldapmemcacheRes *pCurRes = NULL;
    ldapmemcacheReqId *pReqId = (ldapmemcacheReqId*)key;

    for (; pHead; pHead = pHead->ldmemcr_htable_next) {
	if ((pHead->ldmemcr_req_id).ldmemcrid_ld == pReqId->ldmemcrid_ld)
	    break;
	pPrev = pHead;
    }

    if (!pHead)
	return( LDAP_NO_SUCH_OBJECT );

    if (pPrev)
	pPrev->ldmemcr_htable_next = pHead->ldmemcr_htable_next;
    else
	*((ldapmemcacheRes**)ppTableData) = pHead->ldmemcr_htable_next;

    for (pCurRes = pHead; pHead; pCurRes = pHead) {
	pHead = pHead->ldmemcr_next[LIST_TTL];
	memcache_free_from_list(cache, pCurRes, LIST_TMP);
	memcache_free_entry(cache, pCurRes);
    }

    return( LDAP_SUCCESS );
}

/* Called by hash table for removing all items in the table. */
static void
msgid_clearnode(void **ppTableData, void *pData)
{
    LDAPMemCache *cache = (LDAPMemCache*)pData;
    ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
    ldapmemcacheRes *pSubHead = *ppHead;
    ldapmemcacheRes *pCurRes = NULL;

    for (; *ppHead; pSubHead = *ppHead) {
	ppHead = &((*ppHead)->ldmemcr_htable_next);
	for (pCurRes = pSubHead; pSubHead; pCurRes = pSubHead) {
	    pSubHead = pSubHead->ldmemcr_next[LIST_TTL];
	    memcache_free_from_list(cache, pCurRes, LIST_TMP);
	    memcache_free_entry(cache, pCurRes);
	}
    }
}

/********************* Hash table for primary cache ************************/

/* Hash function */
static int
attrkey_hashf(int table_size, void *key)
{
    return ((*((unsigned long*)key)) % table_size);
}

/* Called by hash table to insert an item. */
static int
attrkey_putdata(void **ppTableData, void *key, void *pData)
{
    unsigned long attrkey = *((unsigned long*)key);
    ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
    ldapmemcacheRes *pRes = *ppHead;

    for (; pRes; pRes = pRes->ldmemcr_htable_next) {
	if (pRes->ldmemcr_crc_key == attrkey)
	    return( LDAP_ALREADY_EXISTS );
    }

    pRes = (ldapmemcacheRes*)pData;
    pRes->ldmemcr_htable_next = *ppHead;
    *ppHead = pRes;

    return( LDAP_SUCCESS );
}

/* Called by hash table to retrieve an item. */
static int
attrkey_getdata(void *pTableData, void *key, void **ppData)
{
    unsigned long attrkey = *((unsigned long*)key);
    ldapmemcacheRes *pRes = (ldapmemcacheRes*)pTableData;

    for (; pRes; pRes = pRes->ldmemcr_htable_next) {
	if (pRes->ldmemcr_crc_key == attrkey) {
	    *ppData = (void*)pRes;
	    return( LDAP_SUCCESS );
	}
    }

    *ppData = NULL;

    return( LDAP_NO_SUCH_OBJECT );
}

/* Called by hash table to remove an item. */
static int
attrkey_removedata(void **ppTableData, void *key, void **ppData)
{
    unsigned long attrkey = *((unsigned long*)key);
    ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
    ldapmemcacheRes *pRes = *ppHead;
    ldapmemcacheRes *pPrev = NULL;

    for (; pRes; pRes = pRes->ldmemcr_htable_next) {
	if (pRes->ldmemcr_crc_key == attrkey) {
	    if (ppData)
		*ppData = (void*)pRes;
	    if (pPrev)
		pPrev->ldmemcr_htable_next = pRes->ldmemcr_htable_next;
	    else
		*ppHead = pRes->ldmemcr_htable_next;
	    pRes->ldmemcr_htable_next = NULL;
	    return( LDAP_SUCCESS );
	}
	pPrev = pRes;
    }

    if (ppData)
	*ppData = NULL;

    return( LDAP_NO_SUCH_OBJECT );
}

/* Called by hash table for removing all items in the table. */
static void
attrkey_clearnode(void **ppTableData, void *pData)
{
    ldapmemcacheRes **ppHead = (ldapmemcacheRes**)ppTableData;
    ldapmemcacheRes *pRes = *ppHead;

    (void)pData;

    for (; *ppHead; pRes = *ppHead) {
	ppHead = &((*ppHead)->ldmemcr_htable_next);
	pRes->ldmemcr_htable_next = NULL;
    }
}

/***************************** CRC algorithm ********************************/

/* From http://www.faqs.org/faqs/compression-faq/part1/section-25.html */

/*
 * Build auxiliary table for parallel byte-at-a-time CRC-32.
 */
#define NSLDAPI_CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */

static unsigned long crc32_table[256] = {
    0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
    0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
    0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7,
    0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
    0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3,
    0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
    0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef,
    0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
    0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb,
    0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
    0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
    0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
    0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4,
    0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
    0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08,
    0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
    0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc,
    0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
    0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050,
    0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
    0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
    0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
    0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1,
    0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
    0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5,
    0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
    0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9,
    0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
    0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd,
    0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
    0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
    0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
    0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2,
    0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
    0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e,
    0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
    0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a,
    0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
    0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676,
    0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
    0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
    0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
    0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 };

/* Initialized first time "crc32()" is called. If you prefer, you can
 * statically initialize it at compile time. [Another exercise.]
 */

static unsigned long
crc32_convert(char *buf, int len)
{
    char *p;
#ifdef OSF1V4D
    unsigned int crc;
#else
    unsigned long crc;	    /* FIXME: this is not 32-bits on all platforms! */
#endif /* OSF1V4D */

    crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
    for (p = buf; len > 0; ++p, --len)
	crc = ((crc << 8) ^ crc32_table[(crc >> 24) ^ *p]) & 0xffffffff;

    return (unsigned long) ~crc;    /* transmit complement, per CRC-32 spec */
}