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 int32 entries_size; 48 EntryCacheEntry** entries; 49 50 EntryCacheGeneration(); 51 ~EntryCacheGeneration(); 52 53 status_t Init(int32 entriesSize); 54 }; 55 56 57 struct 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 85 class EntryCache { 86 public: 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 102 private: 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 int32 fGenerationCount; 114 EntryCacheGeneration* fGenerations; 115 int32 fCurrentGeneration; 116 }; 117 118 119 #endif // ENTRY_CACHE_H 120