/*-------------------------------------------------------------------------
 *
 * aspace_map.h
 *	  Address space map.
 *
 * An aspace_map is a lookup table where the keys and values are 64-bit
 * integers.  The key limit (one more than the highest allowable key)
 * must be specified at the time the map is created.  The value may be any
 * 64-bit integer unless ASPACE_MAP_32BIT_VALUES is specified, in which
 * case it must be less than 2^32.  Attempting to look up a key not
 * entered into the table will return 0.
 *
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/utils/aspace_map.h
 *
 *-------------------------------------------------------------------------
 */

#ifndef ASPACE_MAP_H
#define ASPACE_MAP_H

#include "storage/dsm.h"

/*
 * Flags that can be passed to aspace_map_create().
 *
 * If ASPACE_MAP_DIRECT is specified, the map will be stored as a single
 * array whose size is equal to the key limit.  ASPACE_MAP_INDIRECT will
 * use a two-level radix tree, with exactly 18 bits handled at the bottom
 * level.  ASPACE_MAP_DOUBLE_INDIRECT will use a three-level radix tree,
 * with 18 bits handled in each of the bottom two levels and the remainder
 * handled at the top level.  At most one of these flags can be specified.
 * If none of these flags is given, an appropriate value will be chosen
 * based on the key limit.
 *
 * If ASPACE_MAP_32BIT_VALUES is used, all values later stored in the map
 * must be less than 2^32.  This reduces memory consumption by about 50%.
 */
#define ASPACE_MAP_DIRECT					0x0001
#define ASPACE_MAP_INDIRECT					0x0002
#define ASPACE_MAP_DOUBLE_INDIRECT			0x0003
#define ASPACE_MAP_32BIT_VALUES				0x0004

/*
 * Since we expected entries to be clustered within the available keyspace,
 * it makes sense to cache a few entries at each level for quick access.
 * This also helps to keep the map small; if the total number of entries at
 * any given level fits within the cache, we don't need a real array for
 * that level.
 */
#define ASPACE_CACHESIZE_DOUBLE_INDIRECT	4
#define ASPACE_CACHESIZE_INDIRECT			4
#define ASPACE_CACHESIZE_DIRECT				16

typedef struct
{
	uint64		key;
	uint64		value;		/* If indirect, (relative) pointer; else value. */
} aspace_pair;

typedef struct
{
	unsigned	flags;
	uint64		maxkey;
	uint64		map;		/* Pointer or relative pointer. */
	aspace_pair direct_cache[ASPACE_CACHESIZE_DIRECT];
	aspace_pair	indirect_cache[ASPACE_CACHESIZE_INDIRECT];
	aspace_pair	double_indirect_cache[ASPACE_CACHESIZE_DOUBLE_INDIRECT];
} aspace_map;

typedef void *(*aspace_map_allocator)(void *private, Size);

/* API functions. */
extern void aspace_map_initialize(aspace_map *, uint64 key_limit, int flags);
extern void aspace_map_set_range(aspace_map *map,
					 uint64 first_key, uint64 nkeys, uint64 value,
					 char *base, aspace_map_allocator allocator,
					 void *allocator_private);
extern uint64 aspace_map_get(aspace_map *, uint64 key, char *base);

#endif