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/khash.h> 13#include <util/OpenHashTable.h> 14 15 16struct 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 33struct EntryCacheEntry { 34 EntryCacheEntry* hash_link; 35 ino_t node_id; 36 ino_t dir_id; 37 vint32 generation; 38 vint32 index; 39 char name[1]; 40}; 41 42 43struct EntryCacheGeneration { 44 vint32 next_index; 45 EntryCacheEntry** entries; 46 47 EntryCacheGeneration(); 48 ~EntryCacheGeneration(); 49 50 status_t Init(); 51}; 52 53 54struct 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 82class EntryCache { 83public: 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 99private: 100 static const int32 kGenerationCount = 8; 101 102 typedef BOpenHashTable<EntryCacheHashDefinition> EntryTable; 103 typedef DoublyLinkedList<EntryCacheEntry> EntryList; 104 105private: 106 void _AddEntryToCurrentGeneration( 107 EntryCacheEntry* entry); 108 109private: 110 rw_lock fLock; 111 EntryTable fEntries; 112 EntryCacheGeneration fGenerations[kGenerationCount]; 113 int32 fCurrentGeneration; 114}; 115 116 117#endif // ENTRY_CACHE_H 118