रेडिस हैश टेबल स्कैन की व्याख्या:तंत्र के अंदर

रेडिस स्कैन

1. यह गारंटी देता है कि तालिका में मौजूद सभी आइटम कम से कम एक बार लौटाए जाएंगे .
2. यह राज्यविहीन है . तालिका अपने सक्रिय स्कैनर के बारे में कोई डेटा सहेजती नहीं है। इसका मतलब यह भी है कि स्कैन डेटाबेस को लॉक नहीं करता है।
3. यह तालिका का आकार बदलने के लिए लचीला है। O(1) एक्सेस समय को बनाए रखने के लिए, हैश टेबल एक निश्चित लोड फैक्टर बनाए रखते हैं। लोड फैक्टर मापता है कि किसी निश्चित समय पर तालिका कितनी "भरी" है। जब लोड फैक्टर बहुत बड़ा या बहुत छोटा हो जाता है, तो तालिका का आकार बदल दिया जाता है। तालिका का आकार बदलने के दौरान कॉल करने पर भी SCAN अपनी गारंटी बनाए रखेगा।

कार्यान्वयन

unsigned long dictScan(dict *d,
 unsigned long v,
 dictScanFunction *fn,
 dictScanBucketFunction* bucketfn,
 void *privdata)
{
 dictht *t0, *t1;
 const dictEntry *de, *next;
 unsigned long m0, m1;
 if (dictSize(d) == 0) return 0;
 // ...

• फ़ंक्शन 5 पैरामीटर स्वीकार करता है:dict *d , स्कैन किया जाने वाला शब्दकोश, unsigned long v , कर्सर, और 3 अन्य पैरामीटर जिन पर हम बाद में विचार करेंगे।
• फ़ंक्शन इस फ़ंक्शन की अगली कॉल में उपयोग किए जाने वाले कर्सर मान को लौटाता है। यदि फ़ंक्शन 0 लौटाता है, तो इसका मतलब है कि स्कैन हो गया है।
• if (dictSize(d) == 0) return 0; . जब शब्दकोश खाली होता है तो फ़ंक्शन 0 लौटाता है यह इंगित करने के लिए कि स्कैन हो गया है।

1. सामान्य स्कैनिंग

if (!dictIsRehashing(d)) {
 t0 = &(d->ht[0]);
 m0 = t0->sizemask;
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
 de = t0->table[v & m0];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Set unmasked bits so incrementing the reversed cursor
 * operates on the masked bits */
 v |= ~m0;
 /* Increment the reverse cursor */
 v = rev(v);
 v++;
 v = rev(v);
} else {
 // ...

if (!dictIsRehashing(d)) {
 t0 = &(d->ht[0]);
 m0 = t0->sizemask;

/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
}

 /* Set unmasked bits so incrementing the reversed cursor
 * operates on the masked bits */
 v |= ~m0;
 /* Increment the reverse cursor */
 v = rev(v);
 v++;
 v = rev(v);

Table size = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (Current cursor)
v |= ~m0; // v == 11111000 (~m0 = 11110000)
v = rev(v); // v == 00011111
v++; // v == 00100000
v = rev(v); // v == 00000100

2. टेबल रीहैशिंग के दौरान स्कैनिंग

 } else { // dictIsRehashing(d)
 t0 = &d->ht[0];
 t1 = &d->ht[1];
 /* Make sure t0 is the smaller and t1 is the bigger table */
 if (t0->size > t1->size) {
 t0 = &d->ht[1];
 t1 = &d->ht[0];
 }
 m0 = t0->sizemask;
 m1 = t1->sizemask;
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
 de = t0->table[v & m0];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Iterate over indices in larger table that are the expansion
 * of the index pointed to by the cursor in the smaller table */
 do {
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
 de = t1->table[v & m1];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;
 v = rev(v);
 v++;
 v = rev(v);
 /* Continue while bits covered by mask difference is non-zero */
 } while (v & (m0 ^ m1));
 }