src/system/kernel/fs/EntryCache.h

   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