操作系统实验_buddy算法源程序.rar_buddy_伙伴算法_伙伴系统_操作系统

#include "buddy.h" #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <assert.h> #include <string.h> #define NODE_UNUSED 0 #define NODE_USED 1 #define NODE_SPLIT 2 #define NODE_FULL 3 struct buddy { int level; uint8_t tree[1]; }; struct buddy * buddy_new(int level) { int size = 1 << level; struct buddy * self = malloc(sizeof(struct buddy) + sizeof(uint8_t) * (size * 2 - 2)); self->level = level; memset(self->tree , NODE_UNUSED , size*2-1); return self; } void buddy_delete(struct buddy * self) { free(self); } static inline int is_pow_of_2(uint32_t x) { return !(x & (x-1)); } static inline uint32_t next_pow_of_2(uint32_t x) { if ( is_pow_of_2(x) ) return x; x |= x>>1; x |= x>>2; x |= x>>4; x |= x>>8; x |= x>>16; return x+1; } static inline int _index_offset(int index, int level, int max_level) { return ((index + 1) - (1 << level)) << (max_level - level); } static void _mark_parent(struct buddy * self, int index) { for (;;) { int buddy = index - 1 + (index & 1) * 2; if (buddy > 0 && (self->tree[buddy] == NODE_USED || self->tree[buddy] == NODE_FULL)) { index = (index + 1) / 2 - 1; self->tree[index] = NODE_FULL; } else { return; } } } int buddy_alloc(struct buddy * self , int s) { int size; if (s==0) { size = 1; } else { size = (int)next_pow_of_2(s); } int length = 1 << self->level; if (size > length) return -1; int index = 0; int level = 0; while (index >= 0) { if (size == length) { if (self->tree[index] == NODE_UNUSED) { self->tree[index] = NODE_USED; _mark_parent(self, index); return _index_offset(index, level, self->level); } } else { // size < length switch (self->tree[index]) { case NODE_USED: case NODE_FULL: break; case NODE_UNUSED: // split first self->tree[index] = NODE_SPLIT; self->tree[index*2+1] = NODE_UNUSED; self->tree[index*2+2] = NODE_UNUSED; default: index = index * 2 + 1; length /= 2; level++; continue; } } if (index & 1) { ++index; continue; } for (;;) { level--; length *= 2; index = (index+1)/2 -1; if (index < 0) return -1; if (index & 1) { ++index; break; } } } return -1; } static void _combine(struct buddy * self, int index) { for (;;) { int buddy = index - 1 + (index & 1) * 2; if (buddy < 0 || self->tree[buddy] != NODE_UNUSED) { self->tree[index] = NODE_UNUSED; while (((index = (index + 1) / 2 - 1) >= 0) && self->tree[index] == NODE_FULL){ self->tree[index] = NODE_SPLIT; } return; } index = (index + 1) / 2 - 1; } } void buddy_free(struct buddy * self, int offset) { assert( offset < (1<< self->level)); int left = 0; int length = 1 << self->level; int index = 0; for (;;) { switch (self->tree[index]) { case NODE_USED: assert(offset == left); _combine(self, index); return; case NODE_UNUSED: assert(0); return; default: length /= 2; if (offset < left + length) { index = index * 2 + 1; } else { left += length; index = index * 2 + 2; } break; } } } int buddy_size(struct buddy * self, int offset) { assert( offset < (1<< self->level)); int left = 0; int length = 1 << self->level; int index = 0; for (;;) { switch (self->tree[index]) { case NODE_USED: assert(offset == left); return length; case NODE_UNUSED: assert(0); return length; default: length /= 2; if (offset < left + length) { index = index * 2 + 1; } else { left += length; index = index * 2 + 2; } break; } } } static void _dump(struct buddy * self, int index , int level) { switch (self->tree[index]) { case NODE_UNUSED: printf("(%d:%d)", _index_offset(index, level, self->level) , 1 << (self->level - level)); break; case NODE_USED: printf("[%d:%d]", _index_offset(index, level, self->level) , 1 << (self->level - level)); break; case NODE_FULL: printf("{"); _dump(self, index * 2 + 1 , level+1); _dump(self, index * 2 + 2 , level+1); printf("}"); break; default: printf("("); _dump(self, index * 2 + 1 , level+1); _dump(self, index * 2 + 2 , level+1); printf(")"); break; } } void buddy_dump(struct buddy * self) { _dump(self, 0 , 0); printf("\n"); }