q_rkb.c

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

/*================================ q_rkb.c ==================================*/
#include "heap.h"
/*---------------------------------------------------------------------------*/
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_dat; ip->i_dat = pp->i_dat; pp->i_dat = t; /* Swap data.       */
}

/* q_insert:
 *	Insert a new item into the heap.
 */
int rkb_ins(int priority, int data,shared_mem_t *smp,element_t *heap)
{
    int  target,i,j,k,parent,temp;
    register	element_t *	ip;		/* Pointer to deleting item. */
    register	element_t *	tp;		/* Pointer to right child.   */
    register	element_t *	kp;		/* Pointer to right child.   */
    register	element_t *	xp;		/* Pointer to right child.   */

    ip = &heap[SHUFFLE(1)];
    tts_acq(&ip->i_lck);
    
    smp->l_lst++;

    target = smp->l_lst;
    if (target > 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.     */
	}
	target = smp->b_value = bv;             /* Set item # = butterfly #. */
    }
    else if (target == 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;
        target = 2;                             /* Item 2 = butterfly 2.     */
    }

    if (smp->l_lst >= (smp->l_ful<<1))
        smp->l_ful = smp->l_lst;
    i = target - smp->l_ful;
    j = smp->l_ful >> 1;
    k = 1;

    tp = &heap[SHUFFLE(target)];
    kp = &heap[SHUFFLE(k)];
    
    tp->i_tag = T_PENDING;              /* Are they sure about this? */
    
    while (j != 0)
    {
        if (tp->i_tag == T_WANTED)
            break;
        if (kp->i_pri > priority)
        {
            temp = priority; priority = kp->i_pri; kp->i_pri = temp;
            temp = data; data = kp->i_dat; kp->i_dat = temp;
        }
        if (i >= j)
        {
            temp = (k<<1)+1;
            xp = &heap[SHUFFLE(temp)];
            tts_acq(&xp->i_lck);
            tts_rel(&kp->i_lck);
            k = temp;
            kp = xp;
            i -= j;
        }
        else
        {
            temp = k<<1;
            xp = &heap[SHUFFLE(temp)];
            tts_acq(&xp->i_lck);
            tts_rel(&kp->i_lck);
            k = temp;
            kp = xp;
        }
        j >>= 1;
    }
    ip = &heap[SHUFFLE(1)];
    if(tp->i_tag==T_WANTED)
    {
        ip->i_pri = priority;
        tp->i_tag = T_EMPTY;
        ip->i_tag = T_PRESENT;
    }
    else
    {
        tp->i_pri = priority;
        tp->i_tag = T_PRESENT;
    }
    tts_rel(&kp->i_lck);
}
/*---------------------------------------------------------------------------*/
int rkb_del(int *priority, int *data,shared_mem_t *smp,element_t *heap)
{
    int  least,i,j,left,right,min,min_pri;
    register	element_t *	ip;		/* Pointer to deleting item. */
    register	element_t *	jp;		/* Pointer to deleting item. */
    register	element_t *	lp;		/* Pointer to left child itm.*/
    register	element_t *	rp;		/* Pointer to right child.   */
    register	element_t *	mp;		/* Pointer to right child.   */
    int         bn;

    i = 1;
    ip = &heap[SHUFFLE(i)];
    tts_acq(&ip->i_lck);
    if(smp->l_lst==0)
    {
        tts_rel(&ip->i_lck);
        *priority = -1;
        return 0;
    }
    least=ip->i_pri;
    j = 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)                           /* 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;
    }
    else if (bn == 1)                           /* Is this item #2?          */
    {
	smp->b_value    = 0x1;                  /* Yes, initialize the bit   */
    }

    jp = &heap[SHUFFLE(j)];

    if(smp->l_lst < smp->l_ful)
        smp->l_ful >>=1;
    if(j==1)
    {
        ip->i_pri = MAXINT;
        ip->i_tag = T_EMPTY;
        tts_rel(&ip->i_lck);
        *priority = least;
        return 1;
    }
    tts_acq(&jp->i_lck);
    if(jp->i_tag==T_PRESENT)
    {
        ip->i_pri = jp->i_pri;
        jp->i_tag=T_EMPTY;
        jp->i_pri=MAXINT;
    }
    else  
    {
        ip->i_tag=T_EMPTY;
        jp->i_tag=T_WANTED;
    }
    tts_rel(&jp->i_lck);
    while(ip->i_tag==T_EMPTY);

    left = i<<1;
    right = left+1;
    if(left<size)
    {
      mp = lp = &heap[SHUFFLE(left)];
      tts_acq(&lp->i_lck);
    }
    else
      left = 0;

    if(right<size)
    {
      mp = rp = &heap[SHUFFLE(right)];
      tts_acq(&rp->i_lck);
    }
    else
      right = 0;

    if(left && right)
    {
      if(lp->i_pri < rp->i_pri) {
        min=left;   mp = lp;
      }
      else {
        min=right;  mp = rp;
      }
    }

    if(left || right)
      min_pri = mp->i_pri;
    else
      min_pri = MAXINT;    

    while(ip->i_pri > min_pri)
    {
        q_swap(ip,mp);
        
        tts_rel(&ip->i_lck);
        if ( (min == left) && right )
	{
          tts_rel(&rp->i_lck);
	}
        else if(left)
	{
          tts_rel(&lp->i_lck);
	}
        i=min;
        ip = mp;

        left = i<<1;
        right = left+1;
        if(left<size)
        {
          mp = lp = &heap[SHUFFLE(left)];
          tts_acq(&lp->i_lck);
        }
        else
          left = 0;

        if(right<size)
        {
          mp = rp = &heap[SHUFFLE(right)];
          tts_acq(&rp->i_lck);
        }
        else
          right = 0;

        if(left && right)
        {
          if(lp->i_pri < rp->i_pri) {
            min=left;   mp = lp;
          }
          else {
            min=right;  mp = rp;
          }
        }

        if(left || right)
          min_pri = mp->i_pri;
        else
          min_pri = MAXINT;    
    }
    tts_rel(&ip->i_lck);
    tts_rel(&lp->i_lck);
    tts_rel(&rp->i_lck);
    *priority = least;
    return 1;
}

/* End of File */