/* 
 * Written by Josh Dybnis and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 *
 * hazard pointers
 *
 * www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
 *
 */
#include "common.h"
#include "lwt.h"
#include "mem.h"
#include "tls.h"
#include "runtime.h"
#include "hazard.h"

typedef struct pending {
    void * ptr; 
    free_t free_; 
} pending_t;

typedef struct haz_local {
    pending_t *pending; // to be freed
    int pending_size;
    int pending_count;

    haz_t static_haz[STATIC_HAZ_PER_THREAD];

    haz_t **dynamic;
    int dynamic_size;
    int dynamic_count;

} haz_local_t;

static haz_local_t haz_local_[MAX_NUM_THREADS] = {};

static void sort_hazards (haz_t *hazards, int n) {
    return;
}

static int search_hazards (void *p, haz_t *hazards, int n) {
    for (int i = 0; i < n; ++i) {
        if (hazards[i] == p) 
            return TRUE;
    }
    return FALSE;
}

static void resize_pending (void) {
    LOCALIZE_THREAD_LOCAL(tid_, int);
    haz_local_t *l = haz_local_ + tid_;
    pending_t *p = nbd_malloc(sizeof(pending_t) * l->pending_size * 2);
    memcpy(p, l->pending, l->pending_size);
    nbd_free(l->pending);
    l->pending = p;
    l->pending_size *= 2;
}

void haz_defer_free (void *d, free_t f) {
    assert(d);
    assert(f);
    LOCALIZE_THREAD_LOCAL(tid_, int);
    haz_local_t *l = haz_local_ + tid_;
    while (l->pending_count == l->pending_size) {

        if (l->pending_size == 0) {
            l->pending_size = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
            l->pending = nbd_malloc(sizeof(pending_t) * l->pending_size);
            break;
        }

        // scan for hazard pointers
        haz_t *hazards = nbd_malloc(sizeof(haz_t) * l->pending_size);
        int    hazard_count = 0;
        for (int i = 0; i < MAX_NUM_THREADS; ++i) {
            haz_local_t *h = haz_local_ + i;
            for (int j = 0; j < STATIC_HAZ_PER_THREAD; ++j) {
                if (h->static_haz[j] != NULL) {
                    if (hazard_count == l->pending_size) {
                        resize_pending();
                        nbd_free(hazards);
                        haz_defer_free(d, f);
                        return;
                    }
                    hazards[hazard_count++] = h->static_haz[j];
                }
            }
            for (int j = 0; j < h->dynamic_count; ++j) {
                if (h->dynamic[j] != NULL && *h->dynamic[j] != NULL) {
                    if (hazard_count == l->pending_size) {
                        resize_pending();
                        nbd_free(hazards);
                        haz_defer_free(d, f);
                        return;
                    }
                    hazards[hazard_count++] = *h->dynamic[j];
                }
            }
        }
        sort_hazards(hazards, hazard_count);

        // check for conflicts
        int  conflicts_count = 0;
        for (int i = 0; i < l->pending_count; ++i) {
            pending_t *p = l->pending + i;
            if (search_hazards(p->ptr, hazards, hazard_count)) {
                l->pending[conflicts_count++] = *p; // put conflicts back on the pending list
            } else {
                assert(p->free_);
                assert(p->ptr);
                p->free_(p->ptr); // free pending item
            }
        }
        l->pending_count = conflicts_count;
        nbd_free(hazards);
    }
    l->pending[ l->pending_count ].ptr  = d;
    l->pending[ l->pending_count ].free_ = f;
    l->pending_count++;
}

haz_t *haz_get_static (int i) {
    if (i >= STATIC_HAZ_PER_THREAD)
        return NULL;
    LOCALIZE_THREAD_LOCAL(tid_, int);
    return &haz_local_[tid_].static_haz[i];
}

void haz_register_dynamic (haz_t *haz) {
    LOCALIZE_THREAD_LOCAL(tid_, int);
    haz_local_t *l = haz_local_ + tid_;

    if (l->dynamic_size == 0) {
        l->dynamic_size = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
        l->dynamic = nbd_malloc(sizeof(haz_t *) * l->dynamic_size);
    }

    if (l->dynamic_count == l->dynamic_size) {
        haz_t **d = nbd_malloc(sizeof(haz_t *) * l->dynamic_size * 2);
        memcpy(d, l->dynamic, l->dynamic_size);
        nbd_free(l->dynamic);
        l->dynamic = d;
        l->dynamic_size *= 2;
    }

    l->dynamic[ l->dynamic_count++ ] = haz;
}

// assumes <haz> was registered in the same thread
void haz_unregister_dynamic (void **haz) {
    LOCALIZE_THREAD_LOCAL(tid_, int);
    haz_local_t *l = haz_local_ + tid_;

    for (int i = 0; i < l->dynamic_count; ++i) {
        if (l->dynamic[i] == haz) {
            if (i != l->dynamic_count - 1) {
                l->dynamic[i] = l->dynamic[ l->dynamic_count ];
            }
            l->dynamic_count--;
            return;
        }
    }
    assert(0);
}