Lines Matching defs:Cluster
44 // * Cluster -- aligned 1-MB region of the address space
45 // * Block-ID -- block-number within a cluster
46 // * Cluster-ID -- Starting address of cluster divided by cluster size
49 // 1. A hash-table maps from a cluster-ID to the data for that cluster.
50 // 2. For each non-empty cluster we keep an array indexed by
58 // | id->cluster |---> ...
60 // | id->cluster |---> Cluster
71 // clusters. The minimum space requirement for a cluster is the size
73 // the cluster. Empty blocks impose no extra space requirement.
76 // a. A hash-table lookup to find the cluster
77 // b. An array access in the cluster structure
168 // We further group a sequence of consecutive blocks into a cluster.
169 // The data for a cluster is represented as a dense array of
176 struct Cluster {
177 Cluster* next; // Next cluster in hash table chain
178 Number id; // Cluster ID
182 // Number of hash-table entries. With the block-size/cluster-size
183 // defined above, each cluster covers 1 MB, so an 4K entry
192 Cluster** hashtable_; // The hash-table
208 // Find cluster object for specified address. If not found
213 Cluster* FindCluster(Number address, bool create) {
217 for (Cluster* c = hashtable_[h]; c != NULL; c = c->next) {
223 // Create cluster if necessary
225 Cluster* c = New<Cluster>(1);
234 // Return the block ID for an address within its cluster
275 hashtable_ = New<Cluster*>(kHashSize);
296 const Cluster* const c = FindCluster(num, false/*do not create*/);
310 Cluster* const c = FindCluster(num, true/*create*/);
342 Cluster* const c = FindCluster(num, false/*do not create*/);
366 const Cluster* c = FindCluster(num, false/*do not create*/);
391 if (num < kClusterSize) return NULL; // first cluster
392 // go to address-wise previous cluster to try
393 num |= kClusterSize - 1; // start at the last block of previous cluster
411 for (const Cluster* c = hashtable_[h]; c != NULL; c = c->next) {