#line 2 "servlist.c"
/*-
 * C-SaCzech
 * Copyright (c) 1996-2002 Jaromir Dolecek <dolecek@ics.muni.cz>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by Jaromir Dolecek
 *	for the CSacek project.
 * 4. The name of Jaromir Dolecek may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY JAROMIR DOLECEK ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL JAROMIR DOLECEK BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* $Id: servlist.c,v 1.14 2002/02/03 11:13:41 dolecek Exp $ */

#include "csacek.h"

typedef struct {
	const char	*name;
	size_t		 sn_len;
	int	 port;
	int	 chksum;
} csa_server_t;

struct csa_slist {
	size_t max_len[4];
	size_t len[4];
	csa_server_t *servers[4];
	struct pool *pool;
};

#define COMPUTE_CHKSUM(name, chksum, len, i, hash) \
	chksum = 0;				\
	len = strlen(name);			\
	for(i=0; i< len; i++) { 		\
		chksum += CSA_UPPER(name[i]);	\
	}					\
	hash = chksum % 4;

/*
 * Following if condition might be a bit hard to parse, don't look
 * if you are easy to be scared :)
 *
 * The comparing algorith is as follows:
 * 1. if the feature is higher in "new" item, it is greater and
 *    condition is TRUE
 * 2. if the feature is equal in both the "new" item and
 *    listitem, take "lower" level feature and goto 1.
 * 3. if the feature is lower in the inserted item, listitem
 *    is greater and condition is FALSE
 */
#define ITEM_IS_EQ_OR_GREATER(chksum, port, len, name, listitem) \
	(chksum > listitem->chksum ||					\
	    (chksum == listitem->chksum && (port > listitem->port ||	\
		(port == listitem->port && (len > listitem->sn_len ||	\
		    (len == listitem->sn_len				\
			&& strcasecmp(name, listitem->name) >= 0))))))

static void x_csa_cs_cleanup __P((void *));

/*
 * Cleanup function for global list of CSacek servers. Needed to properly
 * null the variable if the pool is deallocated (e.g. when the server is
 * reloaded).
 */
static void
x_csa_cs_cleanup(null)
	void *null;
{
	csacek_servers = NULL;
}

/*
 * Init global list of csacek servers. Besides normal csa_slist_t
 * inicialization, www.csacek.cz is also added to the list.
 */
void
csa_cs_slist_init(wpool)
	struct pool *wpool;
{
	csacek_servers = csa_slist_init(wpool);

	/* register the cleanup so that csacek_servers would be properly
	 * unset if the pool is destroyed */
	ap_register_cleanup(wpool, NULL, x_csa_cs_cleanup, x_csa_cs_cleanup);

	/* always add www.csacek.cz into list of CSacek servers */
	csa_slist_add(csacek_servers, "www.csacek.cz", 0);
}

/*
 * Allocate and initialize slist structure and return pointer to it.
 */
csa_slist_t *
csa_slist_init(wpool)
	struct pool *wpool;
{
	csa_slist_t *list;

	list = (csa_slist_t *) ap_pcalloc(wpool, sizeof(csa_slist_t));
	list->pool = wpool;
	return list;
}

/*
 * add server + port to list of CSacek servers
 */
int
csa_slist_add(list, name, port)
  csa_slist_t *list;
  const char *name;
  int port;
{
	size_t len, i, old_len, new_len, idx, lim;
	int chksum, hash;
	csa_server_t *new_sarr, *s, *p, *base;

	if (!name || !*name) {
		/* empty server name, no reason why we should add the recod */
		/* to list */
		return 1;
	}

	COMPUTE_CHKSUM(name, chksum, len, i, hash);

	/*
	 * Allocate more space if the hash list is full already.
	 */
	if (list->max_len[hash] == list->len[hash]) {
		old_len = list->len[hash];
		new_len = (!old_len) ? 8 : (old_len<<1);
		new_sarr = (csa_server_t *)ap_palloc(list->pool,
				(int)(new_len * sizeof(csa_server_t)));
		if (old_len > 0) {
			memcpy(new_sarr, list->servers[hash],
				old_len * sizeof(csa_server_t));
		}
		list->servers[hash] = new_sarr;
		list->max_len[hash] = new_len;
	}

	/*
	 * Arrange things so that the entries are sorted by checksum, port,
	 * length of name and name. Use the fact that previous items are
	 * sorted and find the spot where should the new entry be put
	 * with derivate of binary search. Note we don't check whether
	 * the same item is on the list already - such thing should
	 * not happen very often and it's not worth the wasted CPU cycles.
	 */
	base = &list->servers[hash][0]; 
	lim = list->len[hash];
	idx = 0;
	for(; lim != 0; lim >>= 1) {
		p = &base[lim >> 1];
		if (ITEM_IS_EQ_OR_GREATER(chksum, port, len, name, p)) {
			idx += (lim >> 1) + 1;
			base = &p[1];
			lim--;
			continue;
		}
	}

	/*
	 * If necessary, shift data to create place for the new entry.
	 */
	if (idx < list->len[hash]) {
		p = &list->servers[hash][idx];
		memmove(&p[1], p, (list->len[hash] - idx)*sizeof(csa_server_t));
	}

	/*
	 * Fill in the spot.
	 */
	s = &list->servers[hash][idx];
	s->name   = name;
	s->sn_len = len;
	s->port   = port;
	s->chksum = chksum;

	list->len[hash]++;

	return 0;
}

/*
 * Checks if the server is on list of CSacek servers.
 */
int
csa_is_csacek_server(list, name, port)
	const csa_slist_t *list;
	const char *name;
	int port;
{
	const csa_server_t *base, *p;
	int chksum, hash;
	size_t i, len, lim;

	if (!name) return 1;
	if (!list)  return 0;

	COMPUTE_CHKSUM(name, chksum, len, i, hash);

	/*
	 * Search the list. Alhorith taken from implementation of
	 * NetBSD bsearch(3).
	 */
	base = &list->servers[hash][0];
	lim = list->len[hash];
	for(; lim != 0; lim >>= 1) {
		p = &base[lim >> 1];
	 	if (chksum == p->chksum && (!p->port || port == p->port)
			&& len == p->sn_len
			&& strcasecmp(name, p->name) == 0)
		{
			return (1);
		}

		if (ITEM_IS_EQ_OR_GREATER(chksum, port, len, name, p)) {
			base = &p[1];
			lim--;
		}
	}

	return (0);
} 

#ifdef CSA_WANT_INFO
/*
 * Writes servers from list of CSacek servers into output.
 */
void
csa_slist_dump(p)
  csa_params_t *p;
{
	const csa_slist_t *slist = p->csacek_servers;
	csa_server_t *serv;
	char buf[2048];
	size_t len, listlen, j, i;
	int need_comma = 0;

    loop:
	for(j=0; j < 4; j++) {
	    serv = slist->servers[j];
	    listlen = slist->len[j];
	    for(i=0; i < listlen; i++) {
		if (need_comma)
			csa_add_output(p, ", ", 2, 0);

		if (serv[i].port)  {
			len = sprintf(buf, "<TT>%s:%d</TT>", serv[i].name,
				serv[i].port);
		} else
			len = sprintf(buf, "<TT>%s</TT>", serv[i].name);

		csa_add_output(p, buf, len, 0);
		need_comma = 1;
	    }
	}	    

	if (slist != csacek_servers && csacek_servers != NULL) {
		slist = csacek_servers;
		goto loop;
	}
}
#endif /* CSA_WANT_INFO */