Buddy Tahsisi Algoritma - Başlangıç ​​Öbek Adres

Question

Şu anda Buddy Allocatoraçıklanan Bilgisayar Programlama Vol Sanat uygulamak çalışıyorum: Belirli bir veri bloğunun ve adresini önemli değişmezin yararlanır 1, kendisine tekabül dostum. hesaplama çok iyi arkadaş sistemi kılan nedir

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 

gerçekleştirmek ... aşağıdaki xor'ing yoluyla (bu hesaplama sadece i'inci biti bir dokunmanızda yapılabilir, arkadaşının adresini bulmak için olmasıdır gibidir 1 < < ile i). Sol blok adresi verildiğinde, bu doğru bloğu döndürecektir. Doğru blok verilirse, bu sol bloğu döndürecektir.

Ancak, bu yöntem, yığının adres 0'da başlayacağını varsayar. Yığın, i olan bir sıraya sahip bitler içeren adreslerle başlıyorsa, yukarıdaki hesaplamanın yapılması size doğru adresin verilmeyecektir. onun dostum.

Bu nedenle, herhangi bir başlangıç ​​yığın adresinde gerçekleştirilebilmesi için bu hesaplamayı genelleştirmenin bir yolu var mı? Maksimum düzene bağlı olduğunu varsayalım. IE * max sipariş 18 ise, 18 seviyesine eşit veya ondan daha büyük herhangi bir hesaplama yapmayı denemeyeceğiz, böylece arkadaşınızı bulmanız gerekmiyor.

Bu konuda herhangi bir yardım veya öneri çok takdir!

Answer 1

Woah, hardcore. Knuth okumak için Kudos!

Her neyse, noktayı kaçırıyor olabilirim, ancak bir noktada, sistemden bellek sistemini uygulamak için OS'den bitişik bir bellek yığınını talep ediyorum. Bu yüzden başlangıç ​​adresini sadece etrafta tutamadınız (buna rağmen free()'a ihtiyacınız var) ve kullandığınız adreslerin sıfır tabanlı görünmesini sağlamak için bu ofseti kullanamazsınız? Örneğin, bu gibi bir şey:

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; 
}