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 = (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 34 struct 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 45 struct EntryCacheGeneration { 46 int32 next_index; 47 EntryCacheEntry** entries; 48 49 EntryCacheGeneration(); 50 ~EntryCacheGeneration(); 51 52 status_t Init(); 53 }; 54 55 56 struct EntryCacheHashDefinition { 57 typedef EntryCacheKey KeyType; 58 typedef EntryCacheEntry ValueType; 59 60 uint32 HashKey(const EntryCacheKey& key) const 61 { 62 return key.hash; 63 } 64 65 size_t Hash(const EntryCacheEntry* value) const 66 { 67 return (uint32)value->dir_id ^ (uint32)(value->dir_id >> 32) 68 ^ hash_hash_string(value->name); 69 } 70 71 bool Compare(const EntryCacheKey& key, const EntryCacheEntry* value) const 72 { 73 return value->dir_id == key.dir_id 74 && strcmp(value->name, key.name) == 0; 75 } 76 77 EntryCacheEntry*& GetLink(EntryCacheEntry* value) const 78 { 79 return value->hash_link; 80 } 81 }; 82 83 84 class EntryCache { 85 public: 86 EntryCache(); 87 ~EntryCache(); 88 89 status_t Init(); 90 91 status_t Add(ino_t dirID, const char* name, 92 ino_t nodeID, bool missing); 93 94 status_t Remove(ino_t dirID, const char* name); 95 96 bool Lookup(ino_t dirID, const char* name, 97 ino_t& nodeID, bool& missing); 98 99 const char* DebugReverseLookup(ino_t nodeID, ino_t& _dirID); 100 101 private: 102 static const int32 kGenerationCount = 8; 103 104 typedef BOpenHashTable<EntryCacheHashDefinition> EntryTable; 105 typedef DoublyLinkedList<EntryCacheEntry> EntryList; 106 107 private: 108 void _AddEntryToCurrentGeneration( 109 EntryCacheEntry* entry); 110 111 private: 112 rw_lock fLock; 113 EntryTable fEntries; 114 EntryCacheGeneration fGenerations[kGenerationCount]; 115 int32 fCurrentGeneration; 116 }; 117 118 119 #endif // ENTRY_CACHE_H 120