bitmap.c

mobile ip 在linux下的一种实现

/* $Id: bitmap.c,v 1.3 2000/04/06 07:26:52 jm Exp $
 * Dynamic bitmap
 *
 * Dynamic hierarchial IP tunnel
 * Copyright (C) 1998-2000, Dynamics group
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See README and COPYING for
 * more details.
 */

#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "debug.h"
#include "bitmap.h"

#define DEBUG_FLAG 'b'


struct bitmap *bitmap_init(int start_size)
{
	struct bitmap *map;

	if (start_size < 1)
		return NULL;

	map = (struct bitmap *) malloc(sizeof(struct bitmap));
	if (map == NULL)
		return NULL;

	map->size = start_size;
	if (start_size % 32 > 0)
		map->size += 32 - start_size % 32;
	map->u32s = map->size / 32;
	map->bits = (__u32 *) malloc(map->size);
	if (map->bits == NULL) {
		free(map);
		return NULL;
	}
	memset(map->bits, 0, map->size);
	DEBUG(DEBUG_FLAG,
	      "bitmap_init - initialized bitmap - size=%i (u32 x %i)\n",
	      map->size, map->u32s);
	return map;
}


void bitmap_destroy(struct bitmap *map)
{
	assert(map != NULL);
	if (map->bits != NULL)
		free(map->bits);
	free(map);
}


int bitmap_get_free(struct bitmap *map)
{
	int i, j;
        __u32 *tmp;

	assert(map != NULL);
	for (i = 0; i < map->u32s; i++) {
		if (map->bits[i] != (__u32) -1)
			break;
	}
	if (i == map->u32s) {
		/* bitmap full - try to allocate more space for it */
		tmp = realloc(map->bits, map->u32s * 2);
		if (tmp == NULL)
			return -1;
		map->bits = tmp;
		memset(&map->bits[map->u32s], 0, map->size);
		map->size *= 2;
		map->u32s *= 2;
		map->bits[i] |= 1;
		return i * 32;
	}

	/* map->bits[i] has at least one free bit */
	for (j = 0; j < 32; j++) {
		if ((map->bits[i] & (1 << j)) == 0)
			break;
	}
	map->bits[i] |= 1 << j;
	return i * 32 + j;
}


void bitmap_release(struct bitmap *map, int bit)
{
	assert(map != NULL);
	assert(bit >= 0 && bit < map->size);
	map->bits[bit / 32] &= ~(1 << (bit % 32));
}


void bitmap_debug_print(struct bitmap *map)
{
	int i, j;

	assert(map != NULL);

	for (i = 0; i < map->u32s; i++) {
		if (map->bits[i] == 0)
			continue;
		printf("%i: ", i);
		for (j = 0; j < 32; j++) {
			if (map->bits[i] & (1 << j))
				printf("X");
			else
				printf("-");
		}
		printf("\n");
	}
}