no_shfl.c

是一个linux下面实现的非阻塞的堆

/*================================ q_mpq.c ==================================*/
#include "heap.h"
/*---------------------------------------------------------------------------*/
static	int	q_delay = 0;
static	int	q_delays[12] = {256,64,8,128,4,32,192,16,2,48,1,96};
/*---------------------------------------------------------------------------*/
/* q_swap:
 *	Swap everything but the locks for the two items.
 */
static void q_swap(register element_t *pp, register element_t *ip) 
{	
    register	int		t;
    
    t = ip->i_pri; ip->i_pri = pp->i_pri; pp->i_pri = t; /* Swap priorities. */
    t = ip->i_tag; ip->i_tag = pp->i_tag; pp->i_tag = t; /* Swap tags.       */
    t = ip->i_dat; ip->i_dat = pp->i_dat; pp->i_dat = t; /* Swap data.       */
}

/* q_insert:
 *	Insert a new item into the heap.
 */
int hetal_ins(int priority, int data,shared_mem_t* smp,element_t* heap)
{
    register	element_t*	ip;		/* Pointer to inserting item.*/
    register	element_t*	pp;		/* Pointer to parent item.   */
    register    int		in;		/* Inserting item number.    */
    register    int		pn;		/* Parent item number.	     */
    register    int		nn;		/* Next step item number.    */
    register    int             has_p_lck;      /* Have parent lock.         */
    int		delay;       		 	/* Lock fallback delay.      */

    tts_acq(&smp->l_lck);			/* Acquire lock on size.     */
    if (smp->l_lst >= size) {			/* Is the queue full?        */
	tts_rel(&smp->l_lck);			/* Yes, release the lock     */
	return 0;				/*   and return failure.     */
    }

    in = ++smp->l_lst;				/* Increment the size.       */
    if (in > 2)  {                         /* Do full butterfly?        */
	register unsigned bv = smp->b_value;    /* Yes, use register vars.   */
	register unsigned bit = smp->b_high_bit;
	for (; bit; bit >>= 1)  {               /* Until end of counter...   */
	    bv ^= bit;                          /* Invert counter bit.       */
	    if (bv & bit) {                     /* Did we just set bit?      */
		break;                          /* Yes, quit.                */
	    }
	}
	if (!bit)  {                            /* Did we quit w/ overflow?  */
	    bv = (smp->b_set_bit <<= 1);        /* Yes, adjust calculation   */
	    smp->b_high_bit <<= 1;              /*   variables by 1 bit.     */
	}
	in = smp->b_value = bv;                 /* Set item # = butterfly #. */
    }
    else if (in == 2)                           /* Is this item #2?          */
    {
	smp->b_value    = 0x2;                  /* Yes, initialize the bit   */
	smp->b_set_bit  = 0x2;                  /*   reversed counter vars.  */
	smp->b_high_bit = 0x1;
        /*in = 2;                               /* Item 2 = butterfly 2.     */
    }
    ip = &heap[in];		/* Set item pointer.	     */

    tts_acq(&ip->i_lck);			/* Once we acquire pos. lock */
    tts_rel(&smp->l_lck);                       /*   we can release sz. lock.*/

    ip->i_pri = priority;			/* Set item priority.        */
    ip->i_dat = data;				/* Set item data.	     */
    if (in == 1) {				/* Did we just insert top?   */
	ip->i_tag = T_PRESENT;			/* Yes, mark it as in place  */
	in = 0;					/*   and fall out of loop.   */
    }
    else
	ip->i_tag = pid;			/* No, mark it as ours.      */
    tts_rel(&ip->i_lck);			/* Release lock on inserted. */

    for (; in > 1; in = nn) {			/* As long as not at top.... */
	pn = (in >> 1);				/* Get the parent number.    */
	pp = &heap[pn];		/* Set the parent pointer.   */
	ip = &heap[in];		/* Set the item pointer.     */

	tts_acq(&pp->i_lck);			/* Acquire lock on parent.   */
	if (pp->i_tag == T_EMPTY) {		/* Is the parent item gone?  */
	    nn = 0;				/* Yes, we should quit.      */
	    tts_rel(&pp->i_lck);                /* Release lock on parent.   */
	    continue;                           /* Return to top of loop.    */
	}
	else if (pp->i_tag == pid)  {     /* Has someone moved us up?  */
	    nn = pn;                            /* Yes, move up to parent.   */
	    tts_rel(&pp->i_lck);                /* Release lock on parent.   */
	    continue;                           /* Return to top of loop.    */
	}
        else if (pp->i_tag != T_PRESENT) {      /* Is our parent in place?   */
            tts_rel(&pp->i_lck);                /* No, release parent lock.  */
            has_p_lck = 0;                      /* Remeber the release.      */
        }
        else
            has_p_lck = 1;                      /* Yes, keep parent lock.    */
	    
	tts_acq(&ip->i_lck);			/* Acquire lock on our item. */

	if (ip->i_tag == pid) {			/* Is this really our item?  */
	    if (has_p_lck) {                    /* Have parent lock?         */
		if (ip->i_pri < pp->i_pri) {    /* Should we swap w/ parent? */
		    q_swap(pp, ip);		/* Yes, swap with parent.    */
		    if (pn == 1) {		/* Was the parent the top?   */
			pp->i_tag = T_PRESENT;	/* Yes, pp is our item, mark */
			nn = 0;			/*   it as in place and quit.*/
		    }
		    else		
			nn = pn;		/* No, move up.              */
		}
		else {
		    ip->i_tag = T_PRESENT;     	/* We shouldn't be moved so  */
		    nn = 0;			/*   mark item as in place.  */
		}
	    }
	    else {
		nn = in;			/* Our parent is not in place*/
	    }					/*   so we must wait here.   */
	}
	else {
	    nn = pn;				/* Move to the parent pos.   */
	}

        if (has_p_lck) {                        /* Still have parent lock?   */
            tts_rel(&pp->i_lck);                /* Yes, release it.          */
        }
	tts_rel(&ip->i_lck);			/* Release lock on item.     */

	if (in == nn) {				/* Are we to stay put?       */
	    delay = q_delays[q_delay++];	/* Yes, wait for parent.     */
	    if (q_delay >= 12)
		q_delay = 0;
	    for (; delay-- > 0;)
	        ;
	}
    }
    if (in == 1) {				/* Did we move to the top?   */
	ip = &heap[in];		/* Yes, get top item pointer.*/
	tts_acq(&ip->i_lck);			/* Acquire lock on item.     */
	if (ip->i_tag == pid)		/* Is the top item ours?     */
	    ip->i_tag = T_PRESENT;			/* Yes, mark it as in place. */
	tts_rel(&ip->i_lck);			/* Release lock on item.     */
    }
    return 1;					/* Return, insert successful.*/
}

/*---------------------------------------------------------------------------*/
int hetal_del(int *priority, int *data,shared_mem_t* smp,element_t* heap)
{
    register	element_t*	dp;		/* Pointer to deleting item. */
    register	element_t*	lp;		/* Pointer to left child itm.*/
    register	element_t*	rp;		/* Pointer to right child.   */
    register    int  	        dn;		/* Deleting item number.     */
    register    int		ln;		/* Left child item number.   */
    register    int		rn;		/* Right child item number.  */
    auto        element_t       cap;		/* Captive item record.      */
    register    int             bn;             /* Post decrement itme no.   */
    
    tts_acq(&smp->l_lck);			/* Acquire lock on the size. */
    if (smp->l_lst < 1) {			/* Is the queue empty?	     */
	tts_rel(&smp->l_lck);			/* Yes, release size lock.   */
	*priority = 0;				/* Clear the return priority */
	*data = 0;				/*   and data.               */
	return 0;				/* Return delete failure.    */
    }	

    ln = smp->b_value;                          /* Delete uses post-decremnt.*/
    bn = --smp->l_lst; 				/* Get the new item number.  */
    if(bn>2)                                    /* Do full butterfly?        */
    {
	register unsigned bv = smp->b_value;    /* Yes, use register vars.   */
	register unsigned bit = smp->b_high_bit;
	for (; bit; bit >>= 1)  {               /* Until end of counter...   */
	    bv ^= bit;                          /* Invert counter bit.       */
	    if (!(bv & bit)) {                  /* Did we just clear bit?    */
		break;                          /* Yes, quit.                */
	    }
	}
	if (!bit)  {                            /* Did we quit w/ overflow?  */
	    bv = bn;                            /* Yes, set all bits.        */
	    smp->b_set_bit >>= 1;               /* And adjust calculation    */
	    smp->b_high_bit >>= 1;              /*   variables by 1 bit.     */
	}
	smp->b_value = bv;                      /* Set item # = butterfly #. */
    }
    else if(bn==2)
    {
	smp->b_value    = 0x2;                  /* Yes, initialize the bit   */
	smp->b_set_bit  = 0x2;                  /*   reversed counter vars.  */
	smp->b_high_bit = 0x1;
    }
    else if(bn==1)
    {
	smp->b_value    = 0x1;                  /* Yes, initialize the bit   */
    }
    lp = &heap[ln];		/* Set last pointer.         */

    tts_acq(&lp->i_lck);			/* Acquire lock on last item.*/
    tts_rel(&smp->l_lck);			/* Release the size lock.    */
    cap = *lp;					/* Take the last data captive*/
    lp->i_tag = T_EMPTY;			/*   and free its record.    */
    tts_rel(&lp->i_lck);			/* Release last item lock.   */

    dn = 1;					/* Heapify from the top.     */
    dp = &heap[dn];		/* Set delete item pointer.  */
    tts_acq(&dp->i_lck);			/* Acquire delete item lock. */
    if (dp->i_tag == T_EMPTY) {			/* Is the record empty?      */
	tts_rel(&dp->i_lck);			/* Yes, release its lock.    */
	*priority = cap.i_pri;			/* Return the captive        */
	*data     = cap.i_dat;			/* priority and data.        */
	return 1;				/* Return success.           */
    }
    
    *priority = dp->i_pri;			/* Return the top item from  */
    *data = dp->i_dat;				/* the queue.		     */
    dp->i_pri = cap.i_pri;			/* Replace it with the       */
    dp->i_dat = cap.i_dat;			/*   captive data.           */
    dp->i_tag = T_PRESENT;				/* Mark the top as valid.    */
    
    for (ln = dn<<1; ln < size; ln = dn<<1) { /* As long as not at bottom..*/
	rn = ln + 1;				/* Set the right child no.   */
	lp = &heap[ln];		/* Set the left pointer.     */
	rp = &heap[rn];		/* Set the right pointer.    */
	
	tts_acq(&lp->i_lck);			/* Acquire lock on left chld.*/
	if (lp->i_tag == T_EMPTY) {		/* Is the child item empty?  */
	    tts_rel(&lp->i_lck);		/* Yes, release the lock     */
	    break;				/*   and break out of loop.  */
	}

	if (rn < size) {			/* Does a right record exist?*/
	    tts_acq(&rp->i_lck);		/* Yes, acquire lock on it.  */
	    if (rp->i_tag != T_EMPTY) {		/* Is the right child empty? */
		if (rp->i_pri < lp->i_pri) {	/* No, Should we go right?   */
		    element_t*	tp;		/* Yes, we need a temp. var. */
		    int		tn;		/*   for pointer and number. */
		    
		    tn = ln; ln = rn; rn = tn;	/* Swap left/right numbers.  */
		    tp = lp; lp = rp; rp = tp;	/* Swap left/right pointers. */
		}				/* Right is aliased to left! */
	    }
	    tts_rel(&rp->i_lck);		/* Release lock on bad child.*/
	}

	if (lp->i_pri < dp->i_pri) {		/* Should we swap w/ child?  */
	    q_swap(lp, dp);			/* Yes, swap delete w/ child.*/
	}
	else {
	    tts_rel(&lp->i_lck);		/* No, quit be releasing chld*/
	    break;				/*  lock and breaking loop.  */
	}

	tts_rel(&dp->i_lck);			/* Release lock on old item. */
	dn = ln;				/* Move to the left child by */
	dp = lp;				/*   acquiring no. and ptr.  */
    }
    tts_rel(&dp->i_lck);			/* Release delete item lock. */
    return 1;					/* Return delete success.    */
}

/* End of File */