/*
 * $Id: filemap.c,v 1.31 1998/07/22 20:37:19 wessels Exp $
 *
 * DEBUG: section 8     Swap File Bitmap
 * AUTHOR: Harvest Derived
 *
 * 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.  Squid is Copyrighted (C) 1998 by
 *  Duane Wessels and the University of California San Diego.  Please
 *  see the COPYRIGHT file for full details.  Squid incorporates
 *  software developed and/or copyrighted by other sources.  Please see
 *  the CREDITS file for full details.
 *
 *  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"

/* Number of bits in a long */
#if SIZEOF_LONG == 8
#define LONG_BIT_SHIFT 6
#define BITS_IN_A_LONG 0x40
#define LONG_BIT_MASK  0x3F
#define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF
#elif SIZEOF_LONG == 4
#define LONG_BIT_SHIFT 5
#define BITS_IN_A_LONG 0x20
#define LONG_BIT_MASK  0x1F
#define ALL_ONES (unsigned long) 0xFFFFFFFF
#else
#define LONG_BIT_SHIFT 5
#define BITS_IN_A_LONG 0x20
#define LONG_BIT_MASK  0x1F
#define ALL_ONES (unsigned long) 0xFFFFFFFF
#endif

fileMap *
file_map_create(int n)
{
    fileMap *fm = xcalloc(1, sizeof(fileMap));
    fm->max_n_files = n;
    fm->nwords = n >> LONG_BIT_SHIFT;
    debug(8, 3) ("file_map_create: creating space for %d files\n", n);
    debug(8, 5) ("--> %d words of %d bytes each\n",
	fm->nwords, sizeof(unsigned long));
    fm->file_map = xcalloc(fm->nwords, sizeof(unsigned long));
    /* XXX account fm->file_map */
    return fm;
}

int
file_map_bit_set(fileMap * fm, int file_number)
{
    unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
    fm->file_map[file_number >> LONG_BIT_SHIFT] |= bitmask;
    fm->n_files_in_map++;
    if (!fm->toggle && (fm->n_files_in_map > ((fm->max_n_files * 7) >> 3))) {
	fm->toggle++;
	debug(8, 0) ("WARNING: filemap utilization at %d%%\n"
	    "\tConsider decreasing store_avg_object_size in squid.conf\n",
	    percent(fm->n_files_in_map, fm->max_n_files));
    } else if (fm->n_files_in_map == fm->max_n_files) {
	fatal_dump("You've run out of swap file numbers.");
    }
    return (file_number);
}

void
file_map_bit_reset(fileMap * fm, int file_number)
{
    unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
    fm->file_map[file_number >> LONG_BIT_SHIFT] &= ~bitmask;
    fm->n_files_in_map--;
}

int
file_map_bit_test(fileMap * fm, int file_number)
{
    unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
    /* be sure the return value is an int, not a u_long */
    return (fm->file_map[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0);
}

int
file_map_allocate(fileMap * fm, int suggestion)
{
    int word;
    int bit;
    int count;
    if (suggestion > fm->max_n_files)
	suggestion = 0;
    if (!file_map_bit_test(fm, suggestion)) {
	return file_map_bit_set(fm, suggestion);
    }
    word = suggestion >> LONG_BIT_SHIFT;
    for (count = 0; count < fm->nwords; count++) {
	if (fm->file_map[word] != ALL_ONES)
	    break;
	word = (word + 1) % fm->nwords;
    }
    for (bit = 0; bit < BITS_IN_A_LONG; bit++) {
	suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit;
	if (!file_map_bit_test(fm, suggestion)) {
	    return file_map_bit_set(fm, suggestion);
	}
    }
    fatal("file_map_allocate: Exceeded filemap limit");
    return 0;			/* NOTREACHED */
}

void
filemapFreeMemory(fileMap * fm)
{
    safe_free(fm->file_map);
    safe_free(fm);
}

void
filemapCopy(fileMap * old, fileMap * new)
{
    assert(old->max_n_files <= new->max_n_files);
    assert(0 == new->n_files_in_map);
    xmemcpy(new->file_map, old->file_map, old->nwords * sizeof(unsigned long));
    new->n_files_in_map = old->n_files_in_map;
}

#ifdef TEST

#define TEST_SIZE 1<<16
main(argc, argv)
{
    int i;

    fm = file_map_create(TEST_SIZE);

    for (i = 0; i < TEST_SIZE; ++i) {
	file_map_bit_set(i);
	assert(file_map_bit_test(i));
	file_map_bit_reset(i);
    }
}
#endif