/*
 * Copyright (c) 2000 Columbia University
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that: (1) source code distributions
 * retain the above copyright notice and this paragraph in its entirety, (2)
 * distributions including binary code include the above copyright notice and
 * this paragraph in its entirety in the documentation or other materials
 * provided with the distribution, and (3) all advertising materials mentioning
 * features or use of this software display the following acknowledgement:
 * ``This product includes software developed by Columbia University
 * and its contributors.'' Neither the name of the University nor the names 
 * of its contributors may be used to endorse or promote products derived 
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Written by Ping Pan, Columbia University/Bell Labs, 2000
 *
 * The author would like to thank Bell Labs for providing time and freedom
 * to complete this work. Please forward bug fixes, enhancements and questions
 * to pingpan@cs.columbia.edu.
 */

/* 
 * This bud is to the fat boys (Tim Rolfes, Bill Guckel and Marc Cochran)
 * of the IBM NSFnet T960 team. Cheers!
 */

#ifndef _QUEUE_H_
#define _QUEUE_H_


/* We are dealing with  singly-linked queues only.
 *
 * To use the macro's here, the real data structure must have 
 * a field of "next" for chaining.
 */

typedef struct {
	int	cnt;
	void	*head;
} LIFO;

typedef struct {
	void *head;
	void *tail;
} FIFO;


/* Build up a link listed table (LIFO) from one block of memory
 *
 * first_entry is the starting pointer of a block of malloc'ed memory.
 * note:  only loop max_depth-1 times!!!
 */
#define LIFO_INIT(type, fbl, first_entry, max_depth)		\
{								\
	intl i, j=max_depth-1;					\
	type *tmp_entry;					\
								\
	fbl.head = (void *)first_entry;				\
	for (i = 0, tmp_entry = first_entry; i < j;		\
	    tmp_entry = tmp_entry->next, i++)			\
		tmp_entry->next = tmp_entry + 1;		\
								\
	tmp_entry->next = NULL;					\
	fbl.cnt = max_depth;					\
}



/* Remove an entry from a LIFO */
#define QR_LIFO(q, thresh, entry)				\
{								\
	entry = NULL;						\
	if (q->cnt > thresh)   {				\
	   entry = q->head;					\
	   q->head = entry->next;				\
	   q->cnt --;						\
	}							\
}


/* Add an entry to a LIFO */
#define QA_LIFO(q, new)						\
{								\
	new->next = q->head;					\
	q->head = new;						\
	q->cnt++;						\
}


/* Move an entry between two LIFO's */
#define QM_LIFO(src_lifo, dst_lifo, entry)			\
{								\
	QR_LIFO(src_lifo, 0, entry);				\
	if (entry != NULL)					\
	   QA_LIFO(dst_lifo, entry);				\
}


/* Move multiple entries between two LIFO's
 * (a combined version of qrm_lifo() and qam_lifo())
 */
#define QMM_LIFO(src_lifo, dst_lifo, thresh, type)		\
{								\
	type	*head, *tail, *curr;				\
	int	old_cnt;					\
								\
	if (src_lifo->cnt < thresh)				\
	   thresh = src_lifo->cnt;				\
								\
	src_lifo->cnt -= thresh;				\
	head = src_lifo->head;					\
	tail = head;						\
	old_cnt = thresh;					\
								\
	while (1) {						\
	   curr = tail->next;					\
	   thresh--;						\
	   if (thresh == 0)					\
		break;						\
	   tail = curr;						\
	}							\
	src_lifo->head = curr;					\
	tail->next = dst_lifo->head;				\
	dst_lifo->head = head;					\
	dst_lifo->cnt += old_cnt;				\
}


/* Remove an entry from the head of a FIFO */
#define QR_FIFO(fifo, entry)					\
{								\
	entry = fifo->head;					\
	if (entry != NULL) {					\
		fifo->head = entry->next;			\
		if (fifo->head == NULL)				\
			fifo->tail == NULL			\
	}							\
}


/* Add an entry to the tail of a FIFO */
#define QA_FIFO(fifo, entry, type)				\
{								\
	type *old_tail;						\
								\
	old_tail = fifo->tail;					\
	fifo->tail = entry;					\
	entry->next = NULL;					\
	if (old_tail == NULL)					\
		fifo->head = entry;				\
	else							\
		old_tail->next = entry;				\
}

#endif