/*
 * Lugh: A utility function library
 * stmtx.c: Software transactional memory
 *
 * Copyright (c) 2012 Patrick McFarland <pmcfarland@adterrasperaspera.com>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "lugh.h"

typedef struct {
    void *dst;
    void *src;

    size_t len;
    size_t size;
} lugh_stmtx_write_data_t;

typedef struct {
    lugh_stmtx_write_data_t *data;

    unsigned long count;
    unsigned long size;
} lugh_stmtx_write_t;

static inline void lugh_stmtx_write_init(lugh_stmtx_write_t *write) {
    write->data = lugh_alloc(sizeof(lugh_stmtx_write_data_t) * 16);
    write->count = 0;
    write->size = 16;
}

static inline void lugh_stmtx_write_deinit(lugh_stmtx_write_t *write) {
    for(size_t i = 0; i < write->size; i++)
        if(write->data[i].src != NULL)
            lugh_free(write->data[i].src);

    lugh_free(write->data);
}

static inline void lugh_stmtx_write_add(lugh_stmtx_write_t *write, void *dst, void *src, size_t len) {
    size_t i;

    for(i = 0; i < write->count; i++) {
        if(write->data[i].dst == dst) {
            break;
        }
    }

    if(write->data[i].dst != dst)
        write->count++;

    if(write->count == write->size) {
        lugh_stmtx_write_data_t *old_write = write->data;

        write->size *= 2;

        write->data = lugh_alloc(sizeof(lugh_stmtx_write_data_t *) * write->size);
        memcpy(write->data, old_write, sizeof(lugh_stmtx_write_data_t *) * write->size);

        lugh_free(old_write);
    }

    write->data[write->count].dst = dst;

    if(write->data[write->count].size < len) {
        lugh_free(write->data[write->count].src);
        write->data[write->count].src = NULL;
    }

    if(write->data[write->count].src == NULL) {
        write->data[write->count].src = lugh_alloc(len);
        write->data[write->count].size = len;
    }

    memcpy(write->data[write->count].src, src, len);

    write->data[write->count].len = len;
}

static inline void lugh_stmtx_write_commit(lugh_stmtx_write_t *write) {
    for(size_t i = 0; i < write->count; i++) {
        memcpy(write->data[i].dst, write->data[i].src, write->data[i].len);
    }
}

static inline void lugh_stmtx_write_clear(lugh_stmtx_write_t *write) {
    for(size_t i = 0; i < write->count; i++)
        write->data[i].dst = NULL;

    write->count = 0;
}

typedef struct {
    uint64_t a;
    uint64_t b;
} lugh_stmtx_filter_t;

static inline void lugh_stmtx_filter_init(lugh_stmtx_filter_t *filter) {
    filter->a = 0;
    filter->b = 0;
}

static inline void lugh_stmtx_filter_add(lugh_stmtx_filter_t *filter, void *addr) {
    uint64_t h1 = 0x43616B653D4C6965LLU;
    uint64_t h2 = h1;

  uint64_t c1 = 0x87c37b91114253d5LLU;
  uint64_t c2 = 0x4cf5ad432745937fLLU;

    uint64_t k1 = 0;

  k1 = (uint64_t)addr;
  k1 *= c1;
    k1  = ((k1 << 31) | (k1 >> (33)));
    k1 *= c2;
    h1 ^= k1;

  h1 ^= 8;
    h2 ^= 8;

  h1 += h2;
  h2 += h1;

  h1 ^= h1 >> 33;
  h2 ^= h2 >> 33;
  h1 *= 0xff51afd7ed558ccdLLU;
  h2 *= 0xff51afd7ed558ccdLLU;
  h1 ^= h1 >> 33;
  h2 ^= h2 >> 33;
  h1 *= 0xc4ceb9fe1a85ec53LLU;
  h2 *= 0xc4ceb9fe1a85ec53LLU;
  h1 ^= h1 >> 33;
  h2 ^= h2 >> 33;

  h1 += h2;
  h2 += h1;

    uint64_t b = 1L << (h1 & 0x3f);

    if((h1 >> 6) % 2)
        filter->a |= b;
    else
        filter->b |= b;

    b = 1L << (h2 & 0x3f);

    if((h2 >> 6) % 2)
        filter->a |= b;
    else
        filter->b |= b;
}

static inline bool lugh_stmtx_filter_intersect(lugh_stmtx_filter_t *filter1, lugh_stmtx_filter_t *filter2) {
    return (filter1->a & filter2->a) || (filter1->b & filter2->b);
}

typedef unsigned int lugh_stmtx_ts_t;

typedef enum {
    LUGH_STMTX_COMMIT_ACTIVE,
    LUGH_STMTX_COMMIT_COMPLETE
} lugh_stmtx_commit_state_t;

typedef struct {
    lugh_stmtx_ts_t start;
    lugh_stmtx_commit_state_t state;
  lugh_stmtx_filter_t filter;
    lugh_stmtx_access_t access;
} lugh_stmtx_commit_t;

#define COMMITS 8

lugh_stmtx_commit_t ring[COMMITS];
lugh_atomic(lugh_stmtx_ts_t) ring_index;
lugh_atomic(lugh_stmtx_ts_t) prefix_index;

struct _lugh_stmtx {
    lugh_stmtx_ts_t start;
    lugh_stmtx_write_t write;
    lugh_stmtx_filter_t filter;
    lugh_stmtx_access_t access;
};

void lugh_stmtx_bootstrap(void) {
    ring_index = 0;
    prefix_index = 0;

    for(int i = 0; i < COMMITS; i++) {
        ring[i].start = 0;
        ring[i].state = LUGH_STMTX_COMMIT_COMPLETE;
        lugh_stmtx_filter_init(&ring[i].filter);
        ring[i].access = LUGH_STMTX_ACCESS_RW;
    }
}

int lugh_stmtx_init(lugh_stmtx_t* tx) {
    return_val_if_fail(tx != NULL, -1);

    tx->start = 0;
    lugh_stmtx_write_init(&tx->write);
    lugh_stmtx_filter_init(&tx->filter);
    tx->access = LUGH_STMTX_ACCESS_RW;

    return 0;
}

lugh_stmtx_t *lugh_stmtx_create(void) {
    lugh_stmtx_t *tx = lugh_alloc(sizeof(lugh_stmtx_t));

    if(lugh_stmtx_init(tx) == 0) {
        return tx;
    } else {
        lugh_free(tx);
        return NULL;
    }
}

void lugh_stmtx_deinit(lugh_stmtx_t *tx) {
    return_if_fail(tx != NULL);

    lugh_stmtx_write_deinit(&tx->write);
}

void lugh_stmtx_destroy(lugh_stmtx_t *tx) {
    return_if_fail(tx != NULL);

    lugh_stmtx_deinit(tx);

    lugh_free(tx);
}

int lugh_stmtx_begin(lugh_stmtx_t *tx, lugh_stmtx_access_t access) {
    return_val_if_fail(tx != NULL, -1);

    tx->start = lugh_atomic_load_uint(&prefix_index);

    while(ring[(tx->start + 1) % COMMITS].state == LUGH_STMTX_COMMIT_COMPLETE &&
              ring[(tx->start + 1) % COMMITS].start > tx->start) {
        tx->start++;
    }

    tx->access = access;

    return 0;
}

void lugh_stmtx_abort(lugh_stmtx_t *tx) {
    return_if_fail(tx != NULL);

    lugh_stmtx_write_clear(&tx->write);
    lugh_stmtx_filter_init(&tx->filter);
}

lugh_stmtx_state_t lugh_stmtx_check(lugh_stmtx_t *tx) {
    return_val_if_fail(tx != NULL, LUGH_STMTX_STATE_ERROR);

    if(ring_index == tx->start)
        return LUGH_STMTX_STATE_VIABLE;

    lugh_stmtx_ts_t suffix_end = ring_index;

    while(ring[suffix_end % COMMITS].start < suffix_end);

    for(lugh_stmtx_ts_t i = ring_index; i >= tx->start + 1; i--) {
        if(!(tx->access == LUGH_STMTX_ACCESS_RO && ring[i % COMMITS].access == LUGH_STMTX_ACCESS_RO) &&
                lugh_stmtx_filter_intersect(&tx->filter, &ring[i % COMMITS].filter)) {
            lugh_stmtx_abort(tx);
            return LUGH_STMTX_STATE_ABORTED;
        }

        if(ring[i % COMMITS].state == LUGH_STMTX_COMMIT_ACTIVE)
            suffix_end = i - 1;
    }

    tx->start = suffix_end;

    return LUGH_STMTX_STATE_VIABLE;
}

lugh_stmtx_state_t lugh_stmtx_write(lugh_stmtx_t *tx, void *dst, void *src, size_t size) {
    return_val_if_fail(tx != NULL, LUGH_STMTX_STATE_ERROR);

    lugh_stmtx_filter_add(&tx->filter, dst);

    lugh_stmtx_write_add(&tx->write, dst, src, size);

    return LUGH_STMTX_STATE_VIABLE;
}

lugh_stmtx_state_t lugh_stmtx_read(lugh_stmtx_t *tx, void *dst, void *src, size_t size) {
    return_val_if_fail(tx != NULL, LUGH_STMTX_STATE_ERROR);

    if(lugh_stmtx_check(tx) == LUGH_STMTX_STATE_ABORTED)
        return LUGH_STMTX_STATE_ABORTED;

    lugh_stmtx_filter_add(&tx->filter, src);

    return LUGH_STMTX_STATE_VIABLE;
}

lugh_stmtx_state_t lugh_stmtx_commit(lugh_stmtx_t *tx) {
    return_val_if_fail(tx != NULL, LUGH_STMTX_STATE_ERROR);

    if(tx->write.count == 0) {

        return LUGH_STMTX_STATE_COMMITTED;
    }

    lugh_stmtx_ts_t commit_time = ring_index;

    do {
        if(lugh_stmtx_check(tx) == LUGH_STMTX_STATE_ABORTED)
            return LUGH_STMTX_STATE_ABORTED;
    }   while(lugh_atomic_compare_exchange_uint(&ring_index, commit_time, commit_time + 1) != commit_time);

    commit_time++;

    lugh_stmtx_ts_t index_time = commit_time % COMMITS;

    ring[index_time].state = LUGH_STMTX_COMMIT_ACTIVE;
    ring[index_time].start = commit_time;

    lugh_atomic_synchronize();

    for(lugh_stmtx_ts_t i = commit_time; i > tx->start; i--) {
        if(!(tx->access == LUGH_STMTX_ACCESS_RO && ring[i % COMMITS].access == LUGH_STMTX_ACCESS_RO) &&
                lugh_stmtx_filter_intersect(&tx->filter, &ring[i % COMMITS].filter))
            while(ring[i % COMMITS].state == LUGH_STMTX_COMMIT_ACTIVE);
    }

    lugh_stmtx_write_commit(&tx->write);

    ring[index_time].filter.a = 0;
    ring[index_time].filter.b = 0;
    ring[index_time].state = LUGH_STMTX_COMMIT_COMPLETE;

    if(prefix_index < tx->start)
        prefix_index = tx->start;

    lugh_atomic_synchronize();

    lugh_stmtx_write_clear(&tx->write);
    lugh_stmtx_filter_init(&tx->filter);

    return LUGH_STMTX_STATE_COMMITTED;
}