source: libcfa/src/concurrency/snzi.hfa @ e4d7c1c

#pragma once

#include <assert.h>
#include <stdint.h>

union __snzi_val_t {
        uint64_t _all;
        struct __attribute__((packed)) {
                char cnt;
                uint64_t ver:56;
        };
};

bool cas(volatile __snzi_val_t & self, __snzi_val_t & exp, char _cnt, uint64_t _ver) {
        __snzi_val_t t;
        t.ver = _ver;
        t.cnt = _cnt;
        /* paranoid */ verify(t._all == ((_ver << 8) | ((unsigned char)_cnt)));
        return __atomic_compare_exchange_n(&self._all, &exp._all, t._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
}

bool cas(volatile __snzi_val_t & self, __snzi_val_t & exp, const __snzi_val_t & tar) {
        return __atomic_compare_exchange_n(&self._all, &exp._all, tar._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
}

void ?{}( __snzi_val_t & this ) { this._all = 0; }
void ?{}( __snzi_val_t & this, const volatile __snzi_val_t & o) { this._all = o._all; }

struct __attribute__((aligned(128))) __snzi_node_t {
        volatile __snzi_val_t value;
        struct __snzi_node_t * parent;
        bool is_root;
};

static inline void arrive( __snzi_node_t & );
static inline void depart( __snzi_node_t & );

static const int __snzi_half = -1;

//--------------------------------------------------
// Root node
static void arrive_r( __snzi_node_t & this ) {
        /* paranoid */ verify( this.is_root );
        __atomic_fetch_add(&this.value._all, 1, __ATOMIC_SEQ_CST);
}

static void depart_r( __snzi_node_t & this ) {
        /* paranoid */ verify( this.is_root );
        __atomic_fetch_sub(&this.value._all, 1, __ATOMIC_SEQ_CST);
}

//--------------------------------------------------
// Hierarchical node
static void arrive_h( __snzi_node_t & this ) {
        int undoArr = 0;
        bool success = false;
        while(!success) {
                __snzi_val_t x = { this.value };
                /* paranoid */ verify(x.cnt <= 120);
                if( x.cnt >= 1 ) {
                        if( cas( this.value, x, x.cnt + 1, x.ver ) ) {
                                success = true;
                        }
                }
                /* paranoid */ verify(x.cnt <= 120);
                if( x.cnt == 0 ) {
                        if( cas( this.value, x, __snzi_half, x.ver + 1) ) {
                                success = true;
                                x.cnt = __snzi_half;
                                x.ver = x.ver + 1;
                        }
                }
                /* paranoid */ verify(x.cnt <= 120);
                if( x.cnt == __snzi_half ) {
                        /* paranoid */ verify( this.parent);
                        arrive( *this.parent );
                        if( !cas( this.value, x, 1, x.ver) ) {
                                undoArr = undoArr + 1;
                        }
                }
        }

        for(int i = 0; i < undoArr; i++) {
                /* paranoid */ verify( this.parent );
                depart( *this.parent );
        }
}

static void depart_h( __snzi_node_t & this ) {
        while(true) {
                const __snzi_val_t x = { this.value };
                /* paranoid */ verifyf(x.cnt >= 1, "%d", x.cnt);
                if( cas( this.value, x, x.cnt - 1, x.ver ) ) {
                        if( x.cnt == 1 ) {
                                /* paranoid */ verify( this.parent );
                                depart( *this.parent );
                        }
                        return;
                }
        }
}

//--------------------------------------------------
// All nodes
static inline void arrive( __snzi_node_t & this ) {
        if(this.is_root) arrive_r( this );
        else arrive_h( this );
}

static inline void depart( __snzi_node_t & this ) {
        if(this.is_root) depart_r( this );
        else depart_h( this );
}

static inline bool query( __snzi_node_t & this ) {
        /* paranoid */ verify( this.is_root );
        return this.value._all > 0;
}

//--------------------------------------------------
// SNZI object
void  ?{}( __snzi_t & this ) {
        this.mask = 0;
        this.root = 0;
        this.nodes = 0p;
}

void  ?{}( __snzi_t & this, unsigned depth ) with( this ) {
        mask = (1 << depth) - 1;
        root = (1 << (depth + 1)) - 2;
        nodes = alloc( root + 1 );

        int width = 1 << depth;
        for(int i = 0; i < root; i++) {
                nodes[i].value._all = 0;
                nodes[i].parent = &nodes[(i / 2) + width ];
                nodes[i].is_root = false;
        }

        nodes[ root ].value._all = 0;
        nodes[ root ].parent = 0p;
        nodes[ root ].is_root = true;
}

void ^?{}( __snzi_t & this ) {
        free( this.nodes );
}

static inline void arrive( __snzi_t & this, int idx) {
        idx >>= 2;
        idx &= this.mask;
        arrive( this.nodes[idx] );
}

static inline void depart( __snzi_t & this, int idx) {
        idx >>= 2;
        idx &= this.mask;
        depart( this.nodes[idx] );
}

static inline bool query( const __snzi_t & this ) {
        return query( this.nodes[ this.root ] );
}