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