<repo_name>qijuweni/WbuddyDemo<file_sep>/src/Salloc.cpp
/*************************************************************************
	> File Name: Salloc.h
	> Author: qijunwei
	> Mail: <EMAIL>
	> Created Time: Mon 12 Dec 2016 01:50:59 PM CST

 ************************************************************************/

#include "Salloc.h"
#include <string.h>
#include <stdlib.h>

SallocManager* Init(int orderNums, unsigned char **pSallocArray)
{
    SallocManager *pSallocManager = (SallocManager*)malloc(sizeof(SallocManager));

    pSallocManager->orderNums_ = orderNums;
    pSallocManager->pSallocArray_ = pSallocArray;
    return pSallocManager;
}

void SetBit(unsigned char *pChar, int bitIndex, bool bIsSet1 = true)
{
    unsigned char mask = 1;
    mask = mask << bitIndex;

    if(bIsSet1 == true)
    {
        *pChar = (*pChar) | mask;
    }
    else
    {
        mask = ~mask;
        *pChar = (*pChar) & mask;
    }
}

void SetBits(unsigned char *pChar, int endBitIndex, bool bIsSet1 = true)
{
    unsigned char mask = 1;
    mask = (mask << (endBitIndex + 1)) - 1;

    if(bIsSet1 == true)
    {
        *pChar = (*pChar) | mask;
    }
    else
    {
        unsigned char tmp = 0xff;
        mask = tmp - mask;
        *pChar = (*pChar) & mask;
    }

}

int IsFirstParaMax(unsigned char *pFirst, unsigned char *pScend, int charNums)
{
    for(int i = charNums - 1; i >= 0; i--)
    {
        if((unsigned char)pFirst[i] > (unsigned char)pScend[i])
            return 1;
        else if((unsigned char)pFirst[i] < (unsigned char)pScend[i])
            return -1;
    }

    return 0;
}

void SetChunkAllocted(SallocManager *pSallocManager, int order, unsigned int chunkNumb, bool isAllocted, unsigned char *pSetSalloc)
{
    unsigned char *pSalloc = pSallocManager->pSallocArray_[order];
    int perChunkBits = order + 1;
    int modByChar = perChunkBits % 8;
    int perChunkSallocSpaceBytes = -1;

    if(modByChar != 0)
        perChunkSallocSpaceBytes = perChunkBits / 8 + 1;
    else
        perChunkSallocSpaceBytes = perChunkBits / 8;

    unsigned long OffsetByChar = perChunkSallocSpaceBytes * chunkNumb;
    unsigned char *pChunkSalloc = pSalloc + OffsetByChar;

    unsigned int broChunkNumb = -1;
    unsigned char *pBroChunkSalloc = NULL;
    int result = -2;

    if(order != pSallocManager->orderNums_ - 1)
    {
        broChunkNumb = (chunkNumb % 2) ? (chunkNumb - 1):(chunkNumb + 1);
        OffsetByChar = broChunkNumb * perChunkSallocSpaceBytes;
        pBroChunkSalloc =  pSalloc + OffsetByChar;

        result = IsFirstParaMax(pChunkSalloc, pBroChunkSalloc, perChunkSallocSpaceBytes);
    }

    if(pSetSalloc != NULL)
    {
//        strncpy(pChunkSalloc, pSetSalloc, pSetSallocLength);因为pSetSalloc 没多大，所以不必用函数
        int pSetSallocLength = 0;
        if((perChunkBits - 1) % 8 == 0)
            pSetSallocLength = perChunkSallocSpaceBytes -1;
        else
            pSetSallocLength = perChunkSallocSpaceBytes;


        if(pSetSalloc[pSetSallocLength - 1] == 0 )//意味着要修改最高位为1
        {
            if(pSetSallocLength == perChunkSallocSpaceBytes - 1)
            {
                if(isAllocted)
                    pChunkSalloc[perChunkSallocSpaceBytes - 1] =  1;
                else
                {
                    if(pChunkSalloc[perChunkSallocSpaceBytes -2] == 0)
                        pChunkSalloc[perChunkSallocSpaceBytes - 1] =  0;
                }

            }
            else
            {
                int bitSetIndex = -1;
                if(modByChar == 0)
                    bitSetIndex = 7;
                else
                    bitSetIndex = modByChar - 1;

                if(isAllocted)
                    SetBit(&pChunkSalloc[perChunkSallocSpaceBytes - 1], bitSetIndex, true);
                else if(pChunkSalloc[perChunkSallocSpaceBytes - 1] == (1 << bitSetIndex))
                    SetBit(&pChunkSalloc[perChunkSallocSpaceBytes - 1], bitSetIndex, false);
            }
        }

        for(int i = pSetSallocLength - 2; i >= 0; i--)
        {
            if(pChunkSalloc[i] == 0 && pSetSalloc[i] == 0)
            {
                break;
            }

            pChunkSalloc[i] = pSetSalloc[i];
        }

        if(pSetSallocLength == perChunkSallocSpaceBytes)
        {
            if(isAllocted)
           {
                pChunkSalloc[pSetSallocLength - 1] =  (pChunkSalloc[pSetSallocLength - 1] | pSetSalloc[pSetSallocLength - 1]);//=的话会有bug
           }
           else
           {
                unsigned char mask = 1;
                int tmp = 0;

                if(modByChar == 0)
                   tmp = 7;
                else
                   tmp = modByChar - 1;

                mask = (unsigned char)0xff - ((mask << tmp) - 1);
                pChunkSalloc[pSetSallocLength - 1] =  (pChunkSalloc[pSetSallocLength - 1] & (pSetSalloc[pSetSallocLength - 1] | mask));//=的话会有bug
            }
        }
        else
            pChunkSalloc[pSetSallocLength - 1] = pSetSalloc[pSetSallocLength - 1];

    }
    else
    {
        int setCharNum = -1;
        if(modByChar == 1)
        {
            if(isAllocted)
                pChunkSalloc[perChunkSallocSpaceBytes - 1] = 1;
            else
                pChunkSalloc[perChunkSallocSpaceBytes - 1] = 0;
        }
        else
        {
            int bitSetIndex = -1;
            if(modByChar == 0)
                bitSetIndex = 7;
            else
                bitSetIndex = modByChar - 1;

            if(isAllocted)
                SetBits(&pChunkSalloc[perChunkSallocSpaceBytes - 1], bitSetIndex, true);
            else
                SetBits(&pChunkSalloc[perChunkSallocSpaceBytes - 1], bitSetIndex, false);
        }

        setCharNum = perChunkSallocSpaceBytes - 1;
        for(int i = 0; i < setCharNum; i++)
        {
            if(isAllocted)
                pChunkSalloc[i] = 0xff;
            else
                pChunkSalloc[i] = 0x0;

        }
    }

    if(order != pSallocManager->orderNums_ - 1)
    {
        if(isAllocted)
        {
            if(result == -1 || (result == 0 && pBroChunkSalloc[perChunkSallocSpaceBytes - 1] == 0 ))
            {
                unsigned char *pUpSetChunk = pBroChunkSalloc;
                if(result != 0 && pSetSalloc != NULL)
                {
                    result = IsFirstParaMax(pChunkSalloc, pBroChunkSalloc, perChunkSallocSpaceBytes);

                    if(result == -1)
                        pUpSetChunk = pChunkSalloc;
                }
                SetChunkAllocted(pSallocManager, order + 1, chunkNumb / 2, isAllocted, pUpSetChunk);
            }
        }
        else
        {
            if(result == 1)
            {
                result = IsFirstParaMax(pChunkSalloc, pBroChunkSalloc, perChunkSallocSpaceBytes);

                if(result != 1)
                {
                    if(!(result == 0 && (pBroChunkSalloc[perChunkSallocSpaceBytes - 1] != 0)))
                        SetChunkAllocted(pSallocManager, order + 1, chunkNumb / 2, isAllocted, pChunkSalloc);
                }

            }
            else //我原来都比你小或者等于你，释放后肯定比你更小了
            {
                SetChunkAllocted(pSallocManager, order + 1, chunkNumb / 2, isAllocted, pChunkSalloc);
            }
        }
    }
}
<file_sep>/include/Salloc.h
/*************************************************************************
	> File Name: Salloc.h
	> Author: qijunwei
	> Mail: <EMAIL>
	> Created Time: Mon 12 Dec 2016 01:50:59 PM CST

 ************************************************************************/
#ifndef SALLOC_H_
#define SALLOC_H_

#include "stdio.h"

struct SallocManager
{
    int orderNums_;
    unsigned char **pSallocArray_;
};

struct SallocManager* Init(int orderNums, unsigned char **pSallocArray);

void SetBit(unsigned char *pChar, int bitIndex, bool bIsSet1);

void SetBits(unsigned char *pChar, int endBitIndex, bool bIsSet1);

int IsFirstParaMax(unsigned char *pFirst, unsigned char *pScend, int charNums);

void SetChunkAllocted(SallocManager *pSallocManager, int order, unsigned int chunkNumb, bool isAllocted, unsigned char *pSetSalloc = NULL);
#endif
<file_sep>/test/SallocTester.c
/*************************************************************************
	> File Name: SallocTester.c
	> Author: qijunwei
	> Mail: <EMAIL>
	> Created Time: Mon 12 Dec 2016 10:45:11 PM CST

 ************************************************************************/
#include "stdio.h"
#include <gtest/gtest.h>
#include "Salloc.h"
#include <string.h>

#define PAGE_SIZE 4096
#define SPACE  4096 * 256 * 4 * 256

static struct SallocManager* SallocManagerForTest()
{
    int MaxChunkNumb = SPACE / PAGE_SIZE;
    int orderNums = 1;

    int tmpChunkNumb = MaxChunkNumb;
    while(tmpChunkNumb/2 != 0)
    {
        orderNums++;
        tmpChunkNumb = tmpChunkNumb / 2;
    }
    unsigned char **pSallocArr = (unsigned char**)malloc(sizeof(char*) * orderNums);

    for(int i = 0; i < orderNums; i++)
    {
        int bits = i + 1;
        int perSallocSize = (bits % 8 ) ? bits / 8 + 1 : bits / 8;
        pSallocArr[i] = (unsigned char*)malloc(perSallocSize * MaxChunkNumb);
        memset(pSallocArr[i], 0, perSallocSize * MaxChunkNumb);
        MaxChunkNumb = MaxChunkNumb / 2;
    }

    return Init(orderNums, pSallocArr);
}

//2^x个page时，则 orderNums = x + 1, 例如一个page对应的orderNum为1，对应的位向量为1位

static SallocManager* pManager = SallocManagerForTest();

TEST(Salloc, SetBit)
{
    unsigned char a = 6;
    SetBit(&a, 3, true);
    EXPECT_EQ(a, 14);

    unsigned char b = 0;
    SetBit(&b, 0, true);
    EXPECT_EQ(b, 1);

    unsigned char c = 7;
    SetBit(&c, 7, true);
    EXPECT_EQ(c, (unsigned char)135);

    unsigned char f = 2;
    SetBit(&f, 0, true);
    EXPECT_EQ(f, (unsigned char)3);

    unsigned char d = 15;
    SetBit(&d, 2, false );
    EXPECT_EQ(d, 11);

    unsigned char e = 255;
    SetBit(&e, 7, false);
    EXPECT_EQ(e,255 - 128);

    unsigned char g = 255;
    SetBit(&g, 0, false);
    EXPECT_EQ(g, 255 - 1);
}

TEST(Salloc, SetBits)
{
    unsigned char a = 6;
    SetBits(&a, 3, true);
    EXPECT_EQ(a, 15);

    unsigned char b = 0;
    SetBits(&b, 0, true);
    EXPECT_EQ(b, 1);

    unsigned char c = 7;
    SetBits(&c, 7, true);
    EXPECT_EQ(c, (unsigned char)255);

    unsigned char d = 255;
    SetBits(&d, 7, false);
    EXPECT_EQ(d, 0);

    unsigned char e = 23;
    SetBits(&e, 2, false);
    EXPECT_EQ(e, 16);

    unsigned char f = 23;
    SetBits(&f, 0, false);
    EXPECT_EQ(f, 22);

    unsigned char g = 22;
    SetBits(&g, 0, true);
    EXPECT_EQ(g, 23);

}

TEST(Salloc, IsFirstParaMax)
{
    unsigned char a[2] = {0};
    a[1] = (unsigned char)128 + 64;
    unsigned char b[2] = {0};
    b[1] = (unsigned char)128;

    EXPECT_EQ(1,IsFirstParaMax(a, b, 2));

    a[0] = 12;
    b[0] = 8;
    EXPECT_EQ(1,IsFirstParaMax(a, b, 1));
}


TEST(Salloc, SetChunkAllocted)
{
//这个test是在 SetChunkAllocted 没有加上递归修改功能的测试代码
 /*   SetChunkAllocted(pManager, 2, 3, true);
    EXPECT_EQ(pManager->pSallocArray_[2][3], 7);

    SetChunkAllocted(pManager, 0, 14, true);
    EXPECT_EQ(pManager->pSallocArray_[0][14], 1);

    SetChunkAllocted(pManager, 1, 5, true);
    EXPECT_EQ(pManager->pSallocArray_[1][5], 3);

    SetChunkAllocted(pManager, 3, 1, true);
    EXPECT_EQ(pManager->pSallocArray_[3][1], 15);

    SetChunkAllocted(pManager, 9, 0, true);//因为order9对应10bit的位向量，所以一个位向量占两个字节
    EXPECT_EQ(pManager->pSallocArray_[9][1], 3);//下标越大，代表越高位的字节
    EXPECT_EQ(pManager->pSallocArray_[9][0], (unsigned char)255);

    SetChunkAllocted(pManager, 8, 1, true);//同上
    EXPECT_EQ(pManager->pSallocArray_[8][3], 1);
    EXPECT_EQ(pManager->pSallocArray_[8][2], (unsigned char)255);

    SetChunkAllocted(pManager, 4, 5, true);//模拟的是order4的第6个组（下标为5）被用，然后第5个组可以用，这时候需要向上更新
    SetChunkAllocted(pManager, 5, 2, &pManager->pSallocArray_[4][4]);
    EXPECT_EQ(pManager->pSallocArray_[5][2], (unsigned char)32);

    SetChunkAllocted(pManager, 10, 0, &pManager->pSallocArray_[9][2]);//模拟order为9的第一个组（下标为0，位向量占两个字节）被用了，第二组可用，向上更新
    EXPECT_EQ(pManager->pSallocArray_[10][1], (unsigned char)4);
    EXPECT_EQ(pManager->pSallocArray_[10][0], (unsigned char)0);

    SetChunkAllocted(pManager, 7, 2, true);//模拟的是order7的第3个组（下标为2）被用，然后第4个组可以用，这时候需要向上更新
    SetChunkAllocted(pManager, 8, 1, &pManager->pSallocArray_[7][3]);//为了走到if(pSetSallocLength == perChunkSallocSpaceBytes - 1)
    EXPECT_EQ(pManager->pSallocArray_[8][3], (unsigned char)1);
    EXPECT_EQ(pManager->pSallocArray_[8][2], (unsigned char)0);
*/

    SallocManager *pSalloc = SallocManagerForTest();

    SetChunkAllocted(pSalloc, 0, 0, true);

    unsigned char value = 1;
    int num = pSalloc->orderNums_;
    for(int i = 0; i < 8; i++)
    {
        if( i >= num )
            break;

        EXPECT_EQ(pSalloc->pSallocArray_[i][0], (unsigned char)value);
        value *= 2;
    }

    value = 1;
    for(int i = 8; i < 16; i++)
    {
        if( i >= num )
            break;

        EXPECT_EQ(pSalloc->pSallocArray_[i][1], (unsigned char)value);
        EXPECT_EQ(pSalloc->pSallocArray_[i][0], (unsigned char)0);
        value *= 2;
    }

    value = 1;
    for(int i = 16; i < 24; i++)
    {
        if( i >= num )
            break;

        EXPECT_EQ(pSalloc->pSallocArray_[i][2], (unsigned char)value);
        EXPECT_EQ(pSalloc->pSallocArray_[i][1], (unsigned char)0);
        EXPECT_EQ(pSalloc->pSallocArray_[i][0], (unsigned char)0);

        value *= 2;
    }

    printf("ordr num is %d\n", num);

    SetChunkAllocted(pSalloc, 2, 1, true);
    EXPECT_EQ(pSalloc->pSallocArray_[3][0], (unsigned char)12);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)16);
/*
    SetChunkAllocted(pSalloc, 3, 1, true);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)28);
    EXPECT_EQ(pSalloc->pSallocArray_[5][0], (unsigned char)32);
*/
    SetChunkAllocted(pSalloc, 2, 2, true);
    EXPECT_EQ(pSalloc->pSallocArray_[3][1], (unsigned char)8);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)24);

    SetChunkAllocted(pSalloc, 4, 1, true);
    EXPECT_EQ(pSalloc->pSallocArray_[5][0], (unsigned char)56);
    EXPECT_EQ(pSalloc->pSallocArray_[6][0], (unsigned char)64);

    SetChunkAllocted(pSalloc, 7, 1, true);
    EXPECT_EQ(pSalloc->pSallocArray_[8][0], (unsigned char)128);
    EXPECT_EQ(pSalloc->pSallocArray_[8][1], (unsigned char)1);

 /*   SetChunkAllocted(pSalloc, 7, 3, true);
    EXPECT_EQ(pSalloc->pSallocArray_[8][3], (unsigned char)1);
    EXPECT_EQ(pSalloc->pSallocArray_[8][2], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[9][1], (unsigned char)3);
*/
    SetChunkAllocted(pSalloc, 8, 1, true);
    EXPECT_EQ(pSalloc->pSallocArray_[9][0], (unsigned char)128);
    EXPECT_EQ(pSalloc->pSallocArray_[9][1], (unsigned char)3);

    SetChunkAllocted(pSalloc, 0, 0, false);
    EXPECT_EQ(pSalloc->pSallocArray_[0][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[1][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[2][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[3][0], (unsigned char)8);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)24);
    EXPECT_EQ(pSalloc->pSallocArray_[5][0], (unsigned char)56);

    SetChunkAllocted(pSalloc, 2, 1, false);
    EXPECT_EQ(pSalloc->pSallocArray_[0][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)16);
    EXPECT_EQ(pSalloc->pSallocArray_[5][0], (unsigned char)48);
    EXPECT_EQ(pSalloc->pSallocArray_[6][0], (unsigned char)64);

    SetChunkAllocted(pSalloc, 7, 1, false);
    EXPECT_EQ(pSalloc->pSallocArray_[8][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[8][1], (unsigned char)1);
    EXPECT_EQ(pSalloc->pSallocArray_[9][0], (unsigned char)0);

    SetChunkAllocted(pSalloc, 8, 1, false);
    EXPECT_EQ(pSalloc->pSallocArray_[9][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[9][1], (unsigned char)2);
    EXPECT_EQ(pSalloc->pSallocArray_[10][1], (unsigned char)4);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)16);

    SetChunkAllocted(pSalloc, 2, 2, false);
    EXPECT_EQ(pSalloc->pSallocArray_[3][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[3][1], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[4][0], (unsigned char)0);
    EXPECT_EQ(pSalloc->pSallocArray_[5][0], (unsigned char)32);


    SetChunkAllocted(pSalloc, 4, 1, false);

    for(int i = 0; i < pSalloc->orderNums_ ; i++)
    {
        EXPECT_EQ(pSalloc->pSallocArray_[i][0], (unsigned char)0);
    }
}

<file_sep>/include/CLChunkGroup.h
/*************************************************************************
	> File Name: ChunkGroup.h
	> Author: qijunwei
	> Mail: <EMAIL>
	> Created Time: Sun 11 Dec 2016 06:44:13 PM CST

 ************************************************************************/
#ifndef CHUNKGROUP_H_
#define CHUNKGROUP_H_

class ChunkGroup
{
    public:
        ChunkGroup(int order, unsigned int chunkNum);
        ~ChunkGroup();
        unsigned int GetChunk();

    private:
        unsigned int *pulArrayOfChunkUsedCount;
        char *pcGroupSalloc;
}

#endif
<file_sep>/include/ChunkGroup.h
/*************************************************************************
	> File Name: ChunkGroup.h
	> Author: qijunwei
	> Mail: <EMAIL>
	> Created Time: Sun 11 Dec 2016 07:24:35 PM CST

 ************************************************************************/
#ifndef CHUNKGROUP_H_
#define CHUNKGROUP_H_

struct ChunkGroup
{
    unsigned int *pulArrayOfChunkUsedCount;
    char *pcGroupSalloc;
    int order;
    unsigned int chunkNum;
};

ChunkGroup* InitChunkGroup(int order, unsigned int chunkNum);

unsigned int GetFitChunkNumbInBuddyChunks(ChunkGroup *pChunkGroup, unsigned int beginChunkNumb,int wantedOrder);


void SetChunkUesd(ChunkGroup *pChunkGroup, unsigned int ChunkNumb);

#endif
<file_sep>/test/CMakeLists.txt
PROJECT(main)
CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
set(CMAKE_C_COMPILER "g++")
include_directories( ../include /home/qijunwei/googletest/googletest/include)
add_definitions(-g)
#link_directories(../lib/gtest-1.7.0)
AUX_SOURCE_DIRECTORY(. dir_srcs)
aux_source_directory(../src dir_srcs)
#option (cover_test "cover_test build" ON)
#if(cover_test)
#	set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}  -fprofile-arcs -ftest-coverage")
#endif()

#OPTION (ENABLE_COVERAGE "Use gcov" ON)
#MESSAGE(STATUS ENABLE_COVERAGE=${ENABLE_COVERAGE})
#IF(ENABLE_COVERAGE)
	set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage")
#set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -fprofile-arcs -ftest-coverage")
#ENDIF()
add_executable(main ${dir_srcs})
#target_compile_options(main PRIVATE -fprofile-arcs -ftest-coverage) 
#这句话必须放在add_executable的后面
target_link_libraries(main libgtest.a libgtest_main.a pthread)
