lru.h 7.15 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
/*  Copyright (C) 2013 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
14
    along with this program.  If not, see <https://www.gnu.org/licenses/>.
15 16 17 18 19
 */
/**
 * @file lru.h
 * @brief LRU-like cache.
 *
20 21 22 23
 * @note This is a naive LRU implementation with a simple slot stickiness counting.
 *       Each write access increases stickiness on success, and decreases on collision.
 *       A slot is freed if the stickiness decreases to zero. This makes it less likely,
 *       that often-updated entries are jousted out of cache.
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
 *
 * # Example usage:
 *
 * @code{.c}
 * 	// Define new LRU type
 * 	typedef lru_hash(int) lru_int_t;
 *
 * 	// Create LRU on stack
 * 	size_t lru_size = lru_size(lru_int_t, 10);
 * 	lru_int_t lru[lru_size];
 * 	lru_init(&lru, 5);
 *
 * 	// Insert some values
 * 	*lru_set(&lru, "luke", strlen("luke")) = 42;
 * 	*lru_set(&lru, "leia", strlen("leia")) = 24;
 *
 * 	// Retrieve values
 * 	int *ret = lru_get(&lru, "luke", strlen("luke");
 * 	if (ret) printf("luke dropped out!\n");
 * 	else     printf("luke's number is %d\n", *ret);
 *
 * 	// Set up eviction function, this is going to get called
 * 	// on entry eviction (baton refers to baton in 'lru' structure)
 * 	void on_evict(void *baton, void *data_) {
 * 		int *data = (int *) data;
 * 		printf("number %d dropped out!\n", *data);
 * 	}
 * 	char *enemies[] = {"goro", "raiden", "subzero", "scorpion"};
 * 	for (int i = 0; i < 4; ++i) {
53 54 55
 * 		int *val = lru_set(&lru, enemies[i], strlen(enemies[i]));
 * 		if (val)
 * 			*val = i;
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
 * 	}
 *
 * 	// We're done
 * 	lru_deinit(&lru);
 * @endcode
 *
 * \addtogroup generics
 * @{
 */

#pragma once

#include <stdlib.h>
#include <stdint.h>
#include "contrib/murmurhash3/murmurhash3.h"

#define lru_slot_struct \
	char *key;    /**< Slot key */ \
74 75
	uint16_t len; /**< Slot length */ \
	uint16_t refs; /**< Slot importance (#writes - #collisions) */ \
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
/** @brief Slot header. */
struct lru_slot {
	lru_slot_struct
};

/** @brief Return boolean true if slot matches key/len pair. */
static inline int lru_slot_match(struct lru_slot *slot, const char *key, uint32_t len)
{
	return (slot->len == len) && (memcmp(slot->key, key, len) == 0);
}

#define lru_slot_offset(table) \
	(size_t)((void *)&((table)->slots[0].data) - (void *)&((table)->slots[0]))

/** @brief Callback definitions. */
typedef void (*lru_free_f)(void *baton, void *ptr);

/** @brief LRU structure base. */
#define lru_hash_struct \
	uint32_t size;      /**< Number of slots */ \
96
	uint32_t evictions; /**< Number of evictions. */ \
97 98 99 100 101 102 103 104 105
	uint32_t stride;    /**< Stride of the 'slots' array */ \
	lru_free_f evict;   /**< Eviction function */ \
	void *baton;        /**< Passed to eviction function */
/** @internal Object base of any other lru_hash type. */
struct lru_hash_base {
	lru_hash_struct
	char slots[];
};

106
/** @brief User-defined hashtable. */
107 108 109 110 111 112 113 114 115
#define lru_hash(type) \
struct { \
	lru_hash_struct \
	struct { \
		lru_slot_struct \
		type data; \
	} slots[]; \
}

116 117 118
/** Get slot at given index. */
static inline void *lru_slot_at(struct lru_hash_base *lru, uint32_t id)
{
119 120 121
	if (id >= lru->size) {
		return NULL;
	}
122 123 124 125 126 127 128 129 130
	return (struct lru_slot *)(lru->slots + (id * lru->stride));
}

/** Get pointer to slot value. */
static inline void *lru_slot_val(struct lru_slot *slot, size_t offset)
{
	return ((char *)slot) + offset;
}

131
/** @internal Slot data getter */
132
static inline void *lru_slot_get(struct lru_hash_base *lru, const char *key, uint16_t len, size_t offset)
133
{
Marek Vavruša's avatar
Marek Vavruša committed
134 135 136
	if (!lru || !key || len == 0) {
		return NULL;
	}
137
	uint32_t id = hash(key, len) % lru->size;
138
	struct lru_slot *slot = lru_slot_at(lru, id);
139
	if (lru_slot_match(slot, key, len)) {
140
		return lru_slot_val(slot, offset);
141 142 143 144
	}
	return NULL;
}

145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
static inline int lru_slot_evict(struct lru_hash_base *lru, uint32_t id, size_t offset)
{
	struct lru_slot *slot = lru_slot_at(lru, id);
	if (!slot || !slot->key) {
		return -1;
	}
	lru->evictions += 1;
	free(slot->key);
	if (lru->evict) {
		lru->evict(lru->baton, lru_slot_val(slot, offset));
	}
	memset(slot, 0, lru->stride);
	return 0;
}

160
/** @internal Slot data setter */
161
static inline void *lru_slot_set(struct lru_hash_base *lru, const char *key, uint16_t len, size_t offset)
162
{
Marek Vavruša's avatar
Marek Vavruša committed
163 164 165
	if (!lru || !key || len == 0) {
		return NULL;
	}
166
	uint32_t id = hash(key, len) % lru->size;
167
	struct lru_slot *slot = lru_slot_at(lru, id);
168
	if (lru_slot_match(slot, key, len)) {
169
		slot->refs = 1; /* Increase slot significance */
170
	} else {
171
		if (slot->key) {
172 173 174 175
			slot->refs -= 1; /* Decrease slot significance */
			if (slot->refs > 0) {
				return NULL; /* Couldn't joust former key. */
			}
176 177
			if (lru_slot_evict(lru, id, offset) < 0) {
				return NULL;
178 179 180 181 182 183 184 185 186
			}
		}
		memset(slot, 0, lru->stride);
		slot->key = malloc(len);
		if (!slot->key) {
			return NULL;
		}
		memcpy(slot->key, key, len);
		slot->len = len;
187
		slot->refs = 1;
188
	}
189
	return lru_slot_val(slot, offset);
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
}

/**
 * @brief Return size of the LRU structure with given number of slots.
 * @param  type     type of LRU structure
 * @param  max_slots number of slots
 */
#define lru_size(type, max_slots) \
	(sizeof(type) + (max_slots) * sizeof(((type *)NULL)->slots[0]))

/**
 * @brief Initialize hash table.
 * @param table hash table
 * @param max_slots number of slots
 */
205 206 207
#define lru_init(table, max_slots) \
 (memset((table), 0, sizeof(*table) + (max_slots) * sizeof((table)->slots[0])), \
  (table)->stride = sizeof((table)->slots[0]), (table)->size = (max_slots))
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245

/**
 * @brief Free all keys and evict all values.
 * @param table hash table
 */
#define lru_deinit(table) if (table) { \
	for (uint32_t i = 0; i < (table)->size; ++i) { \
		if ((table)->slots[i].key) { \
			if ((table)->evict) { \
				(table)->evict((table)->baton, &(table)->slots[i].data); \
			} \
			free((table)->slots[i].key); \
		} \
	} \
}

/**
 * @brief Find key in the hash table and return pointer to it's value.
 * @param table hash table
 * @param key_ lookup key
 * @param len_ key length
 * @return pointer to data or NULL
 */
#define lru_get(table, key_, len_) \
	(__typeof__(&(table)->slots[0].data)) \
		lru_slot_get((struct lru_hash_base *)(table), (key_), (len_), lru_slot_offset(table))

/**
 * @brief Return pointer to value (create/replace if needed)
 * @param table hash table
 * @param key_ lookup key
 * @param len_ key length
 * @return pointer to data or NULL
 */
#define lru_set(table, key_, len_) \
 	(__typeof__(&(table)->slots[0].data)) \
		lru_slot_set((struct lru_hash_base *)(table), (key_), (len_), lru_slot_offset(table))

246 247 248 249 250 251 252 253 254
/**
 * @brief Evict element at index.
 * @param table hash table
 * @param pos_ element position
 * @return 0 if successful, negative integer if failed
 */
#define lru_evict(table, pos_) \
 	lru_slot_evict((struct lru_hash_base *)(table), (pos_), lru_slot_offset(table))

255
/** @} */