#include <stdlib.h>
#include "locks.h"


/*
  Implementation of memory fence.  Rely on guarantee by GCC that its
  fetch-and-add functions also serve as fences
*/
static void fence () {
    int fence_val = 0;
    __sync_fetch_and_add(&fence_val, 0);
}

/* Delay for random number of cycles.  Exponentially distributed */
static void random_spin(int logmax) {
    volatile int sink;
    int val = random();
    int logloops = random() % logmax;
    volatile int loops = 1 << logloops;
    while (loops--) {
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
	sink *= sink;
    }
    sink = val;
}

void cas_lock_init(cas_lock_t *lock) {
    lock->is_locked = 0;
    fence();
}

#define CAS_LOGMAX 20

void cas_lock_lock(cas_lock_t *lock) {
    while (1) {
	while (lock->is_locked)
	    /* Back off by random amount */
	    random_spin(CAS_LOGMAX);

	if (__sync_bool_compare_and_swap(&lock->is_locked, 0, 1))
	    break;
    }

}

void cas_lock_unlock(cas_lock_t *lock) {
    lock->is_locked = 0;
    fence();
}


void ticket_lock_init(ticket_lock_t *lock) {
    lock->serving = 1;
    lock->next_ticket = 1;
    fence();
}

void ticket_lock_lock(ticket_lock_t *lock) {
    /* Get ticket */
    unsigned long myticket = __sync_fetch_and_add(&lock->next_ticket, 1);

    /* Wait until reach ticket */
    while (lock->serving != myticket)
	/* Keep looping */
	;

    fence();
}

void ticket_lock_unlock(ticket_lock_t *lock) {
    __sync_fetch_and_add(&lock->serving, 1);
}