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