buddy system

#ifndef PUBLIC_UTILITY#define PUBLIC_UTILITY#include <stdio.h>#include <sys/sysinfo.h>#include <vector>#include <algorithm>namespace publicutility{using namespace std;class PublicUtility{public:	/*	 * @brief adjust odd elements to locate before even elements	 * */	static void Odd_before_Even(vector<int>&);	/*	 * @brief judge wheter a number is odd	 * */	inline static bool IsOdd(int num) 	{		return num & 1;	}	/*	 * @brief judge whether the num is to pwoer like 2 4 8 16 ...	 * */	inline static bool ToPower(size_t num)	{		return 0 == (num & (num -1));	}	/*	 * @brief get the free random	 * @return K free memory 	 * */	inline static unsigned long GetFreeRam() 	{		struct sysinfo s_info;		if(sysinfo(&s_info)) return 0;				return s_info.freeram;	}	/*	 * @brief fix the number to the minimal to power number such as num = 3 then return 4 num = 67 return 128	 * */	inline static unsigned FixToPower(unsigned num)	{		if(ToPower(num)) return num;		num |= (num >> 1);					// make top 2 bit to be 1 11xx xxxx xxxx xxxx xxxx xxxx xxxx xxxx		num |= (num >> 2);					// make top 4 bit to be 1 1111 xxxx xxxx xxxx xxxx xxxx xxxx xxxx		num |= (num >> 4);					// make top 8 bit to be 1 1111 1111 xxxx xxxx xxxx xxxx xxxx xxxx		num |= (num >> 8);					// make top 16 bit to be 1 1111 1111 1111 1111 xxxx xxxx xxxx xxxx		num |= (num >> 16);					// make top 32 bit to be 1 1111 1111 1111 1111 1111 1111 1111 1111		return num + 1;	}};}#endif#include "PublicUtility.h"namespace publicutility{/* * @brief adjust odd elements to locate before even elements * */void PublicUtility::Odd_before_Even(vector<int>&v){	int nlow = 0;	int nhigh = v.size() - 1;	bool blow_is_odd = false;	bool bhigh_is_odd = false;	bool blow_is_change = true;	bool bhigh_is_change = true;	while(nlow < nhigh)	{		if(blow_is_change)		{			blow_is_odd = IsOdd(v[nlow]);			blow_is_change = false;		}		if(bhigh_is_change)		{			bhigh_is_odd = IsOdd(v[nhigh]);			bhigh_is_change = false;		}		if(!blow_is_odd && bhigh_is_odd)		{			swap(v[nlow++], v[nhigh--]);			blow_is_change = true;			bhigh_is_change = true;		}		else		if(!blow_is_odd && !bhigh_is_odd)		{			nhigh--;			bhigh_is_change = true;		}		else		if(blow_is_odd && bhigh_is_odd)		{			nlow++;			blow_is_change = true;		}		else		{			nlow++;			nhigh--;			blow_is_change = true;			bhigh_is_change = true;		}	}}}/****************************************************************************@File Name: buddysystem.h@Author: wangzhicheng@mail: 2363702560@QQ.com@Created Time: Wed 15 Feb 2017 01:54:36 PM CST			   2017-02-20****************************************************************************/#ifndef BUDDY_SYSTEM_H#define BUDDY_SYSTEM_H#include <stdio.h>#include <string.h>#include <iostream>#include <vector>#include <mutex>#include <algorithm>#include "PublicUtility.h"namespace buddysystem{using namespace publicutility;class FreeException{public:	FreeException()	{		fPRintf(stderr, "free exception...!/n");	}};class BuddySystem{private:	unsigned m_nCapacity;				// total memory 	vector<unsigned>m_vecTree;			// full binary tree for storing each memory block	void *m_pBasePtr;					// pointer to a memory zone	mutex m_gmutex;private:	/*	 * @brief get the current node of parent	 * */	inline int Parent(int current)	{		return (current - 1) >> 1;	}	/*	 * @brief get the current index of lchild	 * */	inline int Lchild(int current)	{		return (current << 1) + 1;	}	/*	 * @brief get the current index of rchild	 * */	inline int Rchild(int current)	{		return (current << 1) + 2;	}public:	BuddySystem():m_pBasePtr(0)	{	}	~BuddySystem()	{		if(m_pBasePtr)		{			free(m_pBasePtr);	//		m_pBasePtr = 0;		}	}	/*	 * @brief initialize the buddy system	 * @cap the memory capacity unit:Byte	 * @return true if init ok	 * */	bool Init(unsigned cap);	/*	 * @brief cout the tree sequently	 * */	void ShowTree() const;	/*	 * @brief allocate the memory	 * @size memory size(uint:byte)	 * @return the starting allocated memory address	 * */	void *Alloc(unsigned size);	/*	 * @brief free the memory	 * @ptr pointer to the starting memory address 	 * */	void Free(void *ptr);};}#endif/****************************************************************************@File Name: buddysystem.cpp@Author: wangzhicheng@mail: 2363702560@qq.com@Created Time: Wed 15 Feb 2017 01:54:36 PM CST			   2017-02-17****************************************************************************/#include "buddysystem.h"namespace buddysystem{/* * @brief initialize the buddy system * @cap the memory capacity unit:Byte * @return true if init ok * */bool BuddySystem::Init(unsigned cap){	// check the cap	if(!PublicUtility::ToPower(cap)) 	{		cap = PublicUtility::FixToPower(cap);	}	if(cap >= PublicUtility::GetFreeRam()) return false;	m_nCapacity = cap;	m_pBasePtr = malloc(m_nCapacity);	if(!m_pBasePtr) return false;	unsigned n = (m_nCapacity << 1) - 1;		// n is the count of nodes in the full tree	int parent;	m_vecTree.resize(n);	// fill the tree	m_vecTree[0] = m_nCapacity;	for(int i = 1;i < n;i++)	{		parent = Parent(i);		m_vecTree[i] = m_vecTree[parent] >> 1;	}	return true;}/* * @brief cout the tree sequently * */void BuddySystem::ShowTree() const{	for_each(begin(m_vecTree), end(m_vecTree), [](unsigned size)	{		cout << size << endl;	});}/* * @brief allocate the memory * @size memory size(uint:byte) * @return the starting allocated memory address * */void *BuddySystem::Alloc(unsigned size){	if(!m_pBasePtr) return 0;	int index = 0;	unsigned node_size;	unsigned offset;	size = PublicUtility::FixToPower(size);	// lock lockguard	lock_guard<mutex>lockguard(m_gmutex); 	// search the fit memory block	if(m_vecTree[0] < size) return 0;	for(node_size = m_nCapacity;node_size != size;node_size >>= 1)	{		if(m_vecTree[Lchild(index)] >= size) 		{			index = Lchild(index);		}		else		{			index = Rchild(index);		}	}	m_vecTree[index] = 0;	offset = (index + 1) * node_size - m_nCapacity;	// adjust the tree	while(index)	{		index = Parent(index);		m_vecTree[index] = max(m_vecTree[Lchild(index)], m_vecTree[Rchild(index)]);	}	return (void *)((char *)m_pBasePtr + offset);}/* * @brief free the memory * @ptr pointer to the starting memory address  * */void BuddySystem::Free(void *ptr){	int index;	unsigned node_size = 1;	unsigned offset;	unsigned lsize;	unsigned rsize;	if(!m_pBasePtr) return;	offset = (char *)ptr - (char *)m_pBasePtr;			// get the offset	pointer to the memory buffer position	if(offset >= m_nCapacity) throw FreeException();	// check the offset	index = offset + m_nCapacity - 1;					// get the index pointer to the tree position	// lock	lock_guard<mutex>lockguard(m_gmutex); 	for(;m_vecTree[index];index = Parent(index)) 	{		node_size <<= 1;		if(!index) return;	}	m_vecTree[index] = node_size;	// update parent nodes	while(index) 	{		index = Parent(index);		node_size <<= 1;		lsize = m_vecTree[Lchild(index)];		rsize = m_vecTree[Rchild(index)];		if(lsize + rsize == node_size) 		{ 			m_vecTree[index] = node_size;		}		else		{ 			m_vecTree[index] = max(lsize, rsize);		}	}}}/****************************************************************************@File Name: test.cpp@Author: wangzhicheng@mail: 2363702560@qq.com@Created Time: Sat 28 Jan 2017 09:25:55 PM CST@Revision Time:2017-02-17****************************************************************************/#include "buddysystem.h"#include <thread>using namespace buddysystem;void fun0(BuddySystem &bs){	int *p = (int *)bs.Alloc(sizeof(int));	if(p) 	{		*p = 18;		cout << *p << endl;		bs.Free(p);	}}void fun1(BuddySystem &bs){	char *ptr = (char *)bs.Alloc(256);	if(ptr)	{		strcpy(ptr, "hello world...!/n");		cout << ptr << endl;		bs.Free(ptr);	}}int main(){	BuddySystem bs;	cout << bs.Init(1024) << endl;	/*	int *p = (int *)bs.Alloc(sizeof(int));	if(p) 	{		*p = 18;		cout << *p << endl;	}	char *ptr = (char *)bs.Alloc(256);	if(ptr)	{		strcpy(ptr, "hello world...!/n");		cout << ptr << endl;	}*/	thread t0(fun0, ref(bs));	thread t1(fun1, ref(bs));	t0.join();	t1.join();	return 0;}CC=g++all:	$(CC) -std=c++11 -g -o test test.cpp PublicUtility.h PublicUtility.cpp buddysystem.cpp buddysystem.h