search, C++ (gcc) - rextester

Language: Layout:

#include <cstdarg>
#include <cstdio>
#include <cstdint>
#include <vector>
#include <ctime>
#include <random>
#include <algorithm>
#include <string.h>

using std::uintptr_t;
using std::int32_t;
using std::vector;
using std::printf;
using std::clock;
using std::min;
using std::max;

// Map and block properties.
static constexpr int32_t MAP_BITS=14;
static constexpr int32_t BLOCK_BITS=3;
static constexpr int32_t MAP_SIZE=1<<MAP_BITS;
static constexpr int32_t BLOCK_SIZE=1<<BLOCK_BITS;

// A=# index-only blocks, B=# full-raster blocks.
int32_t A=0,B=0;

// Perform optimization, storing only index in blocks, containing only one rectangle.
#define OPTIM 1

struct Rect
{
    int32_t x_min,y_min;
    int32_t x_max,y_max;
};

struct Block
{
    int32_t data[BLOCK_SIZE*BLOCK_SIZE];
};

// Index-only blocks are marked by 1 in lsb of a pointer (the rest contains index).
// Normally allocators return addresses, that are a multiple of 8.
// May fail, e. g. for custom allocator.
// There are many other ways to store this marker.

struct Map
{
    static constexpr int32_t N=1<<(MAP_BITS-BLOCK_BITS);

Map()
    {
        for(int32_t i=0;i<N*N;++i)
            blocks[i]=0;
        free_root=-1;
    };

~Map()
    {
        for(int32_t i=0;i<N*N;++i)
        {
            if(blocks[i]!=0&&(blocks[i]&1)==0)
                delete (Block*)(blocks[i]);
        }
    }

int32_t insert(const Rect &rect)
    {
        int32_t ret=-1;
        Node node;
        node.rect=rect;
        if(free_root!=-1)
        {
            ret=free_root;
            free_root=rects[free_root].next;
            rects[ret]=node;
        }
        else
        {
            ret=int32_t(rects.size());
            rects.push_back(node);
        }
        int32_t x0=rect.x_min>>BLOCK_BITS;
        int32_t y0=rect.y_min>>BLOCK_BITS;
        int32_t x1=((rect.x_max-1)>>BLOCK_BITS)+1;
        int32_t y1=((rect.y_max-1)>>BLOCK_BITS)+1;
        for(int32_t by=y0;by<y1;++by)
            for(int32_t bx=x0;bx<x1;++bx)
            {
                int bi=by*N+bx;
                if(blocks[bi]==0)
                {
#if OPTIM
                    blocks[bi]=(uintptr_t(ret)<<1)^1;
                    ++A;
#else
                    blocks[bi]=uintptr_t(new Block);
                    render({0,0,MAP_SIZE,MAP_SIZE},bx,by,*((Block*)(blocks[bi])),-1);
                    render(rect,bx,by,*((Block*)(blocks[bi])),ret);
                    ++B;
#endif
                }
                else
                {
#if OPTIM
                    if(blocks[bi]&1)
                    {
                        int32_t id=int32_t(blocks[bi]>>1);
                        blocks[bi]=uintptr_t(new Block);
                        render({0,0,MAP_SIZE,MAP_SIZE},bx,by,*((Block*)(blocks[bi])),-1);
                        render(rects[id].rect,bx,by,*((Block*)(blocks[bi])),id);
                        --A;++B;
                    }
#endif
                    render(rect,bx,by,*((Block*)(blocks[bi])),ret);
                }
            }
        return ret;
    }

void remove(int32_t id)
    {
        const Rect &rect=rects[id].rect;
        int32_t x0=rect.x_min>>BLOCK_BITS;
        int32_t y0=rect.y_min>>BLOCK_BITS;
        int32_t x1=((rect.x_max-1)>>BLOCK_BITS)+1;
        int32_t y1=((rect.y_max-1)>>BLOCK_BITS)+1;
        for(int32_t by=y0;by<y1;++by)
            for(int32_t bx=x0;bx<x1;++bx)
            {
                int bi=by*N+bx;
                if(blocks[bi]==0) continue;
                if(blocks[bi]&1)
                {
                    if(intptr_t(blocks[bi]>>1)==id)
                    {
                        blocks[bi]=0;
                        --A;
                    }
                    continue;
                }
                Block *block=((Block*)(blocks[bi]));
                render(rect,bx,by,*block,-1);
                bool empty=true;
                for(int32_t iy=0;iy<BLOCK_SIZE;++iy)
                    for(int32_t ix=0;ix<BLOCK_SIZE;++ix)
                        if(block->data[iy*BLOCK_SIZE+ix]!=-1) {empty=false;goto skip;}
                skip:;
                if(empty)
                {
                    delete (Block*)(blocks[bi]);
                    blocks[bi]=uintptr_t(0);
                    --B;
                }
            }
        rects[id].next=free_root;
        free_root=id;
    }

int32_t test(int32_t x,int32_t y)
    {
        if(x<0||y<0) return -1;
        if(x>=MAP_SIZE||y>=MAP_SIZE) return -1;
        int32_t bx=x>>BLOCK_BITS;
        int32_t by=y>>BLOCK_BITS;
        int32_t ix=x&(BLOCK_SIZE-1);
        int32_t iy=y&(BLOCK_SIZE-1);
        int bi=by*N+bx;
        if(blocks[bi]==0) return -1;
        if(blocks[bi]&1)
        {
            const Rect &rect=rects[int32_t(blocks[bi]>>1)].rect;
            return ((x>=rect.x_min)&&(x<rect.x_max)&&(y>=rect.y_min)&&(y<rect.y_max))?int32_t(blocks[bi]>>1):-1;
        }
        return ((Block*)(blocks[bi]))->data[iy*BLOCK_SIZE+ix];
    }

void render(const Rect &rect,int32_t bx,int32_t by,Block &block,int32_t value)
    {
        int32_t x0=max(bx*BLOCK_SIZE,rect.x_min);
        int32_t y0=max(by*BLOCK_SIZE,rect.y_min);
        int32_t x1=min((bx+1)*BLOCK_SIZE,rect.x_max);
        int32_t y1=min((by+1)*BLOCK_SIZE,rect.y_max);
        if(((x1-x0)&(y1-y0))==BLOCK_SIZE)
        {
            for(int32_t i=0;i<BLOCK_SIZE*BLOCK_SIZE;++i)
                block.data[i]=value;
            return;
        }
        for(int32_t y=y0;y<y1;++y)
            for(int32_t x=x0;x<x1;++x)
            {
                int32_t ix=x&(BLOCK_SIZE-1);
                int32_t iy=y&(BLOCK_SIZE-1);
                block.data[iy*BLOCK_SIZE+ix]=value;
            }
    }
    
    uintptr_t blocks[N*N]; // Pointers to blocks (or indices for index-blocks).

union Node
    {
        Rect rect;
        int32_t next;
    };

vector<Node> rects; // List of rectangles, as well as free-list.
    int32_t free_root;  // Root of free-list.
};

Map m;

int main()
{
    static const int N=500000;
    double t=0;
    t=clock();
    std::minstd_rand rng(1);
    for(int i=0;i<N;++i)
    {
        int x0=rng()%(MAP_SIZE-100);
        int y0=rng()%(MAP_SIZE-100);
        int dx=rng()%16;
        int dy=rng()%16;
        int x1=x0+dx+1;
        int y1=y0+dy+1;
        m.insert({x0,y0,x1,y1});
    }
    t=clock()-t;
    printf("Inserting %d rects.\n",N);
    printf("%.1f ns/insert.\n",1.0e+9*t/CLOCKS_PER_SEC/N);
    t=clock();
    volatile int32_t hash=0;
    for(int i=0;i<N;++i)
    {
        int x=rng()%(MAP_SIZE);
        int y=rng()%(MAP_SIZE);
        hash=hash+(m.test(x,y)!=-1);
    }
    t=clock()-t;
    printf("Testing %d points.\n",N);
    printf("%.1f ns/test.\n",1.0e+9*t/CLOCKS_PER_SEC/N);
    printf("%d hits.\n",hash);
    printf("Total:%10d\nEmpty:%10d\nIndex:%10d\nImage:%10d\n",Map::N*Map::N,Map::N*Map::N-A-B,A,B);
    printf("Size: %d byte(s).\n",Map::N*Map::N*sizeof(uintptr_t)+B*sizeof(Block));
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.63 sec, absolute running time: 0.5 sec, cpu time: 0.54 sec, memory peak: 123 Mb, absolute service time: 1,32 sec