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