1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
/*-------------------------------------------------------------------------
*
* 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
|
