diff -urN ../nagios.orig/base/utils.c ./base/utils.c
--- ../nagios.orig/base/utils.c	2005-06-13 14:41:57 +0200
+++ ./base/utils.c	2005-06-29 00:00:30 +0200
@@ -32,7 +32,7 @@
 #include "../include/broker.h"
 #include "../include/nebmods.h"
 #include "../include/nebmodules.h"
-
+#include "../include/hash.h"
 
 #ifdef EMBEDDEDPERL
 #include "../include/epn_nagios.h"
@@ -4245,68 +4245,6 @@
         }
 
 
-
-/******************************************************************/
-/************************* HASH FUNCTIONS *************************/
-/******************************************************************/
-
-/* single hash function */
-int hashfunc1(const char *name1,int hashslots){
-	unsigned int i,result;
-
-	result=0;
-
-	if(name1)
-		for(i=0;i<strlen(name1);i++)
-			result+=name1[i];
-
-	result=result%hashslots;
-
-	return result;
-        }
-
-
-/* dual hash function */
-int hashfunc2(const char *name1,const char *name2,int hashslots){
-	unsigned int i,result;
-
-	result=0;
-	if(name1)
-		for(i=0;i<strlen(name1);i++)
-			result+=name1[i];
-
-	if(name2)
-		for(i=0;i<strlen(name2);i++)
-			result+=name2[i];
-
-	result=result%hashslots;
-
-	return result;
-        }
-
-
-/* single hash data comparison */
-int compare_hashdata1(const char *val1, const char *val2){
-	
-	return strcmp(val1,val2);
-        }
-
-
-/* dual hash data comparison */
-int compare_hashdata2(const char *val1a, const char *val1b, const char *val2a, const char *val2b){
-	int result;
-
-	result=strcmp(val1a,val2a);
-	if(result>0)
-		return 1;
-	else if(result<0)
-		return -1;
-	else
-		return strcmp(val1b,val2b);
-        }
-
-
-
 /******************************************************************/
 /************************* FILE FUNCTIONS *************************/
 /******************************************************************/
diff -urN ../nagios.orig/cgi/cgiutils.c ./cgi/cgiutils.c
--- ../nagios.orig/cgi/cgiutils.c	2004-11-15 09:28:06 +0100
+++ ./cgi/cgiutils.c	2005-06-29 00:09:51 +0200
@@ -27,6 +27,7 @@
 #include "../include/locations.h"
 #include "../include/objects.h"
 #include "../include/statusdata.h"
+#include "../include/hash.h"
 
 #include "../include/cgiutils.h"
 
@@ -679,71 +680,6 @@
         }
 
 
-
-/**********************************************************
- *************** CHAINED HASH FUNCTIONS *******************
- **********************************************************/
-
-
-/* single hash function */
-int hashfunc1(const char *name1,int hashslots){
-	unsigned int i,result;
-
-	result=0;
-
-	if(name1)
-		for(i=0;i<strlen(name1);i++)
-			result+=name1[i];
-
-	result=result%hashslots;
-
-	return result;
-        }
-
-
-/* dual hash function */
-int hashfunc2(const char *name1,const char *name2,int hashslots){
-	unsigned int i,result;
-
-	result=0;
-	if(name1)
-		for(i=0;i<strlen(name1);i++)
-			result+=name1[i];
-
-	if(name2)
-		for(i=0;i<strlen(name2);i++)
-			result+=name2[i];
-
-	result=result%hashslots;
-
-	return result;
-        }
-
-
-/* single hash data comparison */
-int compare_hashdata1(const char *val1, const char *val2){
-	
-	return strcmp(val1,val2);
-        }
-
-
-/* dual hash data comparison */
-int compare_hashdata2(const char *val1a, const char *val1b, const char *val2a, const char *val2b){
-	int result;
-
-	result=strcmp(val1a,val2a);
-	if(result>0)
-		return 1;
-	else if(result<0)
-		return -1;
-	else
-		return strcmp(val1b,val2b);
-        }
-
-
-
-
-
 /**********************************************************
  ******************* LIFO FUNCTIONS ***********************
  **********************************************************/
diff -urN ../nagios.orig/common/comments.c ./common/comments.c
--- ../nagios.orig/common/comments.c	2005-06-13 14:41:57 +0200
+++ ./common/comments.c	2005-06-28 23:55:34 +0200
@@ -27,6 +27,7 @@
 #include "../include/common.h"
 #include "../include/comments.h"
 #include "../include/objects.h"
+#include "../include/hash.h"
 
 /***** IMPLEMENTATION-SPECIFIC INCLUDES *****/
 
diff -urN ../nagios.orig/common/objects.c ./common/objects.c
--- ../nagios.orig/common/objects.c	2005-06-13 14:41:57 +0200
+++ ./common/objects.c	2005-06-28 23:54:25 +0200
@@ -26,6 +26,7 @@
 #include "../include/config.h"
 #include "../include/common.h"
 #include "../include/objects.h"
+#include "../include/hash.h"
 
 #ifdef NSCORE
 #include "../include/nagios.h"
diff -urN ../nagios.orig/common/statusdata.c ./common/statusdata.c
--- ../nagios.orig/common/statusdata.c	2005-06-13 14:41:57 +0200
+++ ./common/statusdata.c	2005-06-28 23:57:09 +0200
@@ -29,6 +29,7 @@
 #include "../include/common.h"
 #include "../include/objects.h"
 #include "../include/statusdata.h"
+#include "../include/hash.h"
 
 #ifdef NSCORE
 #include "../include/nagios.h"
diff -urN ../nagios.orig/include/cgiutils.h.in ./include/cgiutils.h.in
--- ../nagios.orig/include/cgiutils.h.in	2004-11-15 09:28:06 +0100
+++ ./include/cgiutils.h.in	2005-06-15 11:31:53 +0200
@@ -447,11 +447,6 @@
 int read_all_object_configuration_data(char *,int);
 int read_all_status_data(char *,int);
 
-int hashfunc1(const char *name1, int hashslots);
-int hashfunc2(const char *name1, const char *name2, int hashslots);
-int compare_hashdata1(const char *,const char *);
-int compare_hashdata2(const char *,const char *,const char *,const char *);
-
 void strip(char *);                                		/* strips newlines, carriage returns, and spaces from end of buffer */
 void sanitize_plugin_output(char *);                            /* strips HTML and bad characters from plugin output */
 
diff -urN ../nagios.orig/include/comments.h ./include/comments.h
--- ../nagios.orig/include/comments.h	2004-11-05 15:18:52 +0100
+++ ./include/comments.h	2005-06-29 00:07:21 +0200
@@ -53,12 +53,6 @@
 #define ACKNOWLEDGEMENT_COMMENT         4
 
 
-/*************************** CHAINED HASH LIMITS ***************************/
-
-#define COMMENT_HASHSLOTS      1024
-
-
-
 /**************************** DATA STRUCTURES ******************************/
 
 
diff -urN ../nagios.orig/include/hash.h ./include/hash.h
--- ../nagios.orig/include/hash.h	1970-01-01 01:00:00 +0100
+++ ./include/hash.h	2005-06-29 00:06:00 +0200
@@ -0,0 +1,209 @@
+/*
+ * $Id: $
+ *
+ * lazy hash-functions for Nagios.
+ * Lazy because they don't require the string length to be known.
+ *
+ * Author: Andreas Ericsson <ae@op5.se>
+ *
+ * The functions in this file are supposed to be drop-in replacements for
+ * the current additive hashes, which use this semantic;
+ *
+ * hashfunc1(char *key, int buckets);
+ * hashfunc2(char *key1, char *key2, int buckets);
+ *
+ * Both those functions are *ALWAYS* called with 'buckets' being a macro
+ * and defined as a power of 2, making (buckets - 1) the preferred bitmask.
+ *
+ * Therefore those two functions are nowadays macros so that a (sane)
+ * preprocessor can consign the dec instruction to oblivion, making them
+ * half a cycle faster.
+ *
+ * That also means that we can only use linear hashes that work byte-wise.
+ * This isn't exactly optimal, and we'll be punished for it somewhat on
+ * multipiped CPU's as the internal state is always dependent on the next
+ * parsed byte, but it's still roughly 40% faster than calling strlen() once
+ * for each key, and the drop-in replacement requirement forces it.
+ *
+ *
+ * Note that I (Andreas Ericsson) didn't invent any of the algorithms in
+ * here. I just implemented them. For licensing issues, see LICENSE.hash
+ * in the base directory of the Nagios distribution.
+ *
+ * For a more complete list of hashes, complete with a proper benchmarking
+ * program for practical applications, see http://oss.op5.se/hash (soon).
+ *
+ */
+
+/*
+ * General purpose hash-functions are inside this file to make it possible
+ * to inline the functions from any file, which won't work if they aren't
+ * declared static (at least not with gcc).
+ */
+
+#ifndef NAGIOS_HASH_H
+#include "../include/config.h"  /* for types and such */
+
+/* close enough to accurate. Since we mask off the bits we need it doesn't
+ * matter if this is actually a 64 bit value. For the algorithms used here
+ * It doesn't actually matter if it's smaller either. */
+typedef unsigned int u32;
+
+
+/***************** CHAINED HASH LIMITS ****************/
+/*
+ * All table-sizes *MUST* be powers of 2. This is so we can use a
+ * bitmask to extract the precision we want rather than a modulo op.
+ * Bitmasks use 0.5 latency cycles, while modulo range from 4 to 260.
+ */
+#define SERVICE_HASHSLOTS              1024
+#define HOST_HASHSLOTS                 1024
+#define COMMAND_HASHSLOTS              256
+#define TIMEPERIOD_HASHSLOTS           64
+#define CONTACT_HASHSLOTS              128
+#define CONTACTGROUP_HASHSLOTS         64
+#define HOSTGROUP_HASHSLOTS            128
+#define SERVICEGROUP_HASHSLOTS         128
+#define HOSTEXTINFO_HASHSLOTS          1024
+#define SERVICEEXTINFO_HASHSLOTS       1024
+
+#define HOSTDEPENDENCY_HASHSLOTS       1024
+#define SERVICEDEPENDENCY_HASHSLOTS    1024
+#define HOSTESCALATION_HASHSLOTS       1024
+#define SERVICEESCALATION_HASHSLOTS    1024
+
+#define COMMENT_HASHSLOTS  1024
+
+#ifdef NSCGI
+/* these should only be used when compiling the CGI's, so trigger a
+ * compiler error if they're referenced somewhere in the core */
+# define SERVICESTATUS_HASHSLOTS        8192
+# define HOSTSTATUS_HASHSLOTS           8192
+#endif
+
+
+/* use Kiem-Phong Vo's linear congruential hash per default */
+#define USE_HASH_PHONG_VO1 1
+
+#if defined(USE_HASH_PHONG_VO1)
+/*
+ * lhash_phong_vo - Berkely License, The Regents of California
+ *
+ * Phong Vo's linear congruential hash.
+ */
+
+# define hash_func(key) lhash_phong_vo_lc1(key)
+# define DCHARHASH(h, c) ((h) = 0x63c63cd9 * (h) + 0x9c39c33d + ((unsigned char)c))
+static inline u32
+lhash_phong_vo_lc1(char *k)
+{
+	register u32 h = 0;
+
+	while(*k) DCHARHASH(h, *k++);
+
+	return h;
+}
+
+/* same function using dual keys */
+#define hash_func2(k1, k2) lhash_phong_vo_lc1_2(k1, k2)
+static inline u32
+lhash_phong_vo_lc1_2(char *k1, char *k2)
+{
+	register u32 h = 0;
+	while(*k1) DCHARHASH(h, *k1++);
+	while(*k2) DCHARHASH(h, *k2++);
+
+	return h;
+}
+
+#elif defined(USE_HASH_PHONG_VO2)
+/*
+ * lhash_phong_vo_2 - Common Public License 1.0, AT & T Corp.
+ *
+ * Another linear congruential hash from the same author.
+ */
+# define hash_func(key) lhash_phong_vo_lc2(key)
+#define dtcharhash(h, c) (((h) << 4) + (h) + ((unsigned char)c) + 97531)
+static inline u32
+lhash_phong_vo_lc2(char *k)
+{
+	register u32 h = 0;
+
+	while(*k) h = dtcharhash(h, *k++);
+	return h;
+}
+#else
+/*
+ * lhash_gstr - GPL or Public Domain (not sure about this one)
+ *
+ * glib's g_str_hash(), with minor modifications.
+ *
+ * It produces a 31-bit hash, but that's OK since we won't use more than 16.
+ *
+ * Do a web search for "g_str_hash X31_HASH" if you want to know more.
+ * This is the same function as that described in Kernighan and Pike,
+ * "The Practice of Programming", section 2.9.
+ *
+ * This performs worse than the two above on P4, PentiumM and Athlon XP
+ * but is included anyways because of its loose and easily determined
+ * license.
+ */
+#define hash_func(key) lhash_gstr(key)
+static inline u32
+lhash_gstr(register char *k)
+{
+	register u32 h = 0;
+
+	while(*k)
+		h = (h << 5) - h + (unsigned char)*k++;       /* h * 31 + *key */
+
+	return h;
+}
+#endif /* END - hashtype selection */
+
+
+/* some fair few useful macros */
+#define hashfunc1(key, buckets) hash_func(key) % (buckets)
+#define compare_hashdata1(k1, k2) strcmp(k1, k2)
+
+/* some implementations can hash dual keys properly */
+#ifdef hash_func2
+# define hashfunc2(key1, key2, buckets) hash_func2((key1), (key2)) % (buckets)
+#else
+# define hashfunc2(key1, key2, buckets) \
+	hash_dual_keys(key1, key2) % (buckets)
+
+/*
+ * This must be a function because of the folding concat of the two hashes.
+ */
+static inline u32
+hash_dual_keys(char *k1, char *k2)
+{
+	register u32 h1, h2;
+
+	h1 = hash_func(k1);
+	h2 = hash_func(k2);
+
+	/* This concatenation method was suggested by Paul Hsieh.
+	 * It prevents bits from cancelling if hashes are equal or there are
+	 * very few 1 bits set in h1. It's good enough for our purposes. */
+	return (h1 + (h2 >> 16)) ^ (h2 << 16);
+}
+#endif /* hash_func2 */
+
+/*
+ * This must also be a function, because of the variable needed to
+ * prevent double strcmp()'s.
+ */
+static inline u32
+compare_hashdata2(const char *k1a, const char *k1b, const char *k2a, const char *k2b)
+{
+	int result;
+
+	/* branch for collisions. large networks need the optimizations more */
+	if((result = strcmp(k1a, k2a)) != 0)
+		return result;
+
+	return strcmp(k1b, k2b);
+}
+#endif /* NAGIOS_HASH_H */
diff -urN ../nagios.orig/include/nagios.h.in ./include/nagios.h.in
--- ../nagios.orig/include/nagios.h.in	2005-06-07 17:58:24 +0200
+++ ./include/nagios.h.in	2005-06-15 14:05:28 +0200
@@ -595,13 +595,6 @@
 void free_notification_list(void);		     	/* frees all memory allocated to the notification list */
 
 
-/**** Hash Functions ****/
-int hashfunc1(const char *name1, int hashslots);
-int hashfunc2(const char *name1, const char *name2, int hashslots);
-int compare_hashdata1(const char *,const char *);
-int compare_hashdata2(const char *,const char *,const char *,const char *);
-
-
 /**** Miscellaneous Functions ****/
 void sighandler(int);                                	/* handles signals */
 void service_check_sighandler(int);                     /* handles timeouts when executing service checks */
diff -urN ../nagios.orig/include/objects.h ./include/objects.h
--- ../nagios.orig/include/objects.h	2004-11-15 09:28:06 +0100
+++ ./include/objects.h	2005-06-15 12:10:51 +0200
@@ -41,26 +40,6 @@
 #define MAX_CONTACT_ADDRESSES                   6       /* max number of custom addresses a contact can have */
 
 
-/***************** CHAINED HASH LIMITS ****************/
-
-#define SERVICE_HASHSLOTS                      1024
-#define HOST_HASHSLOTS                         1024
-#define COMMAND_HASHSLOTS                      256
-#define TIMEPERIOD_HASHSLOTS                   64
-#define CONTACT_HASHSLOTS                      128
-#define CONTACTGROUP_HASHSLOTS                 64
-#define HOSTGROUP_HASHSLOTS                    128
-#define SERVICEGROUP_HASHSLOTS                 128
-#define HOSTEXTINFO_HASHSLOTS                  1024
-#define SERVICEEXTINFO_HASHSLOTS               1024
-
-#define HOSTDEPENDENCY_HASHSLOTS               1024
-#define SERVICEDEPENDENCY_HASHSLOTS            1024
-#define HOSTESCALATION_HASHSLOTS               1024
-#define SERVICEESCALATION_HASHSLOTS            1024
-
-
-
 /****************** DATA STRUCTURES *******************/
 
 /* TIMERANGE structure */
diff -urN ../nagios.orig/include/statusdata.h ./include/statusdata.h
--- ../nagios.orig/include/statusdata.h	2004-11-05 15:18:52 +0100
+++ ./include/statusdata.h	2005-06-15 12:09:16 +0200
@@ -40,13 +40,6 @@
 #define READ_ALL_STATUS_DATA    READ_PROGRAM_STATUS | READ_HOST_STATUS | READ_SERVICE_STATUS
 
 
-
-/*************************** CHAINED HASH LIMITS ***************************/
-
-#define SERVICESTATUS_HASHSLOTS      1024
-#define HOSTSTATUS_HASHSLOTS         1024
-
-
 /**************************** DATA STRUCTURES ******************************/
 
 
