cache_inode_avl.h File Reference

Definitions supporting AVL dirent representation. More...

#include "log.h"
#include "cache_inode.h"
#include "avltree.h"

Go to the source code of this file.

Defines
#define	CACHE_INODE_FLAG_NEXT_ACTIVE   0x0001
Functions
void	avl_dirent_set_deleted (cache_entry_t *entry, cache_inode_dir_entry_t *v)
void	avl_dirent_clear_deleted (cache_entry_t *entry, cache_inode_dir_entry_t *v)
void	cache_inode_avl_init (cache_entry_t *entry)
int	cache_inode_avl_qp_insert (cache_entry_t *entry, cache_inode_dir_entry_t *v)
cache_inode_dir_entry_t *	cache_inode_avl_lookup_k (cache_entry_t *entry, uint64_t k, uint32_t flags)
cache_inode_dir_entry_t *	cache_inode_avl_qp_lookup_s (cache_entry_t *entry, cache_inode_dir_entry_t *v, int maxj)

---

Detailed Description

Definitions supporting AVL dirent representation.

Author:

Matt Benjamin

DESCRIPTION

Definitions supporting AVL dirent representation. The current design represents dirents as a single AVL tree ordered by a collision-resistent hash function (currently, Murmur3, which appears to be several times faster than lookup3 on x86_64 architecture). Quadratic probing is used to emulate perfect hashing. Worst case behavior is challenging to reproduce. Heuristic methods are used to detect worst-case scenarios and fall back to tractable (e.g., lookup) algorthims.

Definition in file cache_inode_avl.h.

---

Define Documentation

#define CACHE_INODE_FLAG_NEXT_ACTIVE   0x0001

Definition at line 84 of file cache_inode_avl.h.

---

Function Documentation

void avl_dirent_clear_deleted	(	cache_entry_t *	entry,
		cache_inode_dir_entry_t *	v
	)

Definition at line 102 of file cache_inode_avl.c.

void avl_dirent_set_deleted	(	cache_entry_t *	entry,
		cache_inode_dir_entry_t *	v
	)

Definition at line 77 of file cache_inode_avl.c.

void cache_inode_avl_init

(

cache_entry_t *

entry

)

Definition at line 50 of file cache_inode_avl.c.

cache_inode_dir_entry_t* cache_inode_avl_lookup_k	(	cache_entry_t *	entry,
		uint64_t	k,
		uint32_t	flags
	)

Definition at line 233 of file cache_inode_avl.c.

int cache_inode_avl_qp_insert	(	cache_entry_t *	entry,
		cache_inode_dir_entry_t *	v
	)

Definition at line 187 of file cache_inode_avl.c.

cache_inode_dir_entry_t* cache_inode_avl_qp_lookup_s	(	cache_entry_t *	entry,
		cache_inode_dir_entry_t *	v,
		int	maxj
	)

Definition at line 276 of file cache_inode_avl.c.