q_lck.c

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

/*================================ q_lck.c ==================================*/
#include "heap.h"
static void q_swap(register element_t *pp, register element_t *ip) 
{	
register  int	temp;

  temp = ip->i_pri; ip->i_pri = pp->i_pri; pp->i_pri = temp;
  temp = ip->i_dat; ip->i_dat = pp->i_dat; pp->i_dat = temp;
}

int single_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.    */

    ussetlock(smp->l_lock);                     /* Acquire the queue lock.   */
    
    if (smp->l_lst >= size) {			/* Is the queue full?        */
        usunsetlock(smp->l_lock);               /* Free the queue lock.      */
	return 0;				/*   and return failure.     */
    }

    in = ++smp->l_lst;				/* Increment the size.       */
    ip = &heap[in];       		/* Set item pointer.	     */

    ip->i_pri = priority;			/* Set item priority.        */
    ip->i_dat = data;				/* Set item data.	     */
    if (in == 1) {				/* Did we just insert top?   */
	in = 0;					/* Fall out of loop.   */
    }

    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.     */

	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?   */
		nn = 0;			/*   it as in place and quit.*/
	    }
	    else		
		nn = pn;		/* No, move up.              */
	}
	else {
	    nn = 0;			/*   mark item as in place.  */
	}
    }
    usunsetlock(smp->l_lock);                   /* Free the queue lock.      */
    return 1;					/* Return, insert successful.*/
}
/*---------------------------------------------------------------------------*/
int single_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.      */
    
    ussetlock(smp->l_lock);                     /* Acquire the queue lock.   */

    if (smp->l_lst < 1) {			/* Is the queue empty?	     */
        usunsetlock(smp->l_lock);               /* Free the queue lock.      */
	*priority = 0;				/* Clear the return priority */
	*data = 0;				/*   and data.               */
	return 0;				/* Return delete failure.    */
    }	

    ln = smp->l_lst--; 				/* Decrease the queue size.  */
    lp = &heap[ln];       		/* Set last pointer.         */


    cap = *lp;					/* Take the last data captive*/

    dn = 1;					/* Heapify from the top.     */
    dp = &heap[dn];	        	/* Set delete item pointer.  */
    if (ln==1) {			/* Is the record empty?      */
        usunsetlock(smp->l_lock);               /* Free the queue 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.           */
    
    for (ln = dn<<1; ln <= smp->l_lst; 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.    */
	
	if (rn <= smp->l_lst) {			/* Does a right record exist?*/
	  if (rp->i_pri < lp->i_pri) {	/* 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! */
        }

	if (lp->i_pri < dp->i_pri) {		/* Should we swap w/ child?  */
	    q_swap(lp, dp);			/* Yes, swap delete w/ child.*/
	}
	else {
	    break;				/*  lock and breaking loop.  */
	}

	dn = ln;				/* Move to the left child by */
	dp = lp;				/*   acquiring no. and ptr.  */
    }
    usunsetlock(smp->l_lock);                   /* Free the queue lock.      */
    return 1;					/* Return delete success.    */
}

/* End of File */