/* 
   Copyright © 2000-2006 Dave Carrigan
   All rights reserved.

   This module is free software; you can redistribute it and/or modify
   it under the same terms as Apache itself. This module is
   distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or
   FITNESS FOR A PARTICULAR PURPOSE. The copyright holder of this
   module can not be held liable for any general, special, incidental
   or consequential damages arising out of the use of the module.

   $Id: auth_ldap_cache_mgr.c,v 1.3 2001/02/16 23:06:20 dave Exp $
*/

#include "auth_ldap.h"

static const int primes[] =
{
  11,
  19,
  37,
  73,
  109,
  163,
  251,
  367,
  557,
  823,
  1237,
  1861,
  2777,
  4177,
  6247,
  9371,
  14057,
  21089,
  31627,
  47431,
  71143,
  106721,
  160073,
  240101,
  360163,
  540217,
  810343,
  1215497,
  1823231,
  2734867,
  4102283,
  6153409,
  9230113,
  13845163,
  0
};

void
ald_free(void *ptr)
{
#ifdef WITH_SHARED_LDAP_CACHE
  if (auth_ldap_mm != NULL) {
    ap_mm_free(auth_ldap_mm, ptr);
  } else {
    free(ptr);
  }
#else
  free(ptr);
#endif
}

void *
ald_alloc(int size)
{
#ifdef WITH_SHARED_LDAP_CACHE
  if (auth_ldap_mm != NULL) {
    return (void *)ap_mm_malloc(auth_ldap_mm, size);
  } else {
    return (void *)malloc(size);
  }
#else
  return (void *)malloc(size);
#endif
}

char *
ald_strdup(char *s)
{
#ifdef WITH_SHARED_LDAP_CACHE
  if (auth_ldap_mm != NULL) {
    return ap_mm_strdup(auth_ldap_mm, s);
  } else {
    return strdup(s);
  }
#else
  return strdup(s);
#endif
}

/*
 * Computes the hash on a set of strings. The first argument is the number
 * of strings to hash, the rest of the args are strings. 
 * Algorithm taken from glibc.
 */
unsigned long
ald_hash_string(int nstr, ...)
{
  int i;
  va_list args;
  unsigned long h=0, g;
  char *str, *p;
  
  va_start(args, nstr);
  for (i=0; i < nstr; ++i) {
    str = va_arg(args, char *);
    for (p = str; *p; ++p) {
      h = ( h << 4 ) + *p;
      if ( ( g = h & 0xf0000000 ) ) {
	h = h ^ (g >> 24);
	h = h ^ g;
      }
    }
  }
  va_end(args);

  return h;
}

/*
  Purges a cache that has gotten full. We keep track of the time that we
  added the entry that made the cache 3/4 full, then delete all entries
  that were added before that time. It's pretty simplistic, but time to
  purge is only O(n), which is more important.
*/
void
ald_cache_purge(ald_cache *cache)
{
  int i;
  cache_node *current, *next, *prev;
  time_t t;
  
  time(&(cache->last_purge));
  cache->npurged = 0;
  cache->numpurges++;

  for (i=0; i < cache->size; ++i) {
    current = cache->nodes[i];
    next = prev = NULL;
    while (current != NULL) {
      if (current->add_time < cache->marktime) {
	next = current->next;
	(*cache->free)(current->payload);
	ald_free(current);
	cache->numentries--;
	cache->npurged++;
	current = next;
	if (prev == NULL) {
	  cache->nodes[i] = next;
	} else {
	  prev->next = next;
	}
      } else {
	prev = current;
	current = current->next;
      }
    }
  }

  time(&t);
  cache->avg_purgetime = 
    ((t - cache->last_purge) + (cache->avg_purgetime * (cache->numpurges-1))) / 
    cache->numpurges;
}

ald_cache *
ald_create_cache(unsigned long maxentries,
		 unsigned long (*hashfunc)(void *), 
		 int (*comparefunc)(void *, void *),
		 void * (*copyfunc)(void *),
		 void (*freefunc)(void *))
{
  ald_cache *cache;
  int i;

  if (maxentries <= 0)
    return NULL;

  cache = (ald_cache *)ald_alloc(sizeof(ald_cache));
  if (cache == NULL)
    return NULL;

  cache->maxentries = maxentries;
  cache->numentries = 0;
  cache->size = maxentries / 3;
  if (cache->size < 64) cache->size = 64;
  for (i = 0; primes[i] && primes[i] < cache->size; ++i) ;
  cache->size = primes[i]? primes[i] : primes[i-1];
  cache->nodes = (cache_node **)ald_alloc(cache->size * sizeof(cache_node *));
  for (i=0; i < cache->size; ++i)
    cache->nodes[i] = NULL;

  cache->hash = hashfunc;
  cache->compare = comparefunc;
  cache->copy = copyfunc;
  cache->free = freefunc;

  cache->fullmark = cache->maxentries / 4 * 3;
  cache->marktime = 0;
  cache->avg_purgetime = 0.0;
  cache->numpurges = 0;
  cache->last_purge = 0;
  cache->npurged = 0;

  cache->fetches = 0;
  cache->hits = 0;
  cache->inserts = 0;
  cache->removes = 0;

  return cache;
}

void
ald_destroy_cache(ald_cache *cache)
{
  int i;
  cache_node *p, *q;

  if (cache == NULL)
    return;

  for (i = 0; i < cache->size; ++i) {
    p = cache->nodes[i];
    q = NULL;
    while (p != NULL) {
      q = p->next;
      (*cache->free)(p->payload);
      ald_free(p);
      p = q;
    }
  }
  ald_free(cache->nodes);
}

void *
ald_cache_fetch(ald_cache *cache, void *payload)
{
  int hashval;
  cache_node *p;

  if (cache == NULL)
    return NULL;

  cache->fetches++;

  hashval = (*cache->hash)(payload) % cache->size;
  for (p = cache->nodes[hashval]; 
       p && !(*cache->compare)(p->payload, payload);
       p = p->next) ;

  if (p != NULL) {
    cache->hits++;
    return p->payload;
  } else {
    return NULL;
  }
}

/*
 * Insert an item into the cache. 
 * *** Does not catch duplicates!!! ***
 */
void
ald_cache_insert(ald_cache *cache, void *payload)
{
  int hashval;
  cache_node *node;

  if (cache == NULL || payload == NULL)
    return;

  cache->inserts++;
  hashval = (*cache->hash)(payload) % cache->size;
  node = (cache_node *)ald_alloc(sizeof(cache_node));
  time(&(node->add_time));
  node->payload = (*cache->copy)(payload);
  node->next = cache->nodes[hashval];
  cache->nodes[hashval] = node;
  if (++cache->numentries == cache->fullmark) 
    time(&(cache->marktime));
  if (cache->numentries >= cache->maxentries)
    ald_cache_purge(cache);
}

void
ald_cache_remove(ald_cache *cache, void *payload)
{
  int hashval;
  cache_node *p, *q;
  
  if (cache == NULL)
    return;

  cache->removes++;
  hashval = (*cache->hash)(payload) % cache->size;
  for (p = cache->nodes[hashval], q=NULL;
       p && !(*cache->compare)(p->payload, payload);
       p = p->next) {
    q = p;
  }
  
  /* If p is null, it means that we couldn't find the node, so just return */
  if (p == NULL)
    return;

  if (q == NULL) {
    /* We found the node, and it's the first in the list */
    cache->nodes[hashval] = p->next;
  } else {
    /* We found the node and it's not the first in the list */
    q->next = p->next;
  }
  (*cache->free)(p->payload);
  ald_free(p);
  cache->numentries--;
}

void
ald_cache_display_stats(ald_cache *cache, request_rec *r, char *name)
{
  int i;
  int totchainlen = 0;
  int nchains = 0;
  double chainlen;
  cache_node *p;

  ap_log_rerror(APLOG_MARK, APLOG_DEBUG|APLOG_NOERRNO, r,
		"{%d} Entering ald_cache_display_stats", (int)getpid());

  if (cache == NULL)
    return;

  for (i=0; i < cache->size; ++i) {
    if (cache->nodes[i] != NULL) {
      nchains++;
      for (p = cache->nodes[i]; p != NULL; p = p->next)
	totchainlen++;
    }
  }
  chainlen = nchains? (double)totchainlen / (double)nchains : 0;

  ap_rputs("<tr valign='top'>", r);

  ap_rprintf(r, "<td nowrap>%s</td>", name);

  ap_rprintf(r, "<td align='right' nowrap>%lu (%.0f%% full)</td>",
	     cache->numentries, 
	     (double)cache->numentries / (double)cache->maxentries * 100.0);

  ap_rprintf(r, "<td align='right'>%.1f</td>", chainlen);

  ap_rprintf(r, 
	     "<td align='right'>%lu/%lu</td>"
	     "<td align='right'>%.0f%%</td>",
	     cache->hits, 	     
	     cache->fetches,
	     (cache->fetches > 0? 
	      (double)(cache->hits) / (double)(cache->fetches) * 100.0 : 100.0));

  ap_rprintf(r, "<td align='right'>%lu/%lu</td>",
	     cache->inserts, cache->removes);

  if (cache->numpurges) {
    ap_rprintf(r, 
	       "<td align='right'>%lu</td>\n"
	       "<td align='right' nowrap>%s</td>\n", 
	       cache->numpurges,
	       ctime(&cache->last_purge));
  } else {
    ap_rputs("<td colspan='2' align='center'>(none)</td>\n", r);
  }

  ap_rprintf(r, "<td align='right'>%.2g</td>\n", cache->avg_purgetime);

  ap_rputs("</tr>", r);
}