[thirdparty/squid.git] / src / CacheDigest.cc


/*
 * $Id: CacheDigest.cc,v 1.24 1998/07/20 19:25:28 wessels Exp $
 *
 * DEBUG: section 70    Cache Digest
 * AUTHOR: Alex Rousskov
 *
 * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
 * --------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from the
 *  Internet community.  Development is led by Duane Wessels of the
 *  National Laboratory for Applied Network Research and funded by
 *  the National Science Foundation.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *  
 *  This program 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.  See the
 *  GNU General Public License for more details.
 *  
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *  
 */

#include "squid.h"

/* local types */
typedef struct {
    int bit_count;		/* total number of bits */
    int bit_on_count;		/* #bits turned on */
    int bseq_len_sum;		/* sum of all bit seq length */
    int bseq_count;		/* number of bit seqs */
} CacheDigestStats;

/* local functions */
static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);

/* static array used by cacheDigestHashKey for optimization purposes */
static u_num32 hashed_keys[4];

static void
cacheDigestInit(CacheDigest * cd, int capacity, int bpe)
{
    const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe);
    assert(cd);
    assert(capacity > 0 && bpe > 0);
    assert(mask_size > 0);
    cd->capacity = capacity;
    cd->bits_per_entry = bpe;
    cd->mask_size = mask_size;
    cd->mask = xcalloc(cd->mask_size, 1);
    debug(70, 2) ("cacheDigestInit: capacity: %d entries, bpe: %d; size: %d bytes\n",
	cd->capacity, cd->bits_per_entry, cd->mask_size);
}

CacheDigest *
cacheDigestCreate(int capacity, int bpe)
{
    CacheDigest *cd = memAllocate(MEM_CACHE_DIGEST);
    assert(MD5_DIGEST_CHARS == 16);	/* our hash functions rely on 16 byte keys */
    cacheDigestInit(cd, capacity, bpe);
    return cd;
}

static void
cacheDigestClean(CacheDigest * cd)
{
    assert(cd);
    xfree(cd->mask);
    cd->mask = NULL;
}

void
cacheDigestDestroy(CacheDigest * cd)
{
    assert(cd);
    cacheDigestClean(cd);
    memFree(MEM_CACHE_DIGEST, cd);
}

CacheDigest *
cacheDigestClone(const CacheDigest * cd)
{
    CacheDigest *clone;
    assert(cd);
    clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry);
    clone->count = cd->count;
    clone->del_count = cd->del_count;
    assert(cd->mask_size == clone->mask_size);
    xmemcpy(clone->mask, cd->mask, cd->mask_size);
    return clone;
}

void
cacheDigestClear(CacheDigest * cd)
{
    assert(cd);
    cd->count = cd->del_count = 0;
    memset(cd->mask, 0, cd->mask_size);
}

/* changes mask size, resets bits to 0, preserves "cd" pointer */
void
cacheDigestChangeCap(CacheDigest * cd, int new_cap)
{
    assert(cd);
    cacheDigestClean(cd);
    cacheDigestInit(cd, new_cap, cd->bits_per_entry);
}

/* returns true if the key belongs to the digest */
int
cacheDigestTest(const CacheDigest * cd, const cache_key * key)
{
    assert(cd && key);
    /* hash */
    cacheDigestHashKey(cd, key);
    /* test corresponding bits */
    return
	CBIT_TEST(cd->mask, hashed_keys[0]) &&
	CBIT_TEST(cd->mask, hashed_keys[1]) &&
	CBIT_TEST(cd->mask, hashed_keys[2]) &&
	CBIT_TEST(cd->mask, hashed_keys[3]);
}

void
cacheDigestAdd(CacheDigest * cd, const cache_key * key)
{
    assert(cd && key);
    /* hash */
    cacheDigestHashKey(cd, key);
    /* turn on corresponding bits */
#if CD_FAST_ADD
    CBIT_SET(cd->mask, hashed_keys[0]);
    CBIT_SET(cd->mask, hashed_keys[1]);
    CBIT_SET(cd->mask, hashed_keys[2]);
    CBIT_SET(cd->mask, hashed_keys[3]);
#else
    {
	int on_xition_cnt = 0;
	if (!CBIT_TEST(cd->mask, hashed_keys[0])) {
	    CBIT_SET(cd->mask, hashed_keys[0]);
	    on_xition_cnt++;
	}
	if (!CBIT_TEST(cd->mask, hashed_keys[1])) {
	    CBIT_SET(cd->mask, hashed_keys[1]);
	    on_xition_cnt++;
	}
	if (!CBIT_TEST(cd->mask, hashed_keys[2])) {
	    CBIT_SET(cd->mask, hashed_keys[2]);
	    on_xition_cnt++;
	}
	if (!CBIT_TEST(cd->mask, hashed_keys[3])) {
	    CBIT_SET(cd->mask, hashed_keys[3]);
	    on_xition_cnt++;
	}
	statHistCount(&Counter.cd.on_xition_count, on_xition_cnt);
    }
#endif
    cd->count++;
}

void
cacheDigestDel(CacheDigest * cd, const cache_key * key)
{
    assert(cd && key);
    cd->del_count++;
    /* we do not support deletions from the digest */
}

/* returns mask utilization parameters */
static void
cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
{
    int on_count = 0;
    int pos = cd->mask_size * 8;
    int seq_len_sum = 0;
    int seq_count = 0;
    int cur_seq_len = 0;
    int cur_seq_type = 1;
    assert(stats);
    memset(stats, 0, sizeof(*stats));
    while (pos-- > 0) {
	const int is_on = 0 != CBIT_TEST(cd->mask, pos);
	if (is_on)
	    on_count++;
	if (is_on != cur_seq_type || !pos) {
	    seq_len_sum += cur_seq_len;
	    seq_count++;
	    cur_seq_type = is_on;
	    cur_seq_len = 0;
	}
	cur_seq_len++;
    }
    stats->bit_count = cd->mask_size * 8;
    stats->bit_on_count = on_count;
    stats->bseq_len_sum = seq_len_sum;
    stats->bseq_count = seq_count;
}

int
cacheDigestBitUtil(const CacheDigest * cd)
{
    CacheDigestStats stats;
    assert(cd);
    cacheDigestStats(cd, &stats);
    return xpercentInt(stats.bit_on_count, stats.bit_count);
}

void
cacheDigestGuessStatsUpdate(cd_guess_stats * stats, int real_hit, int guess_hit)
{
    assert(stats);
    if (real_hit) {
	if (guess_hit)
	    stats->true_hits++;
	else
	    stats->false_misses++;
    } else {
	if (guess_hit)
	    stats->false_hits++;
	else
	    stats->true_misses++;
    }
}

void
cacheDigestGuessStatsReport(const cd_guess_stats * stats, StoreEntry * sentry, const char *label)
{
    const int true_count = stats->true_hits + stats->true_misses;
    const int false_count = stats->false_hits + stats->false_misses;
    const int hit_count = stats->true_hits + stats->false_hits;
    const int miss_count = stats->true_misses + stats->false_misses;
    const int tot_count = true_count + false_count;

    assert(label);
    assert(tot_count == hit_count + miss_count);	/* paranoid */

    storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label);
    storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n");
    storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n");

    storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	stats->true_hits, xpercent(stats->true_hits, tot_count),
	stats->true_misses, xpercent(stats->true_misses, tot_count),
	true_count, xpercent(true_count, tot_count));
    storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	stats->false_hits, xpercent(stats->false_hits, tot_count),
	stats->false_misses, xpercent(stats->false_misses, tot_count),
	false_count, xpercent(false_count, tot_count));
    storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	hit_count, xpercent(hit_count, tot_count),
	miss_count, xpercent(miss_count, tot_count),
	tot_count, xpercent(tot_count, tot_count));
    storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
	stats->close_hits, xpercentInt(stats->close_hits, stats->false_hits));
}

void
cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e)
{
    CacheDigestStats stats;
    assert(cd && e);
    cacheDigestStats(cd, &stats);
    storeAppendPrintf(e, "%s digest: size: %d bytes\n",
	label ? label : "", stats.bit_count / 8
	);
    storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n",
	cd->count,
	cd->capacity,
	xpercentInt(cd->count, cd->capacity)
	);
    storeAppendPrintf(e, "\t deletion attempts: %d\n",
	cd->del_count
	);
    storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
	cd->bits_per_entry,
	stats.bit_on_count, stats.bit_count,
	xpercentInt(stats.bit_on_count, stats.bit_count)
	);
    storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
	stats.bseq_count,
	xdiv(stats.bseq_len_sum, stats.bseq_count)
	);
}

size_t
cacheDigestCalcMaskSize(int cap, int bpe)
{
    return (size_t) (cap * bpe + 7) / 8;
}

static void
cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
{
    const unsigned int bit_count = cd->mask_size * 8;
    unsigned int tmp_keys[4];
    /* we must memcpy to ensure alignment */
    xmemcpy(tmp_keys, key, sizeof(tmp_keys));
    hashed_keys[0] = htonl(tmp_keys[0]) % bit_count;
    hashed_keys[1] = htonl(tmp_keys[1]) % bit_count;
    hashed_keys[2] = htonl(tmp_keys[2]) % bit_count;
    hashed_keys[3] = htonl(tmp_keys[3]) % bit_count;
    debug(70, 9) ("cacheDigestHashKey: %s -(%d)-> %d %d %d %d\n",
	storeKeyText(key), bit_count,
	hashed_keys[0], hashed_keys[1], hashed_keys[2], hashed_keys[3]);
}
Commit	Line	Data
bdbb6d04	1
bdbb6d04	2	/*
98abae73	3	* $Id: CacheDigest.cc,v 1.24 1998/07/20 19:25:28 wessels Exp $
bdbb6d04	4	*
8638fc66	5	* DEBUG: section 70 Cache Digest
bdbb6d04	6	* AUTHOR: Alex Rousskov
	7	*
	8	* SQUID Internet Object Cache http://squid.nlanr.net/Squid/
	9	* --------------------------------------------------------
	10	*
	11	* Squid is the result of efforts by numerous individuals from the
	12	* Internet community. Development is led by Duane Wessels of the
	13	* National Laboratory for Applied Network Research and funded by
	14	* the National Science Foundation.
	15	*
	16	* This program is free software; you can redistribute it and/or modify
	17	* it under the terms of the GNU General Public License as published by
	18	* the Free Software Foundation; either version 2 of the License, or
	19	* (at your option) any later version.
	20	*
	21	* This program is distributed in the hope that it will be useful,
	22	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	23	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	24	* GNU General Public License for more details.
	25	*
	26	* You should have received a copy of the GNU General Public License
	27	* along with this program; if not, write to the Free Software
cbdec147	28	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
bdbb6d04	29	*
	30	*/
	31
	32	#include "squid.h"
	33
12784378	34	/* local types */
12784378	35	typedef struct {
b644367b	36	int bit_count; /* total number of bits */
	37	int bit_on_count; /* #bits turned on */
	38	int bseq_len_sum; /* sum of all bit seq length */
	39	int bseq_count; /* number of bit seqs */
12784378	40	} CacheDigestStats;
	41
	42	/* local functions */
13c31e72	43	static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);
bdbb6d04	44
	45	/* static array used by cacheDigestHashKey for optimization purposes */
	46	static u_num32 hashed_keys[4];
	47
315127ff	48	static void
4b4cd312	49	cacheDigestInit(CacheDigest * cd, int capacity, int bpe)
bdbb6d04	50	{
315127ff	51	const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe);
	52	assert(cd);
	53	assert(capacity > 0 && bpe > 0);
	54	assert(mask_size > 0);
	55	cd->capacity = capacity;
	56	cd->bits_per_entry = bpe;
	57	cd->mask_size = mask_size;
	58	cd->mask = xcalloc(cd->mask_size, 1);
99edd1c3	59	debug(70, 2) ("cacheDigestInit: capacity: %d entries, bpe: %d; size: %d bytes\n",
315127ff	60	cd->capacity, cd->bits_per_entry, cd->mask_size);
56a1c446	61	}
56a1c446	62
56a1c446	63	CacheDigest *
315127ff	64	cacheDigestCreate(int capacity, int bpe)
56a1c446	65	{
56a1c446	66	CacheDigest *cd = memAllocate(MEM_CACHE_DIGEST);
4b4cd312	67	assert(MD5_DIGEST_CHARS == 16); /* our hash functions rely on 16 byte keys */
315127ff	68	cacheDigestInit(cd, capacity, bpe);
bdbb6d04	69	return cd;
	70	}
	71
315127ff	72	static void
	73	cacheDigestClean(CacheDigest * cd)
	74	{
	75	assert(cd);
	76	xfree(cd->mask);
	77	cd->mask = NULL;
	78	}
	79
bdbb6d04	80	void
1afe05c5	81	cacheDigestDestroy(CacheDigest * cd)
bdbb6d04	82	{
bdbb6d04	83	assert(cd);
315127ff	84	cacheDigestClean(cd);
315127ff	85	memFree(MEM_CACHE_DIGEST, cd);
bdbb6d04	86	}
bdbb6d04	87
6d80b36f	88	CacheDigest *
	89	cacheDigestClone(const CacheDigest * cd)
	90	{
	91	CacheDigest *clone;
	92	assert(cd);
315127ff	93	clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry);
c2186446	94	clone->count = cd->count;
315127ff	95	clone->del_count = cd->del_count;
315127ff	96	assert(cd->mask_size == clone->mask_size);
6d80b36f	97	xmemcpy(clone->mask, cd->mask, cd->mask_size);
	98	return clone;
	99	}
	100
12784378	101	void
	102	cacheDigestClear(CacheDigest * cd)
	103	{
	104	assert(cd);
	105	cd->count = cd->del_count = 0;
	106	memset(cd->mask, 0, cd->mask_size);
	107	}
	108
315127ff	109	/* changes mask size, resets bits to 0, preserves "cd" pointer */
304b267e	110	void
	111	cacheDigestChangeCap(CacheDigest * cd, int new_cap)
	112	{
	113	assert(cd);
315127ff	114	cacheDigestClean(cd);
315127ff	115	cacheDigestInit(cd, new_cap, cd->bits_per_entry);
304b267e	116	}
304b267e	117
bdbb6d04	118	/* returns true if the key belongs to the digest */
bdbb6d04	119	int
1afe05c5	120	cacheDigestTest(const CacheDigest * cd, const cache_key * key)
bdbb6d04	121	{
	122	assert(cd && key);
	123	/* hash */
56a1c446	124	cacheDigestHashKey(cd, key);
bdbb6d04	125	/* test corresponding bits */
1afe05c5	126	return
bdbb6d04	127	CBIT_TEST(cd->mask, hashed_keys[0]) &&
	128	CBIT_TEST(cd->mask, hashed_keys[1]) &&
	129	CBIT_TEST(cd->mask, hashed_keys[2]) &&
	130	CBIT_TEST(cd->mask, hashed_keys[3]);
	131	}
	132
c2186446	133	void
	134	cacheDigestAdd(CacheDigest * cd, const cache_key * key)
	135	{
	136	assert(cd && key);
	137	/* hash */
56a1c446	138	cacheDigestHashKey(cd, key);
c2186446	139	/* turn on corresponding bits */
c135694e	140	#if CD_FAST_ADD
c2186446	141	CBIT_SET(cd->mask, hashed_keys[0]);
	142	CBIT_SET(cd->mask, hashed_keys[1]);
	143	CBIT_SET(cd->mask, hashed_keys[2]);
	144	CBIT_SET(cd->mask, hashed_keys[3]);
c135694e	145	#else
	146	{
	147	int on_xition_cnt = 0;
	148	if (!CBIT_TEST(cd->mask, hashed_keys[0])) {
	149	CBIT_SET(cd->mask, hashed_keys[0]);
	150	on_xition_cnt++;
	151	}
	152	if (!CBIT_TEST(cd->mask, hashed_keys[1])) {
	153	CBIT_SET(cd->mask, hashed_keys[1]);
	154	on_xition_cnt++;
	155	}
	156	if (!CBIT_TEST(cd->mask, hashed_keys[2])) {
	157	CBIT_SET(cd->mask, hashed_keys[2]);
	158	on_xition_cnt++;
	159	}
	160	if (!CBIT_TEST(cd->mask, hashed_keys[3])) {
	161	CBIT_SET(cd->mask, hashed_keys[3]);
	162	on_xition_cnt++;
	163	}
	164	statHistCount(&Counter.cd.on_xition_count, on_xition_cnt);
	165	}
	166	#endif
c2186446	167	cd->count++;
	168	}
	169
bdbb6d04	170	void
1afe05c5	171	cacheDigestDel(CacheDigest * cd, const cache_key * key)
bdbb6d04	172	{
	173	assert(cd && key);
	174	cd->del_count++;
	175	/* we do not support deletions from the digest */
	176	}
	177
c2186446	178	/* returns mask utilization parameters */
12784378	179	static void
b644367b	180	cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
c2186446	181	{
c2186446	182	int on_count = 0;
56a1c446	183	int pos = cd->mask_size * 8;
12784378	184	int seq_len_sum = 0;
	185	int seq_count = 0;
	186	int cur_seq_len = 0;
	187	int cur_seq_type = 1;
	188	assert(stats);
	189	memset(stats, 0, sizeof(*stats));
c2186446	190	while (pos-- > 0) {
e998b523	191	const int is_on = 0 != CBIT_TEST(cd->mask, pos);
12784378	192	if (is_on)
c2186446	193	on_count++;
12784378	194	if (is_on != cur_seq_type \|\| !pos) {
	195	seq_len_sum += cur_seq_len;
	196	seq_count++;
e998b523	197	cur_seq_type = is_on;
12784378	198	cur_seq_len = 0;
	199	}
	200	cur_seq_len++;
c2186446	201	}
56a1c446	202	stats->bit_count = cd->mask_size * 8;
12784378	203	stats->bit_on_count = on_count;
	204	stats->bseq_len_sum = seq_len_sum;
	205	stats->bseq_count = seq_count;
c2186446	206	}
bdbb6d04	207
315127ff	208	int
	209	cacheDigestBitUtil(const CacheDigest * cd)
	210	{
	211	CacheDigestStats stats;
	212	assert(cd);
	213	cacheDigestStats(cd, &stats);
	214	return xpercentInt(stats.bit_on_count, stats.bit_count);
	215	}
	216
8638fc66	217	void
4b4cd312	218	cacheDigestGuessStatsUpdate(cd_guess_stats * stats, int real_hit, int guess_hit)
56a1c446	219	{
	220	assert(stats);
	221	if (real_hit) {
	222	if (guess_hit)
	223	stats->true_hits++;
	224	else
	225	stats->false_misses++;
	226	} else {
	227	if (guess_hit)
	228	stats->false_hits++;
	229	else
	230	stats->true_misses++;
	231	}
	232	}
	233
	234	void
4b4cd312	235	cacheDigestGuessStatsReport(const cd_guess_stats * stats, StoreEntry * sentry, const char *label)
56a1c446	236	{
	237	const int true_count = stats->true_hits + stats->true_misses;
	238	const int false_count = stats->false_hits + stats->false_misses;
	239	const int hit_count = stats->true_hits + stats->false_hits;
	240	const int miss_count = stats->true_misses + stats->false_misses;
	241	const int tot_count = true_count + false_count;
4b4cd312	242
56a1c446	243	assert(label);
4b4cd312	244	assert(tot_count == hit_count + miss_count); /* paranoid */
56a1c446	245
	246	storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label);
	247	storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n");
	248	storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n");
	249
	250	storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	251	stats->true_hits, xpercent(stats->true_hits, tot_count),
	252	stats->true_misses, xpercent(stats->true_misses, tot_count),
	253	true_count, xpercent(true_count, tot_count));
	254	storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	255	stats->false_hits, xpercent(stats->false_hits, tot_count),
	256	stats->false_misses, xpercent(stats->false_misses, tot_count),
	257	false_count, xpercent(false_count, tot_count));
	258	storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	259	hit_count, xpercent(hit_count, tot_count),
	260	miss_count, xpercent(miss_count, tot_count),
	261	tot_count, xpercent(tot_count, tot_count));
315127ff	262	storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
315127ff	263	stats->close_hits, xpercentInt(stats->close_hits, stats->false_hits));
56a1c446	264	}
	265
	266	void
4b4cd312	267	cacheDigestReport(CacheDigest * cd, const char label, StoreEntry e)
8638fc66	268	{
12784378	269	CacheDigestStats stats;
8638fc66	270	assert(cd && e);
12784378	271	cacheDigestStats(cd, &stats);
12784378	272	storeAppendPrintf(e, "%s digest: size: %d bytes\n",
b644367b	273	label ? label : "", stats.bit_count / 8
b644367b	274	);
8638fc66	275	storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n",
	276	cd->count,
	277	cd->capacity,
	278	xpercentInt(cd->count, cd->capacity)
b644367b	279	);
b644367b	280	storeAppendPrintf(e, "\t deletion attempts: %d\n",
8638fc66	281	cd->del_count
b644367b	282	);
315127ff	283	storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
315127ff	284	cd->bits_per_entry,
12784378	285	stats.bit_on_count, stats.bit_count,
12784378	286	xpercentInt(stats.bit_on_count, stats.bit_count)
b644367b	287	);
b644367b	288	storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
12784378	289	stats.bseq_count,
12784378	290	xdiv(stats.bseq_len_sum, stats.bseq_count)
b644367b	291	);
8638fc66	292	}
8638fc66	293
315127ff	294	size_t
315127ff	295	cacheDigestCalcMaskSize(int cap, int bpe)
304b267e	296	{
315127ff	297	return (size_t) (cap * bpe + 7) / 8;
304b267e	298	}
304b267e	299
e5834061	300	static void
5999b776	301	cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
e5834061	302	{
e5834061	303	const unsigned int bit_count = cd->mask_size * 8;
13c31e72	304	unsigned int tmp_keys[4];
	305	/* we must memcpy to ensure alignment */
	306	xmemcpy(tmp_keys, key, sizeof(tmp_keys));
e5834061	307	hashed_keys[0] = htonl(tmp_keys[0]) % bit_count;
	308	hashed_keys[1] = htonl(tmp_keys[1]) % bit_count;
	309	hashed_keys[2] = htonl(tmp_keys[2]) % bit_count;
	310	hashed_keys[3] = htonl(tmp_keys[3]) % bit_count;
	311	debug(70, 9) ("cacheDigestHashKey: %s -(%d)-> %d %d %d %d\n",
	312	storeKeyText(key), bit_count,
	313	hashed_keys[0], hashed_keys[1], hashed_keys[2], hashed_keys[3]);
	314	}