/* deq.c
 * implement deques of 12-word blocks in DECUS C
 * tasks can perform send/receives to operate on deques
 */
/* a deque is a double-ended queue
 * it is called a deque because of the ellision of "double", "ended" and
 * "queue" and because it is like a deck of cards: you can't get at the
 * middle but you can push/pull cards at both ends.
 * the operations on a deque are to push/pull from the A or the B end
 * of the deque:
 *
 *	A end		<-> X-X-X-X-X-X-X-X <->		B end
 *			 *		     *
 *				deque
 *
 *			* == push or pull one object here
 */

/* 31 deques are maintained.
 * all are public resources - no priveliges are enforced
 * except that a task can exclude all other tasks from a deque
 * an operation is when a task sends a packet to ...DEQ
 * deq guarentees to reply with exactly one packet.
 * the contents of the return packet depends on the operator packet
 * deque number 0 is special: it is returned to indicate errors and sent
 * to indicate "don't care"
 */

/* operator packets have the following format:
 *
 *	+---------------------------------------------------------------+
 *	| operation byte		| sender's 8-bit private code	|
 *	|-------------------------------|				|
 *	| 3-bit	    | deque number	|				|
 *	| operation | [0:31]		|				|
 *	| code	    |			|				|
 *	+---------------------------------------------------------------+
 *	|	12 words of sender's data : meaning depends on op-code	|
 *	+---------------------------------------------------------------+
 */
/* reply packets look the same: the deque number is sometimes changed
 * and the data changes. The sender's private byte is never changed so
 * senders can use this to co-relate requests and replies.
 */
/* opcodes look like:
 *
 *	+---------------------------------------+
 *	|	A/B	|	op (2 bits)	|
 *	+---------------------------------------+
 *
 *	operations are:
 *	00	special
 *		if A/B = 0 then	detach from the nominated deque
 *				this decrements the usage count of the deque
 *				when the usage count of the deque falls to 0
 *				then the data in the deque is lost
 *				specifying 0 as the deque number is illegal
 *				reply contains the deque number detached
 *				if the reply has a zero deque number then
 *				the detach request failed.
 *				a detach request might fail if the owner of
 *				the deque was not the requesting task
 *				the data part of the request should be 0
 *				to allow for future foolishness
 *		if A/B = 1 then attach to a deque
 *				if no deque number is given then don't
 *				care which deque number is used,
 *				but it must be a fresh deque, not one in use.
 *				reply deque number is 0 if deque could
 *				not be attached else is number of deque
 *				attached.
 *				the first two words of the data part are
 *				0 or a task name. If a task name and if
 *				currently no task owns the deque, then the
 *				named task will now have exclusive access
 *				to the deque.
 *				the rest of the data part of the request
 *				should be 0 to allow for future foolishness
 ** for the rest of the op-codes: each deque has two ends:
 ** arbitrarily named "A" and "B". Each command operates on the
 ** "A" end unless the A/B bit is set: then it works on the "B" end
 *	01	copy
 *		return a copy of the block at the deque end
 *		do not change the deque
 *		ignore the data part of the request
 *		the data part of the request should be 0
 *		to allow for future foolishness
 *		such future extension might include accessing elements
 *		which are not at the end of the deque or gathering
 *		statistics about the deque.
 *		return deque number of 0 if deque is empty
 *	10	pull
 *		as for "copy" command but remove block if it exists
 *		the data part of the request should be 0
 *		to allow for future foolishness
 *	11	push
 *		catenate data part to deque end
 *		nominating deque 0 is illegal
 *		return deque number 0 if failed
 *		only failure mode is "no more memory"
 */
/* as a convention ... don't use deque number 31. - it may mean something
 * special one day. In fact - keep deque numbers between 1-15. inclusive
 * because the high bit of the deque number may become the low bit of the
 * op-code in future versions!
 */


#include <stdio.h>
#include <cx.h>
#define decus

#define PACKETSIZE 13
#define DEQNUMBER 32
#define DATAOFFSET 1
#define EFN 0

				/* request packet op-codes */
#define SPEC 0
#define COPY 1
#define PULL 2
#define PUSH 3



				/* objects are organised in rings */

struct head			/* object header for ring of objects */
	{char	*b4;		/* points to previous object in ring */
	 char	*aft;		/* points to next object in ring */
	}
;

struct	deqhed			/* deque header */
	{struct	head	hed;	/* points to self if empty ring */
	 struct	rad50	owner;	/* 0 if public deque
				   task name that exclusively owns deque */
	 unsigned	usage;	/* number of tasks attached to deque */
	}
;

struct	object			/* the things we push and pull */
	{struct head	hed;	/* */
	 int		data[PACKETSIZE-DATAOFFSET];
	}
;

/*
 *
 *		a head:
 *
 *			+===============+
 *			|		|
 *	.b4:		|	*---------------+
 *			|		|	|
 *			+===============+	|
 *			|		|	|
 *	.aft:	+---------------*	|	|
 *		|	|		|	|
 *		|	+===============+	|
 *		|				|
 *		V				V
 *		"A" end				"B" end
 *
 */



int		tracer;		/* TRUE when desperately debugging */


main(argc,argv)
int		argc;
char		**argv;
{int		i;		/* scratch */
 struct deqhed	*d;		/* points to particular deq(hed) we work on */
 struct	deqhed	h[DEQNUMBER];	/* 0th element never used */
 int		inpack[PACKETSIZE+2];	/* incoming (request) packet */
 int		outpack[PACKETSIZE];	/* outgoing (reply) packet */
 int		b;		/* TRUE if A/B bit set */
 char		dsw;		/* dsw from exec calls */
 int		op;		/* 2-bit op code */
 int		deq;		/* the deq number */
 struct object	*o;		/* scratch */
 unsigned	objsize;	/* size in chars of object */
 int		trace;		/* TRUE if tracing */
 char		ascii[7];	/* ASCII task name as string */
 int		printf();

 objsize = sizeof(*o);


 trace = argc>1;
 tracer = argc>2;

				/* initialise */
 for	(i=31; i; i--)
	{d = h+i;		/* d points to particular deqhed */
	 d->hed.b4 = d;
	 d->hed.aft = d;
	 d->usage = 0;
	 d->owner.w[0] = 0;
	 d->owner.w[1] = 0;
	}
 ;
 d = h;			/* as a debug measure, fill deque 0 with junk */
 d->hed.b4 = 1;			/* bad address */
 d->hed.aft = 1;
 d->usage = 42;
 d->owner.w[0] = 42;
 d->owner.w[1] = 42;

 while(1)			/* repeat until we are shot */
	{
				/* receive a request */
	 while	((dsw=rcst(NULL,inpack)) == IS_SET)	/* ignore false alarms */
	 ;

	 op = inpack[2] >> 8 & 0xFF;	/* second byte of packet */
	 deq = op & 0x1F;
	 op = op >> 5;
	 b = op & 0x4;
	 op = op & 0x3;
	 d = h+deq;			/* d points to particular deque header */
					/* copy in packet to out packet */
	 copy(outpack,inpack+2,PACKETSIZE*sizeof(int));

	 if	(trace)
		{r50toa(ascii,inpack,2);
		 ascii[6]=0;
		 printf("from task %s  op=%d b=%d deque=%d\n",ascii,op,b,deq);
		 wblock(inpack+2,26,printf);
		}
	 ;

	 switch	(op)
		{
	 case SPEC:
		 if	(b)
			{/* attach to deq */
			 if	(deq==0)
				{for	(deq=DEQNUMBER-1,d=h+DEQNUMBER; deq; deq--)
					{if	(!(--d)->usage)
						{if	(trace)
							{printf("attach:chose deque %d\n",deq);
							}
						 ;
						 break;
						}
					 ;
					}
				 ;
				}
			 ;
			 /* here with a deq number */
			 if	(deq)
				{if	(bufeq(&d->owner,4))
					{if	(!bufeq(inpack+2+DATAOFFSET,4))
						{copy	(&d->owner,inpack+2+DATAOFFSET,4);
						 if	(trace)
							{printf("task %s now owns deque %d\n",ascii,deq);
							}
						 ;
						}
					 ;
					}
				 else
					{if	(!bufcmp(&d->owner,inpack,4))
						{if	(trace)
							{r50toa(ascii,&d->owner,2);
							 printf("but task %s owns deque %d so attach fails\n",ascii,deq);
							}
						 ;
						 deq = 0;	/* private - hands off! */
						}
					 ;
					}
				 ;
				}
			 ;
			 /* deq = 0 if failed */
			 if	(deq)
				{d->usage++;
				 if	(trace)
					{printf("deque %d usage count now %d\n",deq,d->usage);
					}
				 ;
				}
			 ;
			}
		else	/* detach */
			{deqcheck(trace,&deq,&d,h,inpack);
			 if	(deq)
				{if	(!(--(d->usage)))
					{/* last user detached : annihilate deque */
					 i = 0;
					 while	(!emptyp(d))
						{aftoff(d);
						 i++;
						}
					 ;
					 if	(trace)
						{printf("deque %d now unused :%d objects annihilated\n",deq,i);
						}
					 ;
					}
				 ;
				 if	(trace)
					{printf("detach from deque %d leaves usage count at %d\n",deq,d->usage);
					}
				 ;
				}
			 ;
			}
		;
		break;
	 case COPY:
		deqcheck(trace,&deq,&d,h,inpack);
		if	(deq && emptyp(d))
			{if	(trace)
				{printf("can't copy from empty deque %d\n",deq);
				}
			 ;
			 deq = 0;
			}
		;
		if	(deq)
			{o = b?d->hed.b4:d->hed.aft;
			 if	(tracer)
				{printf("o=%Xx d=%Xx\n",o,d);
				 objdump(o);
				}
			 ;
			 copy(outpack+DATAOFFSET,o->data,(PACKETSIZE-DATAOFFSET)*sizeof(int));
			}
		;
		break;
	 case PULL:
		deqcheck(trace,&deq,&d,h,inpack);
		if	(deq && emptyp(d))
			{if	(trace)
				{printf("can't pull from empty deque %d\n",deq);
				}
			 ;
			 deq = 0;
			}
		;
		if	(deq)
			{o = b?d->hed.b4:d->hed.aft;
			 if	(tracer)
				{printf("o=%Xx d=%Xx\n",o,d);
				 objdump(o);
				}
			 ;
			 copy(outpack+DATAOFFSET,o->data,(PACKETSIZE-DATAOFFSET)*sizeof(int));
			 if	(b)
				{b4off(d);
				}
			 else
				{aftoff(d);
				}
			 ;
			}
		;
		break;
	 case PUSH:
		deqcheck(trace,&deq,&d,h,inpack);
		if	(deq && !(b?b4on(d,objsize):afton(d,objsize)))
			{if	(trace)
				{printf("no room to push onto %c end of deque %d\n",b?'B':'A',deq);
				}
			 ;
			 deq = 0;	/* no room */
			}
		;
		if	(deq)
			{o = b?d->hed.b4:d->hed.aft;
			 if	(tracer)
				{printf("o=%Xx d=%Xx\n",o,d);
				}
			 ;
			 copy(o->data,inpack+2+DATAOFFSET,(PACKETSIZE-DATAOFFSET)*sizeof(int));
			 if	(tracer)
				{objdump(o);
				}
			 ;
			}
		;
		break;
	 default:
		if	(trace)
			{printf("impossible op = %d\n",op);
			}
		;
		deq = 0;
		break;
		}
	 ;
	 outpack[0] = outpack[0] & 0xE0FF | deq<<8 ;
	 if	(trace)
		{wblock(outpack,26,printf);
		 printf("\n");
		}
	 ;
	 dsw = sdat(inpack,outpack,EFN);
	 if	(dsw!=IS_SUC)	printf("\7dsw of sdat =%oo\n",dsw);
	 dsw = ustp(inpack);
	 if	(dsw!=IS_SUC && dsw !=IE_ITS)	printf("\7dsw of ustp =%oo\n",dsw);
	}
 ;
}



deqcheck(trace,deqp,dp,hp,inpack)	/* check deq access rights */
int		trace;		/* TRUE if tracing */
int		*deqp;		/* points to deq */
struct deqhed	**dp;		/* points to d */
struct deqhed	hp[DEQNUMBER];
int		inpack[PACKETSIZE+2];
{int		deq;
 struct deqhed	*d;
 char		ascii[7];	/* ASCII task name string */
 deq = *deqp;
 if	(trace)
	{r50toa(ascii,inpack,2);
	 ascii[6]=0;
	 printf("checking access of task %s to deque %d\n",ascii,deq);
	}
 ;
 if	(deq)
	{d = hp+deq;
	 if	(bufeq(&d->owner,4))
		{if	(!d->usage)
			{if	(trace)
				{printf("access denied: no task owns deque but usage count is zero\n");
				}
			 ;
			 deq = 0;
			}
		 ;
		}
	 else
		{if	(!bufcmp(&d->owner,inpack,4))
			{if	(trace)
				{r50toa(ascii,&d->owner,2);
				 printf("access denied: task %s owns deque %d\n",ascii,deq);
				}
			 ;
			 deq = 0;
			}
		 ;
		}
	 ;
	}
 ;
 *dp = d;
 *deqp = deq;			/* zero if failed */
 if	(trace && deq)
	{printf("access granted\n");
	}
 ;
}



int emptyp(d)
struct deqhed	*d;
{return(d->hed.b4 == &d->hed);
}


b4off(d)
struct deqhed	*d;
{struct	head	*hp,*hhp,*hhhp;
 hp = &d->hed;
 hhp = hp->b4;
 hhhp = hhp->b4;
 if	(tracer)
	{printf("aoff: d=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,hp,hhp,hhhp);
	 printf("aoff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 hp->b4 = hhhp;
 hhhp->aft = hp;
 if	(tracer)
	{printf("aoff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 mfree(hhp);
}


aftoff(d)
struct deqhed	*d;
{struct	head	*hp,*hhp,*hhhp;
 hp = &d->hed;
 hhp = hp->aft;
 hhhp = hhp->aft;
 if	(tracer)
	{printf("boff: d=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,hp,hhp,hhhp);
	 printf("boff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 hp->aft = hhhp;
 hhhp->b4 = hp;
 if	(tracer)
	{printf("boff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 mfree(hhp);
}


int	b4on(d,size)
struct deqhed	*d;
{struct head	*hp,*hhp,*hhhp;
 hp = &d->hed;
 hhhp = hp->b4;
 hhp = malloc(size);
 if	(tracer)
	{printf("aon: d=%Xx size=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,size,hp,hhp,hhhp);
	 printf("aon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 if	(!hhp)	return(0);
 hhp->b4 = hhhp;
 hhp->aft = hp;
 hhhp->aft = hhp;
 hp->b4 = hhp;
 if	(tracer)
	{printf("aon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 return	(1);
}


int	afton(d,size)
struct deqhed	*d;
{struct head	*hp,*hhp,*hhhp;
 hp = &d->hed;
 hhhp = hp->aft;
 hhp = malloc(size);
 if	(tracer)
	{printf("bon: d=%Xx size=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,size,hp,hhp,hhhp);
	 printf("bon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 if	(!hhp)	return(0);
 hhp->aft = hhhp;
 hhp->b4 = hp;
 hhhp->b4 = hhp;
 hp->aft = hhp;
 if	(tracer)
	{printf("bon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n"
	 ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft);
	}
 ;
 return	(1);
}


int	bufcmp(a,b,len)
char		*a;
char		*b;
unsigned	len;
{while	(len--)	if	(*a++!=*b++)	return (*--a<*--b?-1:1);
 return(0);
}


int	bufeq(a,len)
char		*a;
unsigned	len;
{int		r;
 r = 1;
 while	(len--)	if	(*a++)	{r=0; break;}
 if	(tracer)
	{printf("bufeq: returns %d\n",r);
	}
 ;
 return(r);
}


objdump(o)
struct	object	*o;
{int	printf();
 printf("dumping object at address %Xx: b4=%Xx aft=%Xx\n",o,o->hed.b4,o->hed.aft);
 wblock(o->data,(PACKETSIZE-DATAOFFSET)*2,printf);
}


wblock(buf,len,pf)
char	*buf;
int	len;
int	(*pf)();
{int	max;
 int	i;
 while	(len)
	{max = len>8 ? 8 : len;
	 for	(i = 0; i<max; i++)	(*pf)("%2x",buf[i]&0xFF);
	 for	(; i<8; i++)		(*pf)("  ");
	 				(*pf)("\t");
	 for	(i=0; i<max; i++)
		{(*pf)(" ");
		 wchar(buf[i],pf);
		}
	 ;
					(*pf)("\n");
	 len -= max;
	 buf += max;
	}
 ;
}

wchar(c,pf)
char	c;
int	(*pf)();
{(*pf)(c&0x80?"'":" ");
 c &= 0x7F;
 if	(c<040)
	{c+=0100;
	 (*pf)("^");
	}
 else
	{(*pf)(" ");
	}
 ;
 (*pf)("%c",c);
}
