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 char name[1]; 40 }; 41 42 43 struct EntryCacheGeneration { 44 int32 next_index; 45 EntryCacheEntry** entries; 46 47 EntryCacheGeneration(); 48 ~EntryCacheGeneration(); 49 50 status_t Init(); 51 }; 52 53 54 struct 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 82 class EntryCache { 83 public: 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 99 private: 100 static const int32 kGenerationCount = 8; 101 102 typedef BOpenHashTable<EntryCacheHashDefinition> EntryTable; 103 typedef DoublyLinkedList<EntryCacheEntry> EntryList; 104 105 private: 106 void _AddEntryToCurrentGeneration( 107 EntryCacheEntry* entry); 108 109 private: 110 rw_lock fLock; 111 EntryTable fEntries; 112 EntryCacheGeneration fGenerations[kGenerationCount]; 113 int32 fCurrentGeneration; 114 }; 115 116 117 #endif // ENTRY_CACHE_H 118