dr->dr_raddr = da;	/* Verify this address next time around. */
	dr->dr_rtime = time(NULL);
}


/*
 * Fill the reclaimation list from the used list.  Take addresses off the head
 * of the used queue until the reclaim queue is full, the used queue is empty,
 * or the address at the head of the used queue has been verified (responded
 * to an ARP) within dr_time_addrretry tocks.
 */
static int
da_fill_reclaim(dr)
struct drange_desc *dr;
{
        struct daddr *da;
        long now;

        now = time(NULL);

        while(dr->dr_rcount < RECLAIM_QUEUE_MAX){
		/* Look at first address on used queue. */
                da = (struct daddr *) dr->dr_usedq.head;
                if(da == NULL)
			return 0;    /* If used queue is empty, done filling. */
                if(now - da->da_time < dr->dr_time_addrretry)
                        return 0;

		/* If the first element has responded to in ARP recently.
		 * I am done filling.
		 */
		/* Get first address on used queue. */
                da = (struct daddr *) q_dequeue(&dr->dr_usedq);
		/* Mark time addr put in reclaim queue. */
                da->da_time = now;
		/* Put it at end of reclaim queue. */
                q_enqueue(&dr->dr_reclaimq,(struct q_elt *)da);
                ++dr->dr_rcount;
        }
        return 0;
}


/*
 * Address assignment routines.
 */

/*
 * Assign an address.
 */
int
da_assign(iface, hwaddr, ipaddr)
struct iface *iface;	/* -> Pointer to lnet struct of net on which to assign addr. */
uint8	*hwaddr;	/* -> Pointer to hardware address of hosts. */
int32	*ipaddr;	/* <- Address assigned to host. */
{
	struct drange_desc *dr;	
	struct daddr *da;	
	int status;
	struct arp_type	*at;

	/* Find the network table */
	for(dr = (struct drange_desc *) rtabq.head; dr != NULL; dr = dr->dr_next){
		if(iface == dr->dr_iface)
			break;	
	}

	if(dr == NULL){
		*ipaddr = 0;
		return ERR_NOIPADDRESS;
	}

	/* If this host had an address assigned previously, try to reassign
	 * that. If no previous address, assign a new one.
	 */
	status = da_get_old_addr(dr, hwaddr, &da);
	if(status != 0) 
		status = da_get_free_addr(dr, &da);
	
	/* If I got an address, assign it and link it in to the use list. */
	if(status == 0){
		memcpy(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen);
		*ipaddr = da->da_addr;
		da->da_time = time(NULL);	/* Time assigned */
		q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
		at = &Arp_type[dr->dr_iface->iftype->type];
		bp_log("IP addr %s assigned to %s on network %s\n",
		 inet_ntoa(*ipaddr),
		 (*at->format)(bp_ascii, hwaddr), dr->dr_iface->name);
	}

        switch(dr->dr_rstate){
        case R_OFF:
        case R_DONE:
                if(dr->dr_fcount <= dr->dr_thon) 
			da_enter_reclaim(dr);
                /* Fall through. */
        case R_RECLAIM:
                if(dr->dr_fcount <= dr->dr_thcritical) 
			da_enter_critical(dr);
                break;
        /* case R_CRITICAL: is not handled. */
        }
        return status;
}


/*
 * Enter the reclaimation state.
 */
static void
da_enter_reclaim(dr)
struct drange_desc *dr;
{
        char ipa[16], ipb[16];

        iptoa(dr->dr_start, ipa);
        iptoa(dr->dr_end, ipb);

        if(dr->dr_rstate & R_OFF){
                dr->dr_vstate = V_SWAIT;  /* da_enter_reclaim: R_OFF */
                dr->dr_rtime = 0;
        }
        dr->dr_rstate = R_RECLAIM;
        dr->dr_time_addrretry = TIME_ADDRRETRY;         /* Wait a while before retrying addresses. */
}

/*
 * Search for hwaddr on the used list, the reclaimation list, and the free list.
 */
static int
da_get_free_addr(dr, dap)
struct drange_desc *dr;
struct daddr **dap;
{
        *dap = (struct daddr *) q_dequeue(&(dr->dr_freeq));
        if(*dap == NULL) 
		return ERR_NOIPADDRESS;
        --dr->dr_fcount;

        return 0;
}

/*
 * Search for hwaddr on the used list, the reclaimation list, and the free list.
 */
static int
da_get_old_addr(dr, hwaddr, dap)
struct drange_desc *dr;
uint8  	*hwaddr;
struct daddr **dap;
{
        struct daddr *da;

	/* Search the used queue */
        for(da = (struct daddr *) dr->dr_usedq.head; da != NULL; da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        q_remove(&dr->dr_usedq,(struct q_elt *)da);
                        *dap = da;
                        return 0;
                }
        }

	/* Search the relaimq queue */
        for(da = (struct daddr *) dr->dr_reclaimq.head; da != NULL; 
		da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        /* Here is the address.  I have to be carefull in removing it from
			 * reclaim queue, I may be verifying this address.
                         * If I am, I have to fix up the pointers before removing this
                         * element.
                         */
                        if((dr->dr_rstate & R_OFF) == 0 && dr->dr_vstate == V_VERIFY 
				&& dr->dr_raddr == da){ 
				/* I am verifying this very address.  */
                                /* Start over.  
				 * This should happen very infrequently at most. */
                                dr->dr_vstate = V_SWAIT;  /* get_old_addr */
                        }
                        q_remove(&dr->dr_reclaimq,(struct q_elt *)da);
                        *dap = da;
                        return 0;
                }
        }

	/* Search the free queue */
        for(da = (struct daddr *) dr->dr_freeq.head; da != NULL; da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        q_remove(&dr->dr_freeq,(struct q_elt *)da);
                        --dr->dr_fcount;
                        *dap = da;
                        return 0;
                }
        }
        return ERR_NOIPADDRESS;
}

#ifdef	notdef
static void
dprint_dr_record(dr)
struct drange_desc *dr;
{
        bp_log("Queue link   x%lx\n", dr->dr_next);
        bp_log("Pointer to network information         x%lx\n", dr->dr_iface);
        bp_log("First IP address in range              x%lx\n", dr->dr_start);
        bp_log("Last IP address in range               x%lx\n", dr->dr_end);
        bp_log("Number of IP addresses in range        %d\n", dr->dr_acount);
        bp_log("Number of IP addresses in free         %d\n", dr->dr_fcount);
        bp_log("Number of IP addresses on reclaimation queue %d\n", 
		dr->dr_rcount);
        bp_log("Threshold for turning on reclaimation  %d\n", dr->dr_thon);
        bp_log("Threshold for critical reclaimation    %d\n", dr->dr_thcritical);
        bp_log("Threshold for turning off reclaimation %d\n", dr->dr_thoff);
        bp_log("Time to wait before retrying addresses %ld\n", 
		dr->dr_time_addrretry);
        bp_log("Length of hardware address             %d\n", dr->dr_hwaddrlen);
        bp_log("Reclaimation state                     %d\n",(int)dr->dr_rstate);
        bp_log("Verification state                     %d\n",(int)dr->dr_vstate);
        bp_log("Time stamp for reclaimation            %ld\n", dr->dr_rtime);
        bp_log("Address being verified                 x%lx\n", dr->dr_raddr);
        bp_log("Pointer to table of addresses          x%lx\n", dr->dr_table);
        bp_log("uesdq x%lx  reclaimq                   x%lx  freeq x%lx\n", dr->dr_usedq, 
		dr->dr_reclaimq, dr->dr_freeq);
}
#endif


/*
 * Enter the critical reclaimation state.
 */
static void
da_enter_critical(dr)
struct drange_desc *dr;
{
        char ipa[16], ipb[16];
	char *ipc;

	ipc = inet_ntoa(dr->dr_start);
	strcpy(ipa, ipc);
	ipc = inet_ntoa(dr->dr_end);
	strcpy(ipb, ipc);

        if((dr->dr_rstate & R_OFF) == 0){
                dr->dr_vstate = V_SWAIT;	/* Enter critical, & R_OFF */
                dr->dr_rtime = 0;
        }
        dr->dr_rstate = R_CRITICAL;
        dr->dr_time_addrretry = 0;      /* Retry addresses as fast as possible. */
}

/*
 * Initialization	
 */
/*
 * Initialize the Dynamic address assignment module.
 */
int
da_init()
{
        q_init(&rtabq);
        return 0;
}

/*
 * Begin dynamic address service for a network.
 */
int
da_serve_net(iface, rstart, rend)
struct iface *iface;		/* Pointer to lnet record. */
int32 rstart;			/* First address in range. */
int32 rend;			/* Last address in range. */
{
	struct drange_desc *dr;	/* Pointer to the range descriptor. */
	struct daddr *da;	/* Pointer to an address structure. */
	int32 rcount;		/* Number of addresses range. */
	time_t now;		/* Current time. */
	uint16 i;
	char ipc[16], ipd[16];

        /* Find the network table */
        for(dr = (struct drange_desc *) rtabq.head; dr != NULL;
	 dr = dr->dr_next){
                if(iface == dr->dr_iface)
                        break;
        }

	
	if(dr == NULL){
		/* If there is no network table, allocate a new one
		 *
 		 * Allocate the memory I need.
 		 */
		dr = (struct drange_desc *) calloc(1, sizeof(*dr));
		if(dr == NULL) 
			return E_NOMEM;
	} else if((dr->dr_start != rstart) || (dr->dr_end != rend)) 
		/* If the range is different, create a new range */
		free(dr->dr_table);
	else
		return 0; /* There is no change, return */


	rcount = (rend - rstart) + 1;
	da = (struct daddr *) calloc(1,(sizeof (*da) + iface->iftype->hwalen) * rcount);
	if(da == NULL) 
		return E_NOMEM;

	/* 
	 * Got the memory, fill in the structures.
	 */
	dr->dr_iface = iface;
	dr->dr_start = rstart;
	dr->dr_end = rend;
	dr->dr_acount = rcount;
	dr->dr_fcount = 0;
	dr->dr_rcount = 0;
	dr->dr_thon = (rcount * THRESH_ON) / 100;
	dr->dr_thcritical = THRESH_CRITICAL;
	dr->dr_thoff = (rcount * THRESH_OFF) / 100;
	dr->dr_time_addrretry = 0;
        dr->dr_hwaddrlen = iface->iftype->hwalen;
	dr->dr_rstate = R_OFF;
	dr->dr_vstate = V_SWAIT;			/* Initialize */
	dr->dr_rtime = 0;
	dr->dr_raddr = NULL;
	dr->dr_table = da;

	/* 
	 * Fill in the table and link them all onto the used list.
	 */
	time(&now);
	for(i = 0, da = dr->dr_table; i < dr->dr_acount; ++i, da = da_getnext(dr, da)){
		da->da_addr = rstart++;
		da->da_time = 0;		/* Initiallize at 0, only here */
		q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
	}
	/* and set up the timer stuff */
	if(rtabq.head == NULL){
		set_timer(&da_timer,TIME_RWAIT*1000L);
       		da_timer.func = da_runtask;
	       	da_timer.arg = (void *) 0;
		start_timer(&da_timer);
	}
	q_enqueue(&rtabq,(struct q_elt *)dr);
	da_enter_critical(dr);	/* Start reclaiming some of these addresses. */

	iptoa(dr->dr_start, ipc);
	iptoa(dr->dr_end, ipd);
	bp_log("DynamicIP range: %s - %s\n", ipc, ipd);
	return 0;
}


/*
 * Routines to implement a simple forward linked queue.
 */

/*
 *      q_init()
 *      Initialize simple Q descriptor
 */
static void
q_init(queue)
struct q *queue;
{
        queue->head = 0;
        queue->tail = 0;
}


/*
 *      q_enqueue()
 *              Enqueue an element in a simple Q.
 */
void
q_enqueue(queue, elem)
struct q *queue;
struct q_elt *elem;
{
        struct q_elt *last;

        if(queue->tail != NULL){  /* If not empty Q... */
                last = (struct q_elt *) queue->tail;
                last->next = elem;
        }
        else
		queue->head = (char *) elem;

        queue->tail = (char *) elem;
        elem->next = NULL;
}


/*
 *      q_dequeue       ()
 *      Pull an element off of the head of a Q.
 */
struct q_elt *
q_dequeue(queue)
struct q *queue;
{
        struct q_elt *elem;

        if(queue->head == NULL)
		return NULL; /* return NULL when empty Q */
        elem = (struct q_elt *) queue->head;
        queue->head = (char *) elem->next;
        elem->next = NULL;
        if(queue->head == NULL)
		queue->tail = NULL;
        return elem;
}


/*
 *      Remove an element from the middle of a queue.  Note that
 *      there is no mutex here, so this shouldn't be used on
 *      critical Qs
 */

static int
q_remove(source_queue, qel)
struct q *source_queue;
struct q_elt *qel;
{
        struct q_elt *prev, *e;

        /*   Case : removing first in Q */

        if(qel == (struct q_elt *) source_queue->head){
                source_queue->head = (char *)qel->next;  /* trying to remove first in queue... */
                if(source_queue->head == NULL)  	/* nothing left... */
                        source_queue->tail = NULL; 	/* blank out the Q */
                else if(source_queue->head == source_queue->tail){ /* One thing left */
                        e = (struct q_elt *) source_queue->head; /* As insurance, set it's next to NULL. */
                        e->next = NULL;
                }
                return 0;
        }

        /* find Q element before qel, so that we can link around qel */
        for(prev = (struct q_elt *) source_queue->head; prev->next != qel; prev = prev->next)
                if(prev == NULL)
                        return 1;

        /* Case : Removing last in Q */

        if(qel == (struct q_elt *) source_queue->tail){     /* trying to remove last one in queue... */
                prev->next = NULL;   /* there is a prev elt, since we return on first */
                source_queue->tail = (char *) prev;
                return 0;
        }

        /*  else, removing a queue element in the middle...  */
        prev->next = qel->next;
        return 0;
}

/*
 * Support Routines
 */

static void
iptoa(ipaddr, ipstr)
int32 ipaddr;
char ipstr[16];
{
	char *tmpStr;

	tmpStr = inet_ntoa(ipaddr);
	strcpy(ipstr, tmpStr);
}


#ifdef	notdef
static  void
build_hex_string(fromstr, len, tostr)
char *fromstr; int  len;
char *tostr;
{
	int i;

	for(i=0; i < len; i++){
		sprintf(tostr, "%02x", fromstr[i]);
		tostr++;
		tostr++;
	}
	fromstr[len] = 0;
}
#endif