lruhash.h

Go to the documentation of this file.

/*
 * util/storage/lruhash.h - hashtable, hash function, LRU keeping.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

 
#ifndef UTIL_STORAGE_LRUHASH_H
#define UTIL_STORAGE_LRUHASH_H
#include "util/locks.h"
struct lruhash_bin;
struct lruhash_entry;

#define HASH_DEFAULT_STARTARRAY     1024 /* entries in array */
#define HASH_DEFAULT_MAXMEM     4*1024*1024 /* bytes */

typedef uint32_t hashvalue_type;

typedef size_t (*lruhash_sizefunc_type)(void*, void*);

typedef int (*lruhash_compfunc_type)(void*, void*);

typedef void (*lruhash_delkeyfunc_type)(void*, void*);

typedef void (*lruhash_deldatafunc_type)(void*, void*);

typedef void (*lruhash_markdelfunc_type)(void*);

struct lruhash {
    lock_quick_type lock;
    lruhash_sizefunc_type sizefunc;
    lruhash_compfunc_type compfunc;
    lruhash_delkeyfunc_type delkeyfunc;
    lruhash_deldatafunc_type deldatafunc;
    lruhash_markdelfunc_type markdelfunc;
    void* cb_arg;

    size_t size;
    int size_mask;
    struct lruhash_bin* array;

    struct lruhash_entry* lru_start;
    struct lruhash_entry* lru_end;

    size_t num;
    size_t space_used;
    size_t space_max;
};

struct lruhash_bin {
    lock_quick_type lock;
    struct lruhash_entry* overflow_list;
};

struct lruhash_entry {
    lock_rw_type lock;
    struct lruhash_entry* overflow_next;
    struct lruhash_entry* lru_next;
    struct lruhash_entry* lru_prev;
    hashvalue_type hash;
    void* key;
    void* data;
};

struct lruhash* lruhash_create(size_t start_size, size_t maxmem,
    lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc,
    lruhash_delkeyfunc_type delkeyfunc,
    lruhash_deldatafunc_type deldatafunc, void* arg);

void lruhash_delete(struct lruhash* table);

void lruhash_clear(struct lruhash* table);

void lruhash_insert(struct lruhash* table, hashvalue_type hash, 
    struct lruhash_entry* entry, void* data, void* cb_override);

struct lruhash_entry* lruhash_lookup(struct lruhash* table,
    hashvalue_type hash, void* key, int wr);

void lru_touch(struct lruhash* table, struct lruhash_entry* entry);

void lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md);
 
/************************* getdns functions ************************/
/*** these are used by getdns only and not by unbound. ***/

void lru_demote(struct lruhash* table, struct lruhash_entry* entry);

struct lruhash_entry* lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
        struct lruhash_entry* entry, void* data, void* cb_arg);
 
/************************* Internal functions ************************/
/*** these are only exposed for unit tests. ***/

void lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key);

void bin_init(struct lruhash_bin* array, size_t size);

void bin_delete(struct lruhash* table, struct lruhash_bin* bin);

struct lruhash_entry* bin_find_entry(struct lruhash* table, 
    struct lruhash_bin* bin, hashvalue_type hash, void* key);

void bin_overflow_remove(struct lruhash_bin* bin, 
    struct lruhash_entry* entry);

void bin_split(struct lruhash* table, struct lruhash_bin* newa, 
    int newmask);

void reclaim_space(struct lruhash* table, struct lruhash_entry** list);

void table_grow(struct lruhash* table);

void lru_front(struct lruhash* table, struct lruhash_entry* entry);

void lru_remove(struct lruhash* table, struct lruhash_entry* entry);

void lruhash_status(struct lruhash* table, const char* id, int extended);

size_t lruhash_get_mem(struct lruhash* table);

void lruhash_traverse(struct lruhash* h, int wr,
        void (*func)(struct lruhash_entry*, void*), void* arg);
 
#endif /* UTIL_STORAGE_LRUHASH_H */