datapagemap.c

/*
 * A data structure for keeping track of data pages that have changed.
 *
 * This is a fairly simple bitmap.
 *
 * Copyright (c) 2013 VMware, Inc. All Rights Reserved.
 */

#include "postgres_fe.h"

#include "datapagemap.h"
#include "util.h"

struct datapagemap_iterator
{
	datapagemap_t *map;
	BlockNumber	nextblkno;
};

/*****
 * Public functions
 */

/*
 * Add a block to the bitmap.
 */
void
datapagemap_add(datapagemap_t *map, BlockNumber blkno)
{
	int			offset;
	int			bitno;

	offset = blkno / 8;
	bitno = blkno % 8;

	/* enlarge or create bitmap if needed */
	if (map->bitmapsize <= offset)
	{
		int oldsize = map->bitmapsize;
		int newsize;

		/*
		 * The minimum to hold the new bit is offset + 1. But add some
		 * headroom, so that we don't need to repeatedly enlarge the bitmap
		 * in the common case that blocks are modified in order, from beginning
		 * of a relation to the end.
		 */
		newsize = offset + 1;
		newsize += 10;

		if (map->bitmap == NULL)
			map->bitmap = pg_malloc(newsize);
		else
			map->bitmap = pg_realloc(map->bitmap, newsize);

		/* zero out the newly allocated region */
		memset(&map->bitmap[oldsize], 0, newsize - oldsize);

		map->bitmapsize = newsize;
	}

	/* Set the bit */
	map->bitmap[offset] |= (1 << bitno);
}

/*
 * Start iterating through all entries in the page map.
 *
 * After datapagemap_iterate, call datapagemap_next to return the entries,
 * until it returns NULL. After you're done, use free() to destroy the
 * iterator.
 */
datapagemap_iterator_t *
datapagemap_iterate(datapagemap_t *map)
{
	datapagemap_iterator_t *iter = pg_malloc(sizeof(datapagemap_iterator_t));
	iter->map = map;
	iter->nextblkno = 0;
	return iter;
}

bool
datapagemap_next(datapagemap_iterator_t *iter, BlockNumber *blkno)
{
	datapagemap_t *map = iter->map;

	for (;;)
	{
		BlockNumber blk = iter->nextblkno;
		int		nextoff = blk / 8;
		int		bitno = blk % 8;

		if (nextoff >= map->bitmapsize)
			break;

		iter->nextblkno++;

		if (map->bitmap[nextoff] & (1 << bitno))
		{
			*blkno = blk;
			return true;
		}
	}

	/* no more set bits in this bitmap. */
	return false;
}

/*
 * A debugging aid. Prints out the contents of the page map.
 */
void
datapagemap_print(datapagemap_t *map)
{
	datapagemap_iterator_t *iter = datapagemap_iterate(map);
	BlockNumber blocknum;

	while (datapagemap_next(iter, &blocknum))
	{
		printf("  blk %u\n", blocknum);
	}
	free(iter);
}