/*
**++
**  FACILITY:
**      CACHE_VERIFY.C
**
**  ABSTRACT:
**      Cache Message Id check and validation utilities for caching for News.
**      Routines for checking all the links in the cache and produces
**      statistics etc.
**
**  AUTHOR:
**      Bill Teahan, University of Waikato, Hamilton, New Zealand
**
**  COPYRIGHT:
**      Copyright © 1991
**
**	6.1b7   6-Jul-1993 Charles Bailey  bailey@genetics.upenn.edu
**	 - add checks to prevent division by 0 when compiling statistics
**	V6.1b9	17-Aug-1994     Mark Martinec   mark.martinec@ijs.si
**	  - code cleanup to make it compile under gcc 2.6.0 with full
**	    warnings reporting turned on - with no or very few harmless warnings
**	V6.1b9	17-Sep-1994     Mark Martinec   mark.martinec@ijs.si
**	  - code cleanup to preserve the read-only nature of string literals
**	    (strategically placed 'const' attribute to string parameters)
**--
**/

#ifdef __GNUC__
#define variant_union	volatile union
#define variant_struct	volatile struct
#endif

#ifdef __DECC
#pragma message save
#pragma message disable (MACROEXT)
#endif

#ifndef NAKED_INCLUDES
#define NAKED_INCLUDES 0
#endif

#if NAKED_INCLUDES

#include starlet
#include descrip
#include lckdef
#include prvdef
#include jpidef
#include lnmdef
#include psldef
#include chfdef
#include ssdef

#include types
#include stddef
#include stdio
#include stdlib
#include string
#include ctype

#else	/* !NAKED_INCLUDES */

#include <starlet.h>
#include <descrip.h>
#include <lckdef.h>
#include <prvdef.h>
#include <jpidef.h>
#include <lnmdef.h>
#include <psldef.h>
#include <chfdef.h>
#include <ssdef.h>

#if defined(__GNUC__)
  /*  problem is that both multinet and gnu_cc_include contain sys/types.h    *
   *  and the multinet version is missing some declarations (dev_t,off_t,...) *
   *  which are necessary when stat.h gets included, so we force GNU types.h  */
#  include <gnu_cc_include:[sys]types.h>
#elif defined(TWG) || defined(MULTINET)
#  include <sys/types.h>    /* take the Multinet (or other IP vendor) types.h */
#else
#  include <types.h>        /* take whatever we have */
#endif

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#endif

#ifdef __DECC
#pragma message restore
#endif

#include "cachedefine.h"

extern void cache_free_lock(CACHE *);
extern void cache_get_lock(CACHE *);

int used [CACHE_IDS_SIZE];

/* Find the depth of the hash list */
int cache_find_hash_list_depth(index, cache)
	int index;
 	CACHE *cache;
{
	int ptr, depth;

	/* search down list */
	ptr = cache->cache_hash_list [index];
	depth = 0;
	while ((ptr != 0) && (depth < 100)) {
	    depth++;
	    ptr = cache->cache_ids [ptr].cache_fptr;
        }
	return( depth );
}

/* Dump the hash list at INDEX */
void cache_dump_hash_index(index, cache)
	int index;
 	CACHE *cache;
{
	int ptr, depth;

	/* search down list */
	depth = 0;
	ptr = cache->cache_hash_list [index];
	while ((ptr != 0) && (depth < 100)) {
	    depth++;
	    printf( "Hval %d ptr %d depth %d hvalue %X id %s\n", 
		cache->cache_ids [ptr].cache_hval, ptr, depth,
    		cache->cache_ids [ptr].cache_hvalue,
		cache->cache_ids [ptr].cache_id );
	    ptr = cache->cache_ids [ptr].cache_fptr;
        }
}

/* Find the hash linked list from INDEX with depth >= DEPTH. */
void cache_dump_hash_list(index, depth, cache)
	int index, depth;
     	CACHE *cache;
{             
	int i, d;

	if (index < 0)
	    index = 1;
	cache_get_lock( cache );
	for (i=index; i<CACHE_HASH_SIZE; i++) {
	    d = cache_find_hash_list_depth( i, cache );
	    if (d >= depth) {
		printf( "Hash index = %d\n", i );
		cache_dump_hash_index( i, cache );
		break;
	    }
	}
	cache_free_lock( cache );
}

/* Check the hash linked list for inconsistencies. Return the depth */
int cache_check_hash_list(index, cache)
	int index;
 	CACHE *cache;
{
	int len, depth, ptr, bptr, fptr, old_ptr, hval;

	/* search down list */
	len = 0;
	old_ptr = 0;
	ptr = cache->cache_hash_list [index];
	depth = 0;
	while ((ptr != 0) && (depth < 100)) {
	    depth++;
	    if (used [ptr])
		printf( "Multiply used link in hash list %d (ptr=%d) :\n",
			 index, ptr );
	    else
		used [ptr] = 1;
	    bptr = cache->cache_ids [ptr].cache_bptr;
	    fptr = cache->cache_ids [ptr].cache_fptr;
	    hval = cache->cache_ids [ptr].cache_hval;
	    /* printf( "ptr %d bptr %d fptr %d hval %d\n", 
			ptr, bptr, fptr, hval ); */

	    /* check hval is the same for every link in the list */
	    if (hval != index) {
		printf( "Invalid hval in hash linked list %d (ptr=%d) :\n",
			 index, ptr );
		printf( "- hval = %d, should be %d\n", hval, index );
	    }
	    /* check back pointers are valid */
	    if (bptr != old_ptr) {
		printf( "Invalid back pointer in hash index %d (ptr=%d) :\n",
			 index, ptr );
		printf( "- bptr = %d, should be %d\n", bptr, old_ptr );
	    }
	    old_ptr = ptr;
	    ptr = fptr;
        }
	if (ptr != 0) {
	    printf( "Unterminated linked list in hash index %d (ptr=%d) :\n",
			index, ptr );
	    printf( "- depth count = %d\n", depth );
	    depth = -1; /* do not include in statistics */
	}
	return( depth );
}

/* Verify all the links in the hash lists, and print statistics at the end */
void cache_verify_cache(cache)
 	CACHE *cache;
{
	int i, depth, ccount, ecount, hcount, mcount, zcount,
	    dtotal, dlarge;
	int ucount, lcount [16];

	ccount = ecount = hcount = mcount = ucount = zcount = 0;
	dlarge = dtotal = 0;
	for (i=0; i<16; i++)
	    lcount [i] = 0;
	for (i=1; i<CACHE_IDS_SIZE; i++)
	    used [i] = 0;

	/* check all linked lists are consistent */
	cache_get_lock( cache );
	for (i=1; i<CACHE_HASH_SIZE; i++) {
	    if ((i / 1000) * 1000 == i)
		printf( "%d...\015", i );
	    depth = cache_check_hash_list( i, cache );
	    if (depth < 0)
		ecount++;
 	    else {
		if (depth == 0)
		    zcount++;
		dtotal += depth;
		if (depth > 16)
		    lcount [15]++;
		else
		    lcount [depth]++;
		if (depth > dlarge)
		    dlarge = depth;
	    }
	}

	printf( "\n" );
	/* check for cache ids not in a hash list */
	for (i=1; i<CACHE_IDS_SIZE; i++) {
	    if (used [i])
		ucount++;
	    if ((!used [i]) && (cache->cache_ids [i].cache_hval != 0)) {
  		printf( "Cache id not found in a hash list %d\n", i );
		printf( "- hval : %d, fptr %d, bptr %d\n",
			cache->cache_ids [i].cache_hval,
			cache->cache_ids [i].cache_fptr,
			cache->cache_ids [i].cache_bptr );
	    }
	}
	cache_free_lock( cache );
 	printf( "\n" );

	hcount = (CACHE_HASH_SIZE - ecount - 1);
	printf( "\n" );
	printf( "Summary :\n" );
	printf( "---------\n" );
	printf( "Number of terminated hash linked lists = %d\n", hcount );
	printf( "Number of non-terminated hash linked lists = %d\n", ecount );
	printf( "Number of zero-length hash linked lists = %d\n", zcount );
	printf( "Longest hash linked list has depth = %d\n", dlarge );
	printf( "Average hash linked list depth = %f\n",
		((float) dtotal / (float) ((hcount - zcount) ? (hcount - zcount) : 1)));
    	printf( "Total number of links = %d\n", dtotal );
    	printf( "Number of used hash links = %d\n", ucount );
	printf( "\n" );
	printf( "Histogram of hash linked list depths : \n" );
	for (i = 0; i <= dlarge; i++) { /* print out counts for each depth */
	    printf( "Depth = %d : %d\n", i, lcount [i] );
	    if (i > 1) mcount += lcount [i];
	    if (i > 1) ccount += (i-1) * lcount [i];
	}
	printf( "Number of multiple links = %d\n", mcount );
	printf( "Percentage of multiple links = %f\n",
		(100.0 * ((float) mcount / (float) (dtotal ? dtotal : 1))));
	printf( "Number of collisions = %d\n", ccount );
	printf( "Percentage of collisions = %f\n",
		(100.0 * ((float) ccount / (float) (dtotal ? dtotal : 1))));

}
