void
lock(struct lock *l)
{
  struct proc *p;
  
  if (up == nil) {
    return;
  }

 retry:

  if (!cas(&l->holder, nil, up)) {
    p = l->wlist;
    while (p != nil && p->next != nil)
      p = p->next;

    up->next = nil;

    if (p == nil) {
      if (!cas(&l->wlist, nil, up)) {
	goto retry;
      }
    } else if (!cas(&p->next, nil, up)) {
      goto retry;
    }

    procwait();
  }
}

// Possible lock states are MUTEX_UNLOCKED, MUTEX_LOCKED and MUTEX_SLEEPING.
// MUTEX_SLEEPING means that there is presumably at least one sleeping thread.
// Note that there can be spinning threads during all states - they do not
// affect mutex's state.
void
runtime·lock(Lock *l)
{
	uint32 i, v, wait, spin;

	if(m->locks++ < 0)
		runtime·throw("runtime·lock: lock count");

	// Speculative grab for lock.
	v = runtime·xchg(&l->key, MUTEX_LOCKED);
	if(v == MUTEX_UNLOCKED)
		return;

	// wait is either MUTEX_LOCKED or MUTEX_SLEEPING
	// depending on whether there is a thread sleeping
	// on this mutex.  If we ever change l->key from
	// MUTEX_SLEEPING to some other value, we must be
	// careful to change it back to MUTEX_SLEEPING before
	// returning, to ensure that the sleeping thread gets
	// its wakeup call.
	wait = v;

	// On uniprocessor's, no point spinning.
	// On multiprocessors, spin for ACTIVE_SPIN attempts.
	spin = 0;
	if(runtime·ncpu > 1)
		spin = ACTIVE_SPIN;

	for(;;) {
		// Try for lock, spinning.
		for(i = 0; i < spin; i++) {
			while(l->key == MUTEX_UNLOCKED)
				if(runtime·cas(&l->key, MUTEX_UNLOCKED, wait))
					return;
			runtime·procyield(ACTIVE_SPIN_CNT);
		}

		// Try for lock, rescheduling.
		for(i=0; i < PASSIVE_SPIN; i++) {
			while(l->key == MUTEX_UNLOCKED)
				if(runtime·cas(&l->key, MUTEX_UNLOCKED, wait))
					return;
			runtime·osyield();
		}

		// Sleep.
		v = runtime·xchg(&l->key, MUTEX_SLEEPING);
		if(v == MUTEX_UNLOCKED)
			return;
		wait = MUTEX_SLEEPING;
		runtime·futexsleep(&l->key, MUTEX_SLEEPING, -1);
	}
}

//TTAS with exponential backoff
void lock(){
	while(1){
		while(__sync_add_and_fetch(&TTASLock, 0)){//lock is busy -- handle backoff
			__sync_add_and_fetch(&backoff, backoff * 2);//increase backoff time
			if(backoff >= MAX_SLEEP){
				cas(&backoff, backoff, 1);//reset backoff back to 1
			}
			usleep(backoff);
		}//reading to see if lock is busy
			if(cas(&TTASLock, 0, 1)){ //lock acheived
				return;
			}
	}
}

// Sweeps spans in list until reclaims at least npages into heap.
// Returns the actual number of pages reclaimed.
static uintptr
MHeap_ReclaimList(MHeap *h, MSpan *list, uintptr npages)
{
	MSpan *s;
	uintptr n;
	uint32 sg;

	n = 0;
	sg = runtime·mheap.sweepgen;
retry:
	for(s = list->next; s != list; s = s->next) {
		if(s->sweepgen == sg-2 && runtime·cas(&s->sweepgen, sg-2, sg-1)) {
			runtime·MSpanList_Remove(s);
			// swept spans are at the end of the list
			runtime·MSpanList_InsertBack(list, s);
			runtime·unlock(&h->lock);
			n += runtime·MSpan_Sweep(s);
			runtime·lock(&h->lock);
			if(n >= npages)
				return n;
			// the span could have been moved elsewhere
			goto retry;
		}
		if(s->sweepgen == sg-1) {
			// the span is being sweept by background sweeper, skip
			continue;
		}
		// already swept empty span,
		// all subsequent ones must also be either swept or in process of sweeping
		break;
	}
	return n;
}

void Orb_cell_set(Orb_cell_t c, Orb_t val) {
	Orb_t curv, oldv;
	oldv = safe_read(&c->core);
	do {
		curv = oldv;
	} while(curv != (oldv = cas(&c->core, oldv, val)));
}

	void pull(global_queue<value_type> & gq)
	{
		this->clear();

		node * new_head = gq.m_head;
		do
		{
			m_head = new_head;
			new_head = cas(gq.m_head, (node *)0, new_head);
		}
		while (m_head != new_head);

		// Fix-up the pulled list
		if (m_head == 0)
			return;

		++m_size;
		node * cur = m_head;
		while (cur->m_next != 0)
		{
			cur->m_next->m_prev = cur;
			++m_size;
			cur = cur->m_next;
		}

		m_tail = cur;
	}

bool
uf_try_grab (const uf_t *uf, ref_t a)
{
    char x = atomic_read (&uf->array[a].uf_status);
    if (x == UF_LOCK) return false;
    return cas (&uf->array[a].uf_status, x, UF_LOCK);
}

stack_t* stack_push(stack_t* head, stack_t* newHead)
{
#if NON_BLOCKING == 0
    pthread_mutex_lock(&mutex);
    newHead->ptr=head;
    pthread_mutex_unlock(&mutex);

#elif NON_BLOCKING == 1
  // Implement a harware CAS-based stack

    if(head == NULL)
    {
        newHead->ptr = head;
    }
    else
    {
        stack_t* old;
        do
        {
            old = head;
            newHead->ptr = old;
        }while(cas(newHead->ptr, old, head) == old);
    }
#else

  // Implement a software CAS-based stack
#endif

  // Debug practice: you can check if this operation results in a stack in a consistent check
  // It doesn't harm performance as sanity check are disabled at measurement time
  // This is to be updated as your implementation progresses
  stack_check((stack_t*)1);

  return newHead;
}

	// const to allow shared_ptr<T const>
	void release() const
	{
#if GVL_THREADSAFE
		#error "Not finished"
		if(_ref_count == 1) // 1 means it has to become 0, nobody can increment it after this read
			_delete();
		else
		{
			// TODO: Implement CAS
			int read_ref_count;
			do
			{
				read_ref_count = _ref_count;
			}
			while(!cas(&_ref_count, read_ref_count, read_ref_count - 1));
			
			if(read_ref_count - 1 == 0)
			{
				_clear_weak_ptrs();
				_delete();
			}
		}
#else
		--_ref_count;
		if(_ref_count == 0)
		{
			_clear_weak_ptrs();
			_delete();
		}
#endif
	}

void
runtime·cgocall(void (*fn)(void*), void *arg)
{
	Defer d;

	if(m->racecall) {
		runtime·asmcgocall(fn, arg);
		return;
	}

	if(!runtime·iscgo && !Windows)
		runtime·throw("cgocall unavailable");

	if(fn == 0)
		runtime·throw("cgocall nil");

	if(raceenabled)
		runtime·racereleasemerge(&cgosync);

	// Create an extra M for callbacks on threads not created by Go on first cgo call.
	if(runtime·needextram && runtime·cas(&runtime·needextram, 1, 0))
		runtime·newextram();

	m->ncgocall++;

	/*
	 * Lock g to m to ensure we stay on the same stack if we do a
	 * cgo callback. Add entry to defer stack in case of panic.
	 */
	runtime·lockOSThread();
	d.fn = &endcgoV;
	d.siz = 0;
	d.link = g->defer;
	d.argp = (void*)-1;  // unused because unlockm never recovers
	d.special = true;
	d.free = false;
	g->defer = &d;

	m->ncgo++;

	/*
	 * Announce we are entering a system call
	 * so that the scheduler knows to create another
	 * M to run goroutines while we are in the
	 * foreign code.
	 *
	 * The call to asmcgocall is guaranteed not to
	 * split the stack and does not allocate memory,
	 * so it is safe to call while "in a system call", outside
	 * the $GOMAXPROCS accounting.
	 */
	runtime·entersyscall();
	runtime·asmcgocall(fn, arg);
	runtime·exitsyscall();

	if(g->defer != &d || d.fn != &endcgoV)
		runtime·throw("runtime: bad defer entry in cgocallback");
	g->defer = d.link;
	endcgo();
}

void * thread_routine(void * arg)
{
  int tid;
  int m = 0, w, h;
  tid = *((int *)arg);
  
  while(1){
    if ( m < MAX ){
      w = (++m) * 11 + tid;
    }
    else{
      pthread_exit(NULL);
    }
    
    h = (w * 7) % SIZE;
    
    if (h<0)
    {
      ERROR: goto ERROR;
      ;
    }

    while ( cas(table, h, 0, w) == 0){
      h = (h+1) % SIZE;
    }
  }

}

//returns poped element
stack_t* stack_pop(stack_t* head)
{
    if(head == NULL)
		return NULL;
	stack_t* ret; 
#if NON_BLOCKING == 0
  // Implement a lock_based stack
    pthread_mutex_lock(&mutex);
	ret = head;
    head = head->ptr;
    pthread_mutex_unlock(&mutex);
#elif NON_BLOCKING == 1
  // Implement a harware CAS-based stack
	stack_t *newHead; 
    if (head->ptr == NULL){
        ret=head;
        head = NULL;
    }
    else
    {
        do{
            ret = head;
            newHead = head->ptr;
            head = newHead;
        } 
        while(cas(head,newHead,newHead)==newHead);
    }
#else
  /*** Optional ***/
  // Implement a software CAS-based stack
#endif

  return ret;
}

void*
thread_test_aba_1(void* arg) {
#if NON_BLOCKING == 1 || NON_BLOCKING == 2
  thread_test_aba_args_t *args = (thread_test_aba_args_t*) arg;
  pthread_mutex_lock(args->lock);
  printf("thread 1 is in control and begins poping 10 from stack\n");
  node_t* data;
  while (1) {
    data=*(args->shared_stack->head);
    if (data==NULL){
      break;
    }
    int value=data->data;
    pthread_mutex_unlock(args->lock);
    sleep(1);
    pthread_mutex_lock(args->lock);
    if (cas(args->shared_stack->head,data,data->next)==data) {
      printf("thread one successfully pop:ed %i from stack\n",data->data);
      pthread_mutex_unlock(args->lock);
      if (value!=data->data){
      printf("aba problem detected\n");
      args->success=1;
      }

      break;
    }
  }
args->id=0;
#endif
  return NULL;
}

void
unlock(struct lock *l)
{
  struct proc *p;

  if (up == nil) {
    return;
  }

 retry:

  p = l->wlist;
  if (p != nil) {
    if (!cas(&l->wlist, p, p->next)) {
      goto retry;
    }

    p->next = nil;
    
    l->holder = p; 
    procready(p);
  } else {
    l->holder = nil;
  }
}

    static inline T fetch_add(volatile T *ptr, T x) {
      T ncount = *ptr, count;
      do {
	count = ncount;
	ncount = cas((T *)ptr, count, count + x);
      } while(ncount != count);
      return count;
    }

TEST(APC, BasicPrimeStuff) {
  auto store = new_primed_store();
  Variant val;

  EXPECT_TRUE(store->get("int_2", val));
  EXPECT_TRUE(cellSame(*val.asCell(), make_tv<KindOfInt64>(2)));

  bool found = false;
  EXPECT_EQ(store->inc("int_3", 1, found), 4);
  EXPECT_TRUE(found);
  EXPECT_FALSE(store->get("int_200", val));

  EXPECT_EQ(store->cas("obj_1", 1, 2), true); // stdclass converts to 1
  EXPECT_EQ(store->cas("obj_2", 4, 5), false);
  EXPECT_EQ(store->cas("int_4", 4, 5), true);
  EXPECT_EQ(store->cas("int_5", 4, 5), false);
}

void*
thread_test_aba_2(void* arg) {
#if NON_BLOCKING == 1 || NON_BLOCKING == 2
  thread_test_aba_args_t *args = (thread_test_aba_args_t*) arg;
  pthread_mutex_lock(args->lock);
  printf("thread two is in controll\n");
  node_t* data;
  while (1) {
    data=*(args->shared_stack->head);
    if (data==NULL){
      break;
    }
    if (cas(args->shared_stack->head,data,data->next)==data) {
      printf("thread two successfully poped %i from stack\n",data->data);
      break;
    }
  }
  node_t* node=malloc(sizeof(node_t));
  node->data=15;
  while (1) {
    node_t* temp=*(args->shared_stack->head);
    node->next=temp;
    if(cas(args->shared_stack->head,temp,node)==temp) {
      printf("thread 2 succesfully pushed 15 to stack successfull\n");
      break;
    }
  }
  printf("thread 2 modified data in %i" ,data->data);
  data->data=20;
  printf("to 20 \n");

  while (1) {
    node_t* temp=*(args->shared_stack->head);
    data->next=temp;
    if(cas(args->shared_stack->head,temp,data)==temp) {
      printf("thread 2 pushed 20 to stack \n");
      break;
    }
  }
  printf("thread two gives control back to thread one \n");
  pthread_mutex_unlock(args->lock);


#endif
  return NULL;
}

CTraceCollector::~CTraceCollector()
{
    CAutoCriticalSection cas(m_CriticalSectionSys);
    for (TPipeListenerList::iterator it = m_PipeListenerList.begin(); it != m_PipeListenerList.end(); it++)
    {
        delete (*it);
    }
}

static inline void
lock_acquire()
{
    while (1) {
        while (lock) {}
        if (cas(&lock, 0, 1)) return;
    }
}

 /* postfix operator */
 T operator --(int)
 {
     for(;;)
     {
         T oldv = value;
         if(likely(cas(&value, oldv, oldv-1)))
             return oldv;
     }
 }