clizFunctions.h

Go to the documentation of this file.

// clizFunctions.h  -   ClusterLizard helper functions header file

// Copyright (C) 2013, 2014 Simeon Knieling, M.Sc.
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
//

// These are internal helper functions used in the ClusterLizard library

#pragma once
#ifndef _INCLUDE_CLIZFUNCTIONS
#define _INCLUDE_CLIZFUNCTIONS

#include "clizThirdParty.h"

#include <malloc.h>

#define CHKHEAP()  (check_heap(__FILE__, __LINE__))

void check_heap(char *file, int line);

//Required precision when comparing float values
#define FLOATIFPRECISION 0.000001f
//Some big values
#define BIGFLOATVALUE 4294967269.0f
#define BIGINTVALUE 4294967269
//Element swaping required for clMedian
#define ELEM_SWAP(a,b) { register float t=(a);(a)=(b);(b)=t; }
#define ELEM_SWAPUI(a,b) { unsigned int t=(a);(a)=(b);(b)=t; }
//Element swaping required for clSort
#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
#define SWAPUI(a,b) temp2=(a);(a)=(b);(b)=temp2;
#define SWAPFFT(a,b) tempr = (a); (a) = (b); (b) = tempr
//Required for clSort: If an unsorted subarray has less elements than M, it will be sorted using straight insertion
#define M 7
#define SQR(x)  ((x)*(x))


typedef     boost::thread                                       Thread;
typedef     boost::mutex                                        Mutex;
typedef     boost::condition_variable                           ConVar;
typedef     boost::mutex::scoped_lock                           Lock;
typedef     boost::unique_lock< boost::shared_mutex >           Writelock;
typedef     boost::shared_lock< boost::shared_mutex >           Readlock;


//Memory Manager, SK

//BOOST thread library for multi-threading
#include <boost\thread.hpp>

//Mutex locks
typedef boost::mutex::scoped_lock locktype;
typedef boost::unique_lock< boost::shared_mutex > writelocktype;
typedef boost::shared_lock< boost::shared_mutex >  readlocktype;

typedef     int                 memInt;
typedef     unsigned int        memUInt;
typedef     float               memFloat;
typedef     double              memDouble;
typedef     void                memPtr;
typedef     bool                memBool;
typedef     unsigned short      memShort;
typedef     unsigned char       memByte;
typedef     unsigned short      memAdrType;

const       memShort            MAXPOOLS = 2048;
const       memShort            NUMMEMMAN = 4;
const       memShort            MEMSIZECOUNT = 19;
const       memUInt             MEMSIZE[22] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152 };
const       memUInt             POOLCAPACITY[22] = { 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 128, 128, 64, 64, 32, 16, 8, 4, 2 };
const       memShort            METASIZE = sizeof(memAdrType);

/*
In order to optimize performance, I can't search for fragments that are long enough or defragment released memory.
So the fastest way is that each chunk of memory has the same size and I just return a pointer to the next free chunk.
However, this would mean that I waste a lot of memory if only a few bytes are requested and that I can't fulfil requests of memory
that are bigger than my memory chunk. Thus I need chunks in different sizes. So I decided to make a pool for each size consisting of a certain number of
chunks. Now what if the pool is not big enough. What if more chunks of that size will be requested before some of them are released? So it should be
possible to add pools of a particular size if necessary. But what if I have a multi threaded program and both threads do frequent
memory allocation and deallocation. I can't afford to wait until the memory manager is free. Therefore, the global memory manager will have a number of
memory mangers and a manager that is currently free will be choosen to process the request.

Based on these thoughts I came up with the following structure:

GlobalMemMan    (1)->   MemMan[NUMMEMMAN]   (for each MemMan)-> SizedMemPool[NUMSIZES]  (for each size)->   MemPool[1-MAXPOOLS] (for each MemPool)-> [startAddress, size, capacity, bitArray]

Now to release memory again, I need to know where it came from. However, only the pointer to the first element is returned upon free or delete.
A solution is to actually allocate 8 Bytes more for each memory chunk (4 * short) and return a pointer to byte position 9. This way, when
a pointer is received by delete, it knows that 8 bytes before that memory, there is the ID of the Memory Manager used, 6 bytes before, there is the
ID of the Size used, 4 bytes before there is the ID of the Pool of that size used and 2 bytes before, there is the position within this pool that
needs to be released now.

*/
class MemPool
{
public:
    memInt      size;
    memPtr*     startAddress;
    memInt      capacity;
    memInt      numFree;
    memBool*    bitArray;
    memInt      nextFreePos;
    memInt      getNextFreePos();
    MemPool(memInt iSize, memInt iCapacity)
    {
        size = iSize + 4 * METASIZE;
        capacity = iCapacity;
        numFree = iCapacity;
        nextFreePos = 0;
        startAddress = malloc(size*capacity);
        while (!startAddress)
        {
            startAddress = malloc(size*capacity);
        }
        //std::cout << "Adrr" << startAddress << std::endl;
        bitArray = (memBool*)calloc(capacity, 1);
        while (!bitArray)
        {
            bitArray = (memBool*)calloc(capacity, 1);
        }
    };
    inline memPtr*      allocate()
    {
        for (int i = nextFreePos+1; i < capacity; i++)
        {
            if (!bitArray[i])
            {
                bitArray[nextFreePos] = 1;
                numFree--;
                memPtr* memAdr = (memByte*)startAddress + nextFreePos*size;
                //std::cout << startAddress << " " << nextFreePos << " " << size << " " << i << " " << numFree << std::endl;
                ((memAdrType*)memAdr)[3] = (memAdrType)nextFreePos;
                nextFreePos = i;
                return memAdr;
            }
        }
        for (int i = 0; i < nextFreePos; i++)
        {
            if (!bitArray[i])
            {
                bitArray[nextFreePos] = 1;
                numFree--;
                memPtr* memAdr = (memByte*)startAddress + nextFreePos*size;
                //std::cout << startAddress << " " << nextFreePos << " " << size << " " << i << " " << numFree << std::endl;
                ((memAdrType*)memAdr)[3] = (memAdrType)nextFreePos;
                nextFreePos = i;
                return memAdr;
            }
        }
        if (numFree < 1)
        {
            return NULL;
        }
        //std::cout << "PROBLEM INCOMMING!!!" << std::endl;
        if (bitArray[nextFreePos])
        {
            //std::cout << "WTF THIS SHOULD NOT HAPPEN!" << std::endl;
            //getchar();
        }
        numFree--;
        //std::cout << startAddress << " " << nextFreePos << " " << size << " " << numFree << std::endl;
        bitArray[nextFreePos] = 1;
        memPtr* memAdr = (memByte*)startAddress + nextFreePos*size;
        ((memAdrType*)memAdr)[3] = (memAdrType)nextFreePos;
        nextFreePos = -1;
        return memAdr;
    }
    inline void free(memPtr* memAdr)
    {
        memAdrType* adrPos = (memAdrType*)memAdr - 1;
        memAdrType freePos = (*adrPos);
        bitArray[freePos] = 0;
        nextFreePos = freePos;
        numFree++;
        //std::cout << startAddress << " " << nextFreePos << " " << size << " " << numFree << std::endl;
    };
    ~MemPool()
    {
        ::free(startAddress);
        ::free(bitArray);
    };
};

class SizedMemPool
{
public:
    MemPool*    pool;
    memInt      size;
    memInt      numPools;
    memInt      poolCapacity;
    memInt      poolInUse;
    SizedMemPool(memInt iSize, memInt iPoolCapacity)
    {
        size = iSize;
        poolCapacity = iPoolCapacity;
        numPools = 1;
        poolInUse = 0;
        pool = (MemPool*)malloc(sizeof(MemPool)*MAXPOOLS);
        new(&pool[0]) MemPool(size, poolCapacity);
    };
    inline memPtr*      allocate()
    {
        if (pool[poolInUse].numFree > 0)
        {
            memPtr* memAdr = pool[poolInUse].allocate();
            ((memAdrType*)memAdr)[2] = (memAdrType)poolInUse;
            return memAdr;
        }
        memInt oldPoolInUse = poolInUse;
        for (int i = poolInUse+1; i < numPools; i++)
        {
            if (pool[i].numFree > 0)
            {
                poolInUse = i;
                memPtr* memAdr = pool[poolInUse].allocate();
                ((memAdrType*)memAdr)[2] = (memAdrType)poolInUse;
                return memAdr;
            }
        }
        for (int i = 0; i < poolInUse; i++)
        {
            if (pool[i].numFree > 0)
            {
                poolInUse = i;
                memPtr* memAdr = pool[poolInUse].allocate();
                ((memAdrType*)memAdr)[2] = (memAdrType)poolInUse;
                return memAdr;
            }
        }
        //CHKHEAP();
        //std::cout << numPools << std::endl;
        this->spawnNewPool();
        //Was ist wenn max pool erreicht ist!?
        memPtr* memAdr = pool[poolInUse].allocate();
        ((memAdrType*)memAdr)[2] = (memAdrType)poolInUse;
        return memAdr;
    }
    inline void free(memPtr* memAdr)
    {
        memAdrType* adrPool = (memAdrType*)memAdr - 2;
        memAdrType freePool = (*adrPool);
        pool[freePool].free(memAdr);
    };
    inline void spawnNewPool()
    {
        if (numPools < MAXPOOLS)
        {
            new(&(pool[numPools])) MemPool(size, poolCapacity);
            poolInUse = numPools++;
        }
        //std::cout << size << " " << numPools << " " << MAXPOOLS << std::endl;
    };
    ~SizedMemPool()
    {
        for (int i = 0; i < numPools; i++)
        {
            pool[i].~MemPool();
        }
        ::free(pool);
    };
};

class MemoryManager
{
public:
    memBool     isFree;
    SizedMemPool    *sizedPools;
    MemoryManager()
    {
        isFree = 1;
        sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*MEMSIZECOUNT);
        while (!sizedPools)
        {
            sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*MEMSIZECOUNT);
        }
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            new(&sizedPools[i])  SizedMemPool(MEMSIZE[i], POOLCAPACITY[i]);
        }
    };
    MemoryManager(int memSizes)
    {
        isFree = 1;
        sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*memSizes);
        while (!sizedPools)
        {
            sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*memSizes);
        }
        for (int i = 0; i < memSizes; i++)
        {
            new(&sizedPools[i])  SizedMemPool(MEMSIZE[i], POOLCAPACITY[i]);
        }
    };
    ~MemoryManager()
    {
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            sizedPools[i].~SizedMemPool();
        }
        ::free(sizedPools);
    };
    inline memPtr* allocate(size_t  numBytes)
    {
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            if (numBytes < MEMSIZE[i])
            {
                memPtr* memAdr = sizedPools[i].allocate();
                ((memAdrType*)memAdr)[1] = (memAdrType)i;
                memAdr = (memByte*)memAdr + 4 * METASIZE;
                return memAdr;
            }
        }

        std::cout << "malloc" << std::endl;

        memPtr* memAdr = malloc(numBytes + 4 * METASIZE);
        while (!memAdr)
        {
            memAdr = malloc(numBytes + 4 * METASIZE);
        }
        ((memAdrType*)memAdr)[1] = (memAdrType)MEMSIZECOUNT;
        memAdr = (memByte*)memAdr + 4 * METASIZE;
        return memAdr;
    };
    inline void free(memPtr* memAdr)
    {
        memAdrType* adrSizePool = (memAdrType*)memAdr - 3;
        memAdrType freeSizePool = (*adrSizePool);
        if (freeSizePool < MEMSIZECOUNT)
        {
            sizedPools[freeSizePool].free(memAdr);
        }
        else
        {
            //std::cout << "free" << std::endl;
            memAdr = (memByte*)memAdr - 4 * METASIZE;
            //std::cout << memAdr << std::endl;
            ::free(memAdr);
        }
    };
};

class MemoryManagerPart
{
public:
    memBool     isFree;
    SizedMemPool    *sizedPools;
    MemoryManagerPart()
    {
        isFree = 1;
        sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*MEMSIZECOUNT);
        while (!sizedPools)
        {
            sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*MEMSIZECOUNT);
        }
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            new(&sizedPools[i])  SizedMemPool(MEMSIZE[i], POOLCAPACITY[i]);
        }
    };
    MemoryManagerPart(int memSizes)
    {
        isFree = 1;
        sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*memSizes);
        while (!sizedPools)
        {
            sizedPools = (SizedMemPool*)malloc(sizeof(SizedMemPool)*memSizes);
        }
        for (int i = 0; i < memSizes; i++)
        {
            new(&sizedPools[i])  SizedMemPool(MEMSIZE[i], POOLCAPACITY[i]);
        }
    };
    ~MemoryManagerPart()
    {
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            sizedPools[i].~SizedMemPool();
        }
        ::free(sizedPools);
    };
    inline memPtr* allocate(size_t  numBytes)
    {
        for (int i = 0; i < MEMSIZECOUNT; i++)
        {
            if (numBytes < MEMSIZE[i])
            {
                memPtr* memAdr = sizedPools[i].allocate();
                ((memAdrType*)memAdr)[1] = (memAdrType)i;
                return memAdr;
            }
        }

        std::cout << "malloc" << std::endl;

        memPtr* memAdr = malloc(numBytes + 4 * METASIZE);
        while (!memAdr)
        {
            memAdr = malloc(numBytes + 4 * METASIZE);
        }
        ((memAdrType*)memAdr)[1] = (memAdrType)MEMSIZECOUNT;
        memAdr = (memByte*)memAdr + 4 * METASIZE;
        return memAdr;
    };
    inline void free(memPtr* memAdr)
    {
        memAdrType* adrSizePool = (memAdrType*)memAdr - 3;
        memAdrType freeSizePool = (*adrSizePool);
        if (freeSizePool < MEMSIZECOUNT)
        {
            sizedPools[freeSizePool].free(memAdr);
        }
        else
        {
            //std::cout << "free" << std::endl;
            memAdr = (memByte*)memAdr - 4 * METASIZE;
            //std::cout << memAdr << std::endl;
            ::free(memAdr);
        }
    };
};

class GlobalMemoryManager
{
public:
    boost::mutex    memManMutex;
    MemoryManagerPart   *memMan;
    GlobalMemoryManager()
    {
        memMan = (MemoryManagerPart*)malloc(NUMMEMMAN*sizeof(MemoryManagerPart));
        while (!memMan)
        {
            memMan = (MemoryManagerPart*)malloc(NUMMEMMAN*sizeof(MemoryManagerPart));
        }
        for (int i = 0; i < NUMMEMMAN; i++)
        {
            new(&memMan[i]) MemoryManagerPart();
        }
        //CHKHEAP();
    }
    inline memPtr* allocate(size_t  numBytes)
    {
        memShort        memManInUse = 0;
        while (!memManMutex.try_lock());
        for (int i = 0; i < NUMMEMMAN; i++)
        {
            if (memMan[i].isFree == 1)
            {
                memManInUse = i;
                memMan[i].isFree = 0;
                break;
            }
            else if (i == NUMMEMMAN - 1)
            {
                //All Busy
                i = 0;
            }
        }
        
        //lockProtection.unlock();
        //std::cout << "#";

        //CHKHEAP();
        //std::cout << numBytes << std::endl;
        memPtr* memAdr = memMan[memManInUse].allocate(numBytes);
        memManMutex.unlock();
        ((memAdrType*)memAdr)[0] = (memAdrType)memManInUse;
        memAdr = (memByte*)memAdr + 4 * METASIZE;
        memMan[memManInUse].isFree = 1;
        //CHKHEAP();
        //memManMutex.unlock();
        return memAdr;
    }
    inline void free(memPtr* memAdr)
    {
        
        //CHKHEAP();
        memAdrType* adrMemMan = (memAdrType*)memAdr - 4;
        memAdrType freeMemMan = (*adrMemMan);
        while (!memManMutex.try_lock());
        memMan[freeMemMan].free(memAdr);
        //CHKHEAP();
        memManMutex.unlock();
    };
};

extern GlobalMemoryManager gMemMan;



int clBinomial(int n, int k);

float clSign(float x);

int clMax(int a, int b);

void clSort(float vec[], int n);

void clSort(unsigned int vec[], int n);

void clSortTwo(unsigned int vec[], unsigned int vec2[], int n);

void clSortTwo(float vec[], float vec2[], int n);

void clSortTwo(float vec[], unsigned int vec2[], int n);

float clMedian(float vec[], int n);

float clMedian(unsigned int vec[], int n);

float clMean(float arr[], uint32_t n);

double clMean(double arr[], uint32_t n);

float clStd(float arr[], uint32_t n);

inline float clStdWithMean(float arr[], uint32_t n, float mean);

float *clAbs(float arr[], uint32_t n);

uint32_t clMaxIndex(float arr[], uint32_t begin, uint32_t end);

uint32_t clMaxAbsIndex(float arr[], uint32_t begin, uint32_t end);

uint32_t clMinIndex(float arr[], uint32_t begin, uint32_t end);

inline float clErfc(float x);

float clKSTest(float arr[], uint32_t n, MemoryManager &memMan);

void clFindHighestIndices(float arr[], uint32_t n, uint32_t output[], uint32_t numindices, MemoryManager &memMan);

void clFindLowestIndices(float arr[], uint32_t n, uint32_t output[], uint32_t numindices, MemoryManager &memMan);


void clSplineGetY2(float y[], int n, float y2[], MemoryManager &memMan);

float clSplineInterp(float y[], float y2[], float x);


void clHaarWaveDecWithOffset(float spikes[], unsigned int size, uint8_t scales, float output[], uint32_t offset, MemoryManager &memMan);

void clXCorr(float *X, float *Y, unsigned int n, int maxshift, float *&output, MemoryManager &memMan);

void clXCorr(double *X, double *Y, unsigned int n, int maxshift, double *&output, MemoryManager &memMan);

#endif