1/*
2 * Copyright 2008-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5#ifndef ENTRY_CACHE_H
6#define ENTRY_CACHE_H
7
8
9#include <stdlib.h>
10
11#include <util/AutoLock.h>
12#include <util/khash.h>
13#include <util/OpenHashTable.h>
14
15
16struct EntryCacheKey {
17	EntryCacheKey(ino_t dirID, const char* name)
18		:
19		dir_id(dirID),
20		name(name)
21	{
22		hash = (uint32)dir_id ^ (uint32)(dir_id >> 32) ^ hash_hash_string(name);
23			// We cache the hash value, so we can easily compute it before
24			// holding any locks.
25	}
26
27	ino_t		dir_id;
28	const char*	name;
29	size_t		hash;
30};
31
32
33struct EntryCacheEntry {
34			EntryCacheEntry*	hash_link;
35			ino_t				node_id;
36			ino_t				dir_id;
37			vint32				generation;
38			vint32				index;
39			char				name[1];
40};
41
42
43struct EntryCacheGeneration {
44			vint32				next_index;
45			EntryCacheEntry**	entries;
46
47								EntryCacheGeneration();
48								~EntryCacheGeneration();
49
50			status_t			Init();
51};
52
53
54struct EntryCacheHashDefinition {
55	typedef EntryCacheKey	KeyType;
56	typedef EntryCacheEntry	ValueType;
57
58	uint32 HashKey(const EntryCacheKey& key) const
59	{
60		return key.hash;
61	}
62
63	size_t Hash(const EntryCacheEntry* value) const
64	{
65		return (uint32)value->dir_id ^ (uint32)(value->dir_id >> 32)
66			^ hash_hash_string(value->name);
67	}
68
69	bool Compare(const EntryCacheKey& key, const EntryCacheEntry* value) const
70	{
71		return value->dir_id == key.dir_id
72			&& strcmp(value->name, key.name) == 0;
73	}
74
75	EntryCacheEntry*& GetLink(EntryCacheEntry* value) const
76	{
77		return value->hash_link;
78	}
79};
80
81
82class EntryCache {
83public:
84								EntryCache();
85								~EntryCache();
86
87			status_t			Init();
88
89			status_t			Add(ino_t dirID, const char* name,
90									ino_t nodeID);
91
92			status_t			Remove(ino_t dirID, const char* name);
93
94			bool				Lookup(ino_t dirID, const char* name,
95									ino_t& nodeID);
96
97			const char*			DebugReverseLookup(ino_t nodeID, ino_t& _dirID);
98
99private:
100	static	const int32			kGenerationCount = 8;
101
102			typedef BOpenHashTable<EntryCacheHashDefinition> EntryTable;
103			typedef DoublyLinkedList<EntryCacheEntry> EntryList;
104
105private:
106			void				_AddEntryToCurrentGeneration(
107									EntryCacheEntry* entry);
108
109private:
110			rw_lock				fLock;
111			EntryTable			fEntries;
112			EntryCacheGeneration fGenerations[kGenerationCount];
113			int32				fCurrentGeneration;
114};
115
116
117#endif	// ENTRY_CACHE_H
118