बडी आबंटन एल्गोरिथ्म - शुरुआत ढेर पता

Question

मैं वर्तमान में लागू करने के लिए Buddy Allocator कंप्यूटर प्रोग्रामिंग खंड की कला में वर्णित कोशिश कर रहा हूँ: अपनी इसी 1 है, जो डेटा की एक दिए गए ब्लॉक और का पता करने में एक महत्वपूर्ण अपरिवर्तनीय का लाभ लेता है साथी। गणना इस प्रकार है ...

BUDDY(X): 

X + 2^i if x mod 2^i+1 = 0 
X - 2^i if x mod 2^i-1 = 0 

Where X is the address of the block; i is the current order 

क्या साथी प्रणाली बनाता प्रदर्शन इतनी अच्छी तरह से (है कि इस गणना के साथी का पता लगाने के लिए, बस ith आदेश बिट के एक फ्लिप साथ किया जा सकता है xor'ing के माध्यम से यह 1 < < i) के साथ। यदि बाएं ब्लॉक पते दिए गए हैं, तो यह सही ब्लॉक लौटाएगा। यदि सही ब्लॉक दिया गया है, तो यह बाएं ब्लॉक को वापस कर देगा।

हालांकि, यह विधि मानती है कि ढेर 0 पते पर शुरू होता है। यदि ढेर उन पतों के साथ शुरू होता है जिनके पास मेरे आदेश की सीमा के भीतर बिट्स हैं, तो उपर्युक्त गणना करने से आपको सही पता नहीं मिलेगा उसका दोस्त

इसलिए, बस, इस गणना को सामान्यीकृत करने का कोई तरीका है ताकि इसे किसी भी प्रारंभिक ढेर पते पर किया जा सके? मान लें कि अधिकतम आदेश के लिए बाध्य है। आईई * यदि अधिकतम आदेश 18 वर्ष है, तो हम 18 के आदेश से अधिक या उसके बराबर गणना करने की कोशिश नहीं करेंगे, इसलिए आपको अपने दोस्त को खोजने की आवश्यकता नहीं है।

इस पर किसी भी मदद या सुझाव की बहुत सराहना की!

Answer 1

वाह, कट्टर। Knuth पढ़ने के लिए Kudos!

वैसे भी, मैं इस बिंदु को याद कर रहा हूं, लेकिन किसी बिंदु पर आप ओएस से स्मृति प्रणाली के एक संगत खंड का अनुरोध कर रहे हैं (दोस्ताना)। तो क्या आप बस शुरुआती पता नहीं रख सकते थे (आपको इसे बाद में free() की आवश्यकता है), और आपके द्वारा उपयोग किए जाने वाले पते को शून्य-आधारित होने के लिए ऑफ़सेट का उपयोग करें? यानी इस तरह कुछ:

uint8_t* start_addr = malloc(SIZE_IN_BYTES); 

uint8_t* buddy(uint8_t* real_x) { 
    uint8_t *x = real_x - start_addr; 
    // do buddy bit-flipping on "x" 
    return x + start_addr; 
}