[hcoop/debian/openafs.git] / src / ptserver / map.c

/*
 *	bit map routines (in-core).
 */
/*
 * Copyright (c) 1995, 1996, 2007 Marcus D. Watts  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. The name of the developer may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED ``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
 * MARCUS D. WATTS OR CONTRIBUTORS 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.
 */

#include <afsconfig.h>
#include <afs/param.h>

#include <roken.h>

#ifdef SUPERGROUPS
#include "map.h"

#undef PRINT_MAP_ERROR
/* #define MAP_DEBUG */
/* #define NEED_READ_WRITE */

#define LSHIFT 5
#define MSHIFT 8		/* XXX make this 8 in the production version... */
#define MDATA (1<<MSHIFT)
struct bitmap {
    struct bitmap *m_next;
    int m_page;
    int m_data[MDATA];
};

#define MAP(p)	((struct bitmap*)((intptr_t)(p)&~1))
#define NEGMAP(p)	(((intptr_t)(p))&1)
#define POSMAP(p)	(!NEGMAP(p))
#define NOT_MAP(mp)	((struct map *) (((intptr_t)(mp)) ^ 1))

#define NUMBERTOBIT(n)	((n) & ((1<<LSHIFT)-1))
#define NUMBERTOINDEX(n)	((n>>LSHIFT) & ((1<<MSHIFT)-1))
#define NUMBERTOPAGE(n)	((n>>(LSHIFT+MSHIFT)))
#define TONUMBER(p,x,b)	((b) + ((x)<<LSHIFT) + ((p)<<((LSHIFT+MSHIFT))))

#define Mflag	(debug_mask & (1L<<('Y'-'@')))
#define Aflag	(debug_mask & (1L<<('Z'-'@')))
extern int debug_mask;

int
in_map(struct map *parm, int node)
{
    struct bitmap *map;
    int bit;
    int x, page;
    int result;

#ifdef MAP_DEBUG
    if (Aflag) {
	printf("in_map: is %d in [", node);
	print_map(parm);
	printf(" ]");
    }
#endif
    bit = NUMBERTOBIT(node);
    x = NUMBERTOINDEX(node);
    page = NUMBERTOPAGE(node);
#ifdef MAP_DEBUG
    if (Aflag)
	if (TONUMBER(page, x, bit) != node) {
	    printf
		("bxp mixup: node=%d -> p=%d x=%d b=%d -> %d, %d, %d = %d\n",
		 node, page, x, bit, TONUMBER(page, 0, 0), TONUMBER(0, x, 0),
		 TONUMBER(0, 0, bit), TONUMBER(page, x, bit));
	}
#endif
    bit = 1L << bit;;

    for (map = MAP(parm); map; map = map->m_next)
	if (map->m_page == page)
	    return NEGMAP(parm) ^ (!!(map->m_data[x] & bit));
    result = !POSMAP(parm);
#ifdef MAP_DEBUG
    if (Aflag)
	printf(" -> %s\n", result ? "yes" : "no");
#endif
    return result;
}

void
free_map(struct map *parm)
{
    struct bitmap *map, *next;
#ifdef MAP_DEBUG
    if (Aflag) {
	printf("Freeing map");
	print_map(parm);
	printf("\n");
    }
#endif
    map = MAP(parm);
    while (map) {
	next = map->m_next;
	free(map);
	map = next;
    }
}

struct map *
add_map(struct map *parm, int node)
{
    struct bitmap *map;
    int bit;
    int x, page;

#ifdef MAP_DEBUG
    if (Aflag) {
	printf("add_map: adding %d to [", node);
	print_map(parm);
	printf(" ] ");
    }
#endif
    bit = NUMBERTOBIT(node);
    x = NUMBERTOINDEX(node);
    page = NUMBERTOPAGE(node);

    bit = 1L << bit;;

    for (map = MAP(parm); map; map = map->m_next)
	if (map->m_page == page)
	    break;
    if (!map) {
	map = malloc(sizeof *map);
	if (!map) {
#ifdef PRINT_MAP_ERROR
	    printf("No memory!\n");
#endif
	    free_map((struct map *)map);
	    return 0;
	}
	map->m_page = page;
	memset( map->m_data, 0, sizeof map->m_data);
	if (NEGMAP(parm)) {
	    int i;
	    for (i = 0; i < MDATA; ++i)
		map->m_data[i] = ~0;
	}
	map->m_next = MAP(parm);
	if (POSMAP(parm))
	    parm = (struct map *)map;
	else
	    parm = NOT_MAP(map);
    }
    if (POSMAP(parm))
	map->m_data[x] |= bit;
    else
	map->m_data[x] &= ~bit;
#ifdef MAP_DEBUG
    if (Aflag) {
	printf(" ->");
	print_map(parm);
	printf("\n");
    }
#endif
    return (struct map *)parm;
}

struct bitmap *
simplify_bitmap(struct bitmap *map)
{
    struct bitmap **mpp, *mp2;
    int i;
    for (mpp = &map; (mp2 = *mpp);) {
	for (i = 0; i < MDATA; ++i)
	    if (mp2->m_data[i])
		break;
	if (i == MDATA) {
#ifdef PRINT_MAP_ERROR
	    printf("simplify_bitmap: failed to eliminate zero page %d\n",
		   mp2->m_page);
#endif
	    *mpp = mp2->m_next;
	    free(mp2);
	} else
	    mpp = &mp2->m_next;
    }
    return map;
}

struct bitmap *
or_bitmap(struct bitmap *left, struct bitmap *right)
{
    struct bitmap **rightmp, *lmap, *rmap;
    int i;
    for (lmap = left; lmap; lmap = lmap->m_next) {
	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
	    if (rmap->m_page == lmap->m_page) {
		for (i = 0; i < MDATA; ++i)
		    lmap->m_data[i] |= rmap->m_data[i];
		*rightmp = rmap->m_next;
		free(rmap);
		break;
	    }
    }
    for (rightmp = &left; *rightmp; rightmp = &(*rightmp)->m_next)
	;
    *rightmp = right;
    return left;
}

struct bitmap *
and_bitmap(struct bitmap *left, struct bitmap *right)
{
    struct bitmap **rightmp, *lmap, *rmap, **leftmp;
    int i;
    int sig;
    for (leftmp = &left; (lmap = *leftmp);) {
	sig = 0;
	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
	    if (rmap->m_page == lmap->m_page) {
		for (i = 0; i < MDATA; ++i)
		    sig |= (lmap->m_data[i] &= rmap->m_data[i]);
		*rightmp = rmap->m_next;
		free(rmap);
		break;
	    }
	if (rmap && sig) {
	    leftmp = &lmap->m_next;
	} else {
	    *leftmp = lmap->m_next;
	    free(lmap);
	}
    }
    free_map((struct map *)right);
    return simplify_bitmap(left);
}

/* bit set in left, but not in right */
struct bitmap *
bic_bitmap(struct bitmap *left, struct bitmap *right)
{
    struct bitmap **rightmp, *lmap, *rmap, **leftmp;
    int i;
    int sig;
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("bic_bitmap: left=%#lx right=%#lx\n", (long)left, (long)right);
    }
#endif
    for (leftmp = &left; (lmap = *leftmp);) {
	sig = 0;
	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
	    if (rmap->m_page == lmap->m_page) {
		for (i = 0; i < MDATA; ++i)
		    sig |= (lmap->m_data[i] &= ~rmap->m_data[i]);
		*rightmp = rmap->m_next;
		free(rmap);
		break;
	    }
	if (!rmap || sig) {
	    leftmp = &lmap->m_next;
	} else {
	    *leftmp = lmap->m_next;
	    free(lmap);
	}
    }
    free_map((struct map *)right);
    left = simplify_bitmap(left);
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("bic_bitmap: result=%#lx\n", (long) left);
    }
#endif
    return left;
}

struct map *
and_map(struct map *mp1, struct map *mp2)
{
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("Anding maps");
	print_map(mp1);
	printf(" and");
	print_map(mp2);
    }
#endif
    if (POSMAP(mp1))
	if (POSMAP(mp2))
	    mp1 = (struct map *)and_bitmap((struct bitmap *) mp1,
		(struct bitmap *) mp2);
	else
	    mp1 = (struct map *)bic_bitmap((struct bitmap *) mp1, MAP(mp2));
    else if (POSMAP(mp2))
	mp1 = (struct map *)bic_bitmap((struct bitmap *) mp2, MAP(mp1));
    else
	mp1 = NOT_MAP(or_bitmap(MAP(mp1), MAP(mp2)));
#ifdef MAP_DEBUG
    if (Mflag) {
	printf(" ->");
	print_map(mp1);
	printf("\n");
    }
#endif
    return mp1;
}

struct map *
or_map(struct map *mp1, struct map *mp2)
{
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("Oring maps");
	print_map(mp1);
	printf(" and");
	print_map(mp2);
    }
#endif
    if (POSMAP(mp1))
	if (POSMAP(mp2))
	    mp1 = (struct map *)or_bitmap((struct bitmap *) mp1,
		(struct bitmap *) mp2);
	else
	    mp1 = NOT_MAP(bic_bitmap(MAP(mp2), (struct bitmap *) mp1));
    else if (POSMAP(mp2))
	mp1 = NOT_MAP(bic_bitmap(MAP(mp1), (struct bitmap *) mp2));
    else
	mp1 = NOT_MAP(and_bitmap(MAP(mp1), MAP(mp2)));
#ifdef MAP_DEBUG
    if (Mflag) {
	printf(" ->");
	print_map(mp1);
	printf("\n");
    }
#endif
    return mp1;
}

struct map *
not_map(struct map *map)
{
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("Notting map");
	print_map(map);
	printf("\n");
    }
#endif
    return NOT_MAP(map);
}

struct map *
copy_map(struct map *parm)
{
    struct bitmap *result, **mpp, *map;
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("copymap:");
	print_map(parm);
	printf("\n");
    }
#endif
    map = MAP(parm);
    for (mpp = &result; (*mpp = 0), map; map = map->m_next) {
	*mpp = malloc(sizeof **mpp);
	if (!*mpp) {
#ifdef MAP_DEBUG
	    if (Mflag)
		printf("copy_map: out of memory\n");
#endif
	    free_map((struct map *)result);
	    result = 0;
	    break;
	}
	**mpp = *map;
	mpp = &(*mpp)->m_next;
    }
    if (NEGMAP(parm))
	return NOT_MAP(result);
    else
	return (struct map *)result;
}

int
count_map(struct map *parm)
{
    int nf;
    struct bitmap *map;
    int i, j;

    nf = 0;
    for (map = MAP(parm); map; map = map->m_next) {
	for (i = 0; i < MDATA; ++i) {
	    if (!map->m_data[i])
		;
	    else if (!~map->m_data[i])
		nf += (1 << LSHIFT);
	    else
		for (j = 0; j < (1L << LSHIFT); ++j)
		    if (map->m_data[i] & (1L << j))
			++nf;
	}
    }
    if (NEGMAP(parm))
	nf = ~nf;		/* note 1's complement */
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("countmap:");
	print_map(parm);
	printf(" -> %d\n", nf);
    }
#endif
    return nf;
}

int
next_map(struct map *parm, int node)
{
    struct bitmap *map, *lowest;
    int bit, mask;
    int x, page;
    int best;
    int i;
    int bn;

#ifdef MAP_DEBUG
    if (Aflag) {
	printf("next_map: selecting next after %d from", node);
	print_map(parm);
    }
#endif
    if (NEGMAP(parm)) {
#ifdef MAP_DEBUG
	if (Aflag)
	    printf("next_map failed; negative map\n");
#endif
	return -1;
    }

    ++node;
    bit = NUMBERTOBIT(node);
    x = NUMBERTOINDEX(node);
    page = NUMBERTOPAGE(node);
    bit = 1L << bit;
    best = -1;
    lowest = 0;
    for (map = MAP(parm); map; map = map->m_next)
	if (map->m_page >= page && (!lowest || lowest->m_page > map->m_page)) {
	    i = 0;
	    mask = ~0;
	    if (page == map->m_page)
		i = x, mask = -bit;
	    for (; i < MDATA; ++i, mask = ~0)
		if (map->m_data[i] & mask)
		    break;
	    if (i < MDATA) {
		for (bn = 0; bn < (1 << LSHIFT); ++bn)
		    if (map->m_data[i] & mask & (1L << bn)) {
			break;
		    }
#ifdef MAP_DEBUG
		if (Aflag) {
		    if (bn == (1 << LSHIFT)) {
			printf
			    ("next_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
			     map->m_page, i, map->m_data[i], mask, x, bit);
			continue;
		    }
		}
#endif
		best = bn + ((i + ((map->m_page) << MSHIFT)
			     ) << LSHIFT);
		lowest = map;
	    }
	}
#ifdef MAP_DEBUG
    if (Aflag) {
	printf(" -> %d\n", best);
	if (best >= 0 && !in_map(parm, best)) {
	    printf("next_map: botch; %d not in map\n", best);
	    return -1;
	}
    }
#endif
    return best;
}

int
first_map(struct map *parm)
{
    return next_map(parm, -9999);
}

int
prev_map(struct map *parm, int node)
{
    struct bitmap *map, *lowest;
    int bit, mask;
    int x, page;
    int best;
    int i;
    int bn;

#ifdef MAP_DEBUG
    if (Aflag) {
	printf("prev_map: selecting previous before %d from", node);
	print_map(parm);
    }
#endif
    if (NEGMAP(parm)) {
#ifdef MAP_DEBUG
	if (Aflag)
	    printf("prev_map failed; negative map\n");
#endif
	return -1;
    }

    if (node < 0)
	node = ((unsigned int)~0) >> 1;

    --node;
    bit = NUMBERTOBIT(node);
    x = NUMBERTOINDEX(node);
    page = NUMBERTOPAGE(node);
    bit = 1L << bit;
    best = -1;
    lowest = 0;
    for (map = MAP(parm); map; map = map->m_next)
	if (map->m_page <= page && (!lowest || lowest->m_page < map->m_page)) {
	    i = MDATA - 1;
	    mask = ~0;
	    if (page == map->m_page)
		i = x, mask = (bit << 1) - 1;
	    for (; i >= 0; --i, mask = ~0)
		if (map->m_data[i] & mask)
		    break;
	    if (i >= 0) {
		for (bn = (1 << LSHIFT) - 1; bn >= 0; --bn)
		    if (map->m_data[i] & mask & (1L << bn)) {
			break;
		    }
#ifdef MAP_DEBUG
		if (Aflag) {
		    if (bn < 0) {
			printf
			    ("prev_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
			     map->m_page, i, map->m_data[i], mask, x, bit);
			continue;
		    }
		}
#endif
		best = bn + ((i + ((map->m_page) << MSHIFT)
			     ) << LSHIFT);
		lowest = map;
	    }
	}
#ifdef MAP_DEBUG
    if (Aflag) {
	printf(" -> %d\n", best);
	if (best >= 0 && !in_map(parm, best)) {
	    printf("prev_map: botch; %d not in map\n", best);
	    return -1;
	}
    }
#endif
    return best;
}

int
last_map(struct map *parm)
{
    return prev_map(parm, 0x7fffffff);
}

struct map *
negative_map(struct map *map)
{
    return (struct map *)NEGMAP(map);
}

struct map *
bic_map(struct map *mp1, struct map *mp2)
{
#ifdef MAP_DEBUG
    if (Mflag) {
	printf("Bic maps");
	print_map(mp1);
	printf(" minus");
	print_map(mp2);
    }
#endif
    mp1 = and_map(mp1, NOT_MAP(mp2));
#ifdef MAP_DEBUG
    if (Mflag) {
	printf(" ->");
	print_map(mp1);
	printf("\n");
    }
#endif
    return mp1;
}

#ifdef PRINT_MAP_ERROR
void
print_map(struct map *parm)
{
    struct bitmap *map;
    int i, j;
    int bitno, firstbitno, lastbitno;
    if (NEGMAP(parm)) {
	printf(" NOT");
    }
    map = MAP(parm);
    if (!map)
	printf(" nil(%lx)", (long)parm);
    else
	printf(" %lx", (long)parm);
    lastbitno = -100;
    firstbitno = -100;
    for (; map; map = map->m_next)
	for (i = 0; i < MDATA; ++i)
	    if (map->m_data[i])
		for (j = 0; j < (1 << LSHIFT); ++j) {
		    bitno =
			j + (i << LSHIFT) +
			((map->m_page) << (LSHIFT + MSHIFT));
		    if (map->m_data[i] & (1 << j)) {
			if (bitno == lastbitno + 1) {
			    ++lastbitno;
			    continue;
			}
			if (bitno != (lastbitno + 1)) {
			    if (firstbitno >= 0 && firstbitno != lastbitno)
				printf("-%d", lastbitno);
			    firstbitno = -100;
			}
			printf(" %d", bitno);
			firstbitno = lastbitno = bitno;
		    } else {
			if (firstbitno >= 0 && firstbitno != lastbitno)
			    printf("-%d", lastbitno);
			firstbitno = -100;
		    }
		}
    if (firstbitno >= 0 && firstbitno != lastbitno)
	printf("-%d", lastbitno);
}
#endif

#ifdef NEED_READ_WRITE
struct map *
read_map(int (*f) (void *), char *arg)
{
    struct bitmap *map, *result, **mp;
    int page;
    int bitno, lastno;
    int data;

/* count, then startbitno, then bits. */
    lastno = ((*f) (arg));
    if (lastno == -1)
	return 0;
    if (lastno & ((1 << LSHIFT) - 1)) {
#ifdef PRINT_MAP_ERROR
	printf("read_map: bad count\n");
#endif
	return 0;
    }
    bitno = ((*f) (arg));
    if (bitno & ((1 << LSHIFT) - 1)) {
#ifdef PRINT_MAP_ERROR
	printf("read_map: bad start\n");
#endif
	return 0;
    }
    lastno += bitno;
    map = result = 0;
    for (; bitno < lastno; bitno += (1 << LSHIFT)) {
	data = (*f) (arg);
	if (!data)
	    continue;
	page = NUMBERTOPAGE(bitno);
	if (!map || map->m_page != page)
	    for (mp = &result; (map = *mp); mp = &map->m_next)
		if (map->m_page == page)
		    break;
	if (!map) {
	    map = malloc(sizeof *map);
	    if (!map) {
#ifdef PRINT_MAP_ERROR
		printf("No memory!\n");
#endif
		if (result)
		    free_map((struct map *)result);
		return 0;
	    }
	    memset( map->m_data, 0, sizeof map->m_data);
	    map->m_page = page;
	    map->m_next = 0;
	    *mp = map;
	}
	map->m_data[NUMBERTOINDEX(bitno)] = data;
    }
    return (struct map *)result;
}

int
write_map(struct map *parm, int (*f) (void *, int), char *arg)
{
    struct bitmap *map;
    int page;
    int bitno, lastno, thisno, prevno;
    int i, j;

    bitno = first_map(parm);
    bitno &= ~((1 << LSHIFT) - 1);

    lastno = last_map(parm);
    lastno -= bitno;
    lastno += ((1 << LSHIFT));
    lastno &= ~((1 << LSHIFT) - 1);
/* count, then startbitno, then bits. */
    if ((*f) (arg, lastno) == -1)
	return -1;
    /* word: number of bits */
    if ((*f) (arg, bitno) == -1)
	return -1;
    lastno += bitno;
    prevno = bitno;
    for (bitno = first_map(parm); bitno >= 0; bitno = next_map(parm, bitno)) {
	page = NUMBERTOPAGE(bitno);
	for (map = MAP(parm); map; map = map->m_next)
	    if (map->m_page == page)
		break;
	if (!map) {
#ifdef PRINT_MAP_ERROR
	    printf("write_map: botch #1: can't find page %d\n", page);
#endif
	    continue;
	}
	for (i = 0; i < MDATA; ++i) {
	    if (!map->m_data[i])
		continue;
	    thisno = TONUMBER(page, i, 0);
	    for (j = thisno - prevno; j > 0; j -= (1 << LSHIFT))
		if ((*f) (arg, 0) == -1)
		    return -1;
	    prevno = thisno;
	    for (;;) {
		if ((*f) (arg, map->m_data[i]) == -1)
		    return -1;
		prevno += (1 << LSHIFT);
		++i;
		if (i >= MDATA || !map->m_data[i])
		    break;
	    }
	    --i;
	}
	bitno = TONUMBER(page, i, 0) - 1;
    }
#ifdef PRINT_MAP_ERROR
    if (prevno != lastno)
	printf("write_map: botch #2: bitno=%d prevno=%d lastno=%d\n", bitno,
	       prevno, lastno);
#endif
    return 0;
}
#endif

#endif
Commit	Line	Data
805e021f CE	1	/*
	2	* bit map routines (in-core).
	3	*/
	4	/*
	5	* Copyright (c) 1995, 1996, 2007 Marcus D. Watts All rights reserved.
	6	*
	7	* Redistribution and use in source and binary forms, with or without
	8	* modification, are permitted provided that the following conditions
	9	* are met:
	10	* 1. Redistributions of source code must retain the above copyright
	11	* notice, this list of conditions and the following disclaimer.
	12	* 2. Redistributions in binary form must reproduce the above copyright
	13	* notice, this list of conditions and the following disclaimer in the
	14	* documentation and/or other materials provided with the distribution.
	15	* 3. The name of the developer may not be used to endorse or promote
	16	* products derived from this software without specific prior written
	17	* permission.
	18	*
	19	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
	20	* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
	21	* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
	22	* MARCUS D. WATTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	23	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
	24	* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
	25	* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
	26	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
	27	* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
	28	* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	29	*/
	30
	31	#include <afsconfig.h>
	32	#include <afs/param.h>
	33
	34	#include <roken.h>
	35
	36	#ifdef SUPERGROUPS
	37	#include "map.h"
	38
	39	#undef PRINT_MAP_ERROR
	40	/* #define MAP_DEBUG */
	41	/* #define NEED_READ_WRITE */
	42
	43	#define LSHIFT 5
	44	#define MSHIFT 8 /* XXX make this 8 in the production version... */
	45	#define MDATA (1<<MSHIFT)
	46	struct bitmap {
	47	struct bitmap *m_next;
	48	int m_page;
	49	int m_data[MDATA];
	50	};
	51
	52	#define MAP(p) ((struct bitmap*)((intptr_t)(p)&~1))
	53	#define NEGMAP(p) (((intptr_t)(p))&1)
	54	#define POSMAP(p) (!NEGMAP(p))
	55	#define NOT_MAP(mp) ((struct map *) (((intptr_t)(mp)) ^ 1))
	56
	57	#define NUMBERTOBIT(n) ((n) & ((1<<LSHIFT)-1))
	58	#define NUMBERTOINDEX(n) ((n>>LSHIFT) & ((1<<MSHIFT)-1))
	59	#define NUMBERTOPAGE(n) ((n>>(LSHIFT+MSHIFT)))
	60	#define TONUMBER(p,x,b) ((b) + ((x)<<LSHIFT) + ((p)<<((LSHIFT+MSHIFT))))
	61
	62	#define Mflag (debug_mask & (1L<<('Y'-'@')))
	63	#define Aflag (debug_mask & (1L<<('Z'-'@')))
	64	extern int debug_mask;
65
66	int
67	in_map(struct map *parm, int node)
68	{
69	struct bitmap *map;
70	int bit;
71	int x, page;
72	int result;
73
74	#ifdef MAP_DEBUG
75	if (Aflag) {
76	printf("in_map: is %d in [", node);
77	print_map(parm);
78	printf(" ]");
79	}
80	#endif
81	bit = NUMBERTOBIT(node);
82	x = NUMBERTOINDEX(node);
83	page = NUMBERTOPAGE(node);
84	#ifdef MAP_DEBUG
85	if (Aflag)
86	if (TONUMBER(page, x, bit) != node) {
87	printf
88	("bxp mixup: node=%d -> p=%d x=%d b=%d -> %d, %d, %d = %d\n",
89	node, page, x, bit, TONUMBER(page, 0, 0), TONUMBER(0, x, 0),
90	TONUMBER(0, 0, bit), TONUMBER(page, x, bit));
91	}
92	#endif
93	bit = 1L << bit;;
94
95	for (map = MAP(parm); map; map = map->m_next)
96	if (map->m_page == page)
97	return NEGMAP(parm) ^ (!!(map->m_data[x] & bit));
98	result = !POSMAP(parm);
99	#ifdef MAP_DEBUG
100	if (Aflag)
101	printf(" -> %s\n", result ? "yes" : "no");
102	#endif
103	return result;
104	}
105
106	void
107	free_map(struct map *parm)
108	{
109	struct bitmap map, next;
110	#ifdef MAP_DEBUG
111	if (Aflag) {
112	printf("Freeing map");
113	print_map(parm);
114	printf("\n");
115	}
116	#endif
117	map = MAP(parm);
118	while (map) {
119	next = map->m_next;
120	free(map);
121	map = next;
122	}
123	}
124
125	struct map *
126	add_map(struct map *parm, int node)
127	{
128	struct bitmap *map;
129	int bit;
130	int x, page;
131
132	#ifdef MAP_DEBUG
133	if (Aflag) {
134	printf("add_map: adding %d to [", node);
135	print_map(parm);
136	printf(" ] ");
137	}
138	#endif
139	bit = NUMBERTOBIT(node);
140	x = NUMBERTOINDEX(node);
141	page = NUMBERTOPAGE(node);
142
143	bit = 1L << bit;;
144
145	for (map = MAP(parm); map; map = map->m_next)
146	if (map->m_page == page)
147	break;
148	if (!map) {
149	map = malloc(sizeof *map);
150	if (!map) {
151	#ifdef PRINT_MAP_ERROR
152	printf("No memory!\n");
153	#endif
154	free_map((struct map *)map);
155	return 0;
156	}
157	map->m_page = page;
158	memset( map->m_data, 0, sizeof map->m_data);
159	if (NEGMAP(parm)) {
160	int i;
161	for (i = 0; i < MDATA; ++i)
162	map->m_data[i] = ~0;
163	}
164	map->m_next = MAP(parm);
165	if (POSMAP(parm))
166	parm = (struct map *)map;
167	else
168	parm = NOT_MAP(map);
169	}
170	if (POSMAP(parm))
171	map->m_data[x] \|= bit;
172	else
173	map->m_data[x] &= ~bit;
174	#ifdef MAP_DEBUG
175	if (Aflag) {
176	printf(" ->");
177	print_map(parm);
178	printf("\n");
179	}
180	#endif
181	return (struct map *)parm;
182	}
183
184	struct bitmap *
185	simplify_bitmap(struct bitmap *map)
186	{
187	struct bitmap *mpp, mp2;
188	int i;
189	for (mpp = &map; (mp2 = *mpp);) {
190	for (i = 0; i < MDATA; ++i)
191	if (mp2->m_data[i])
192	break;
193	if (i == MDATA) {
194	#ifdef PRINT_MAP_ERROR
195	printf("simplify_bitmap: failed to eliminate zero page %d\n",
196	mp2->m_page);
197	#endif
198	*mpp = mp2->m_next;
199	free(mp2);
200	} else
201	mpp = &mp2->m_next;
202	}
203	return map;
204	}
205
206	struct bitmap *
207	or_bitmap(struct bitmap left, struct bitmap right)
208	{
209	struct bitmap *rightmp, lmap, *rmap;
210	int i;
211	for (lmap = left; lmap; lmap = lmap->m_next) {
212	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
213	if (rmap->m_page == lmap->m_page) {
214	for (i = 0; i < MDATA; ++i)
215	lmap->m_data[i] \|= rmap->m_data[i];
216	*rightmp = rmap->m_next;
217	free(rmap);
218	break;
219	}
220	}
221	for (rightmp = &left; rightmp; rightmp = &(rightmp)->m_next)
222	;
223	*rightmp = right;
224	return left;
225	}
226
227	struct bitmap *
228	and_bitmap(struct bitmap left, struct bitmap right)
229	{
230	struct bitmap *rightmp, lmap, rmap, *leftmp;
231	int i;
232	int sig;
233	for (leftmp = &left; (lmap = *leftmp);) {
234	sig = 0;
235	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
236	if (rmap->m_page == lmap->m_page) {
237	for (i = 0; i < MDATA; ++i)
238	sig \|= (lmap->m_data[i] &= rmap->m_data[i]);
239	*rightmp = rmap->m_next;
240	free(rmap);
241	break;
242	}
243	if (rmap && sig) {
244	leftmp = &lmap->m_next;
245	} else {
246	*leftmp = lmap->m_next;
247	free(lmap);
248	}
249	}
250	free_map((struct map *)right);
251	return simplify_bitmap(left);
252	}
253
254	/* bit set in left, but not in right */
255	struct bitmap *
256	bic_bitmap(struct bitmap left, struct bitmap right)
257	{
258	struct bitmap *rightmp, lmap, rmap, *leftmp;
259	int i;
260	int sig;
261	#ifdef MAP_DEBUG
262	if (Mflag) {
263	printf("bic_bitmap: left=%#lx right=%#lx\n", (long)left, (long)right);
264	}
265	#endif
266	for (leftmp = &left; (lmap = *leftmp);) {
267	sig = 0;
268	for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
269	if (rmap->m_page == lmap->m_page) {
270	for (i = 0; i < MDATA; ++i)
271	sig \|= (lmap->m_data[i] &= ~rmap->m_data[i]);
272	*rightmp = rmap->m_next;
273	free(rmap);
274	break;
275	}
276	if (!rmap \|\| sig) {
277	leftmp = &lmap->m_next;
278	} else {
279	*leftmp = lmap->m_next;
280	free(lmap);
281	}
282	}
283	free_map((struct map *)right);
284	left = simplify_bitmap(left);
285	#ifdef MAP_DEBUG
286	if (Mflag) {
287	printf("bic_bitmap: result=%#lx\n", (long) left);
288	}
289	#endif
290	return left;
291	}
292
293	struct map *
294	and_map(struct map mp1, struct map mp2)
295	{
296	#ifdef MAP_DEBUG
297	if (Mflag) {
298	printf("Anding maps");
299	print_map(mp1);
300	printf(" and");
301	print_map(mp2);
302	}
303	#endif
304	if (POSMAP(mp1))
305	if (POSMAP(mp2))
306	mp1 = (struct map )and_bitmap((struct bitmap ) mp1,
307	(struct bitmap *) mp2);
308	else
309	mp1 = (struct map )bic_bitmap((struct bitmap ) mp1, MAP(mp2));
310	else if (POSMAP(mp2))
311	mp1 = (struct map )bic_bitmap((struct bitmap ) mp2, MAP(mp1));
312	else
313	mp1 = NOT_MAP(or_bitmap(MAP(mp1), MAP(mp2)));
314	#ifdef MAP_DEBUG
315	if (Mflag) {
316	printf(" ->");
317	print_map(mp1);
318	printf("\n");
319	}
320	#endif
321	return mp1;
322	}
323
324	struct map *
325	or_map(struct map mp1, struct map mp2)
326	{
327	#ifdef MAP_DEBUG
328	if (Mflag) {
329	printf("Oring maps");
330	print_map(mp1);
331	printf(" and");
332	print_map(mp2);
333	}
334	#endif
335	if (POSMAP(mp1))
336	if (POSMAP(mp2))
337	mp1 = (struct map )or_bitmap((struct bitmap ) mp1,
338	(struct bitmap *) mp2);
339	else
340	mp1 = NOT_MAP(bic_bitmap(MAP(mp2), (struct bitmap *) mp1));
341	else if (POSMAP(mp2))
342	mp1 = NOT_MAP(bic_bitmap(MAP(mp1), (struct bitmap *) mp2));
343	else
344	mp1 = NOT_MAP(and_bitmap(MAP(mp1), MAP(mp2)));
345	#ifdef MAP_DEBUG
346	if (Mflag) {
347	printf(" ->");
348	print_map(mp1);
349	printf("\n");
350	}
351	#endif
352	return mp1;
353	}
354
355	struct map *
356	not_map(struct map *map)
357	{
358	#ifdef MAP_DEBUG
359	if (Mflag) {
360	printf("Notting map");
361	print_map(map);
362	printf("\n");
363	}
364	#endif
365	return NOT_MAP(map);
366	}
367
368	struct map *
369	copy_map(struct map *parm)
370	{
371	struct bitmap result, mpp, map;
372	#ifdef MAP_DEBUG
373	if (Mflag) {
374	printf("copymap:");
375	print_map(parm);
376	printf("\n");
377	}
378	#endif
379	map = MAP(parm);
380	for (mpp = &result; (*mpp = 0), map; map = map->m_next) {
381	mpp = malloc(sizeof *mpp);
382	if (!*mpp) {
383	#ifdef MAP_DEBUG
384	if (Mflag)
385	printf("copy_map: out of memory\n");
386	#endif
387	free_map((struct map *)result);
388	result = 0;
389	break;
390	}
391	*mpp = map;
392	mpp = &(*mpp)->m_next;
393	}
394	if (NEGMAP(parm))
395	return NOT_MAP(result);
396	else
397	return (struct map *)result;
398	}
399
400	int
401	count_map(struct map *parm)
402	{
403	int nf;
404	struct bitmap *map;
405	int i, j;
406
407	nf = 0;
408	for (map = MAP(parm); map; map = map->m_next) {
409	for (i = 0; i < MDATA; ++i) {
410	if (!map->m_data[i])
411	;
412	else if (!~map->m_data[i])
413	nf += (1 << LSHIFT);
414	else
415	for (j = 0; j < (1L << LSHIFT); ++j)
416	if (map->m_data[i] & (1L << j))
417	++nf;
418	}
419	}
420	if (NEGMAP(parm))
421	nf = ~nf; /* note 1's complement */
422	#ifdef MAP_DEBUG
423	if (Mflag) {
424	printf("countmap:");
425	print_map(parm);
426	printf(" -> %d\n", nf);
427	}
428	#endif
429	return nf;
430	}
431
432	int
433	next_map(struct map *parm, int node)
434	{
435	struct bitmap map, lowest;
436	int bit, mask;
437	int x, page;
438	int best;
439	int i;
440	int bn;
441
442	#ifdef MAP_DEBUG
443	if (Aflag) {
444	printf("next_map: selecting next after %d from", node);
445	print_map(parm);
446	}
447	#endif
448	if (NEGMAP(parm)) {
449	#ifdef MAP_DEBUG
450	if (Aflag)
451	printf("next_map failed; negative map\n");
452	#endif
453	return -1;
454	}
455
456	++node;
457	bit = NUMBERTOBIT(node);
458	x = NUMBERTOINDEX(node);
459	page = NUMBERTOPAGE(node);
460	bit = 1L << bit;
461	best = -1;
462	lowest = 0;
463	for (map = MAP(parm); map; map = map->m_next)
464	if (map->m_page >= page && (!lowest \|\| lowest->m_page > map->m_page)) {
465	i = 0;
466	mask = ~0;
467	if (page == map->m_page)
468	i = x, mask = -bit;
469	for (; i < MDATA; ++i, mask = ~0)
470	if (map->m_data[i] & mask)
471	break;
472	if (i < MDATA) {
473	for (bn = 0; bn < (1 << LSHIFT); ++bn)
474	if (map->m_data[i] & mask & (1L << bn)) {
475	break;
476	}
477	#ifdef MAP_DEBUG
478	if (Aflag) {
479	if (bn == (1 << LSHIFT)) {
480	printf
481	("next_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
482	map->m_page, i, map->m_data[i], mask, x, bit);
483	continue;
484	}
485	}
486	#endif
487	best = bn + ((i + ((map->m_page) << MSHIFT)
488	) << LSHIFT);
489	lowest = map;
490	}
491	}
492	#ifdef MAP_DEBUG
493	if (Aflag) {
494	printf(" -> %d\n", best);
495	if (best >= 0 && !in_map(parm, best)) {
496	printf("next_map: botch; %d not in map\n", best);
497	return -1;
498	}
499	}
500	#endif
501	return best;
502	}
503
504	int
505	first_map(struct map *parm)
506	{
507	return next_map(parm, -9999);
508	}
509
510	int
511	prev_map(struct map *parm, int node)
512	{
513	struct bitmap map, lowest;
514	int bit, mask;
515	int x, page;
516	int best;
517	int i;
518	int bn;
519
520	#ifdef MAP_DEBUG
521	if (Aflag) {
522	printf("prev_map: selecting previous before %d from", node);
523	print_map(parm);
524	}
525	#endif
526	if (NEGMAP(parm)) {
527	#ifdef MAP_DEBUG
528	if (Aflag)
529	printf("prev_map failed; negative map\n");
530	#endif
531	return -1;
532	}
533
534	if (node < 0)
535	node = ((unsigned int)~0) >> 1;
536
537	--node;
538	bit = NUMBERTOBIT(node);
539	x = NUMBERTOINDEX(node);
540	page = NUMBERTOPAGE(node);
541	bit = 1L << bit;
542	best = -1;
543	lowest = 0;
544	for (map = MAP(parm); map; map = map->m_next)
545	if (map->m_page <= page && (!lowest \|\| lowest->m_page < map->m_page)) {
546	i = MDATA - 1;
547	mask = ~0;
548	if (page == map->m_page)
549	i = x, mask = (bit << 1) - 1;
550	for (; i >= 0; --i, mask = ~0)
551	if (map->m_data[i] & mask)
552	break;
553	if (i >= 0) {
554	for (bn = (1 << LSHIFT) - 1; bn >= 0; --bn)
555	if (map->m_data[i] & mask & (1L << bn)) {
556	break;
557	}
558	#ifdef MAP_DEBUG
559	if (Aflag) {
560	if (bn < 0) {
561	printf
562	("prev_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
563	map->m_page, i, map->m_data[i], mask, x, bit);
564	continue;
565	}
566	}
567	#endif
568	best = bn + ((i + ((map->m_page) << MSHIFT)
569	) << LSHIFT);
570	lowest = map;
571	}
572	}
573	#ifdef MAP_DEBUG
574	if (Aflag) {
575	printf(" -> %d\n", best);
576	if (best >= 0 && !in_map(parm, best)) {
577	printf("prev_map: botch; %d not in map\n", best);
578	return -1;
579	}
580	}
581	#endif
582	return best;
583	}
584
585	int
586	last_map(struct map *parm)
587	{
588	return prev_map(parm, 0x7fffffff);
589	}
590
591	struct map *
592	negative_map(struct map *map)
593	{
594	return (struct map *)NEGMAP(map);
595	}
596
597	struct map *
598	bic_map(struct map mp1, struct map mp2)
599	{
600	#ifdef MAP_DEBUG
601	if (Mflag) {
602	printf("Bic maps");
603	print_map(mp1);
604	printf(" minus");
605	print_map(mp2);
606	}
607	#endif
608	mp1 = and_map(mp1, NOT_MAP(mp2));
609	#ifdef MAP_DEBUG
610	if (Mflag) {
611	printf(" ->");
612	print_map(mp1);
613	printf("\n");
614	}
615	#endif
616	return mp1;
617	}
618
619	#ifdef PRINT_MAP_ERROR
620	void
621	print_map(struct map *parm)
622	{
623	struct bitmap *map;
624	int i, j;
625	int bitno, firstbitno, lastbitno;
626	if (NEGMAP(parm)) {
627	printf(" NOT");
628	}
629	map = MAP(parm);
630	if (!map)
631	printf(" nil(%lx)", (long)parm);
632	else
633	printf(" %lx", (long)parm);
634	lastbitno = -100;
635	firstbitno = -100;
636	for (; map; map = map->m_next)
637	for (i = 0; i < MDATA; ++i)
638	if (map->m_data[i])
639	for (j = 0; j < (1 << LSHIFT); ++j) {
640	bitno =
641	j + (i << LSHIFT) +
642	((map->m_page) << (LSHIFT + MSHIFT));
643	if (map->m_data[i] & (1 << j)) {
644	if (bitno == lastbitno + 1) {
645	++lastbitno;
646	continue;
647	}
648	if (bitno != (lastbitno + 1)) {
649	if (firstbitno >= 0 && firstbitno != lastbitno)
650	printf("-%d", lastbitno);
651	firstbitno = -100;
652	}
653	printf(" %d", bitno);
654	firstbitno = lastbitno = bitno;
655	} else {
656	if (firstbitno >= 0 && firstbitno != lastbitno)
657	printf("-%d", lastbitno);
658	firstbitno = -100;
659	}
660	}
661	if (firstbitno >= 0 && firstbitno != lastbitno)
662	printf("-%d", lastbitno);
663	}
664	#endif
665
666	#ifdef NEED_READ_WRITE
667	struct map *
668	read_map(int (f) (void ), char *arg)
669	{
670	struct bitmap map, result, **mp;
671	int page;
672	int bitno, lastno;
673	int data;
674
675	/* count, then startbitno, then bits. */
676	lastno = ((*f) (arg));
677	if (lastno == -1)
678	return 0;
679	if (lastno & ((1 << LSHIFT) - 1)) {
680	#ifdef PRINT_MAP_ERROR
681	printf("read_map: bad count\n");
682	#endif
683	return 0;
684	}
685	bitno = ((*f) (arg));
686	if (bitno & ((1 << LSHIFT) - 1)) {
687	#ifdef PRINT_MAP_ERROR
688	printf("read_map: bad start\n");
689	#endif
690	return 0;
691	}
692	lastno += bitno;
693	map = result = 0;
694	for (; bitno < lastno; bitno += (1 << LSHIFT)) {
695	data = (*f) (arg);
696	if (!data)
697	continue;
698	page = NUMBERTOPAGE(bitno);
699	if (!map \|\| map->m_page != page)
700	for (mp = &result; (map = *mp); mp = &map->m_next)
701	if (map->m_page == page)
702	break;
703	if (!map) {
704	map = malloc(sizeof *map);
705	if (!map) {
706	#ifdef PRINT_MAP_ERROR
707	printf("No memory!\n");
708	#endif
709	if (result)
710	free_map((struct map *)result);
711	return 0;
712	}
713	memset( map->m_data, 0, sizeof map->m_data);
714	map->m_page = page;
715	map->m_next = 0;
716	*mp = map;
717	}
718	map->m_data[NUMBERTOINDEX(bitno)] = data;
719	}
720	return (struct map *)result;
721	}
722
723	int
724	write_map(struct map parm, int (f) (void , int), char arg)
725	{
726	struct bitmap *map;
727	int page;
728	int bitno, lastno, thisno, prevno;
729	int i, j;
730
731	bitno = first_map(parm);
732	bitno &= ~((1 << LSHIFT) - 1);
733
734	lastno = last_map(parm);
735	lastno -= bitno;
736	lastno += ((1 << LSHIFT));
737	lastno &= ~((1 << LSHIFT) - 1);
738	/* count, then startbitno, then bits. */
739	if ((*f) (arg, lastno) == -1)
740	return -1;
741	/* word: number of bits */
742	if ((*f) (arg, bitno) == -1)
743	return -1;
744	lastno += bitno;
745	prevno = bitno;
746	for (bitno = first_map(parm); bitno >= 0; bitno = next_map(parm, bitno)) {
747	page = NUMBERTOPAGE(bitno);
748	for (map = MAP(parm); map; map = map->m_next)
749	if (map->m_page == page)
750	break;
751	if (!map) {
752	#ifdef PRINT_MAP_ERROR
753	printf("write_map: botch #1: can't find page %d\n", page);
754	#endif
755	continue;
756	}
757	for (i = 0; i < MDATA; ++i) {
758	if (!map->m_data[i])
759	continue;
760	thisno = TONUMBER(page, i, 0);
761	for (j = thisno - prevno; j > 0; j -= (1 << LSHIFT))
762	if ((*f) (arg, 0) == -1)
763	return -1;
764	prevno = thisno;
765	for (;;) {
766	if ((*f) (arg, map->m_data[i]) == -1)
767	return -1;
768	prevno += (1 << LSHIFT);
769	++i;
770	if (i >= MDATA \|\| !map->m_data[i])
771	break;
772	}
773	--i;
774	}
775	bitno = TONUMBER(page, i, 0) - 1;
776	}
777	#ifdef PRINT_MAP_ERROR
778	if (prevno != lastno)
779	printf("write_map: botch #2: bitno=%d prevno=%d lastno=%d\n", bitno,
780	prevno, lastno);
781	#endif
782	return 0;
783	}
784	#endif
785
786	#endif