#include "robust.h" #include char qe_errbuf[256]; /* macros for the queue structure (limits) */ #define MAXQ 1024 /* max number of queues */ #define MAXELT 3 /* max number of elements per queue */ /* the queue structure */ typedef int QELT; /* type of element being queued */ typedef struct queue { QTICKET ticket; /* contains unique queue ID */ QELT que[MAXELT]; /* the actual queue */ int head; /* head index in que of the queue */ int count; /* number of elements in queue */ } QUEUE; #define IOFFSET 0x1221 /* used to hide index number in ticket */ #define NOFFSET 0x0502 /* initial nonce */ /* variables shared by library routines */ static QUEUE *queues[MAXQ]; /* the array of queues */ /* nonce generator -- this */ static unsigned int noncectr = NOFFSET; /* MUST be non-zero always */ /* * generate a token; this is an integer: index number + OFFSET,,nonce * WARNING: each quantity must fit into 16 bits * * PARAMETERS: int index index number * RETURNED: QTICKET ticket of corresponding queue * ERRORS: QE_INTINCON * index + OFFSET is too big * * nonce is too big * * index is out of range * (qe_errbuf has disambiguating string) * EXCEPTIONS: none */ static QTICKET qtktref(unsigned int index) { unsigned int high; /* high 16 bits of ticket (index) */ unsigned int low; /* low 16 bits of ticket (nonce) */ /* sanity check argument; called internally ... */ if (index > MAXQ){ ERRBUF3("qtktref: index %u exceeds %d", index, MAXQ); return(QE_INTINCON); } /* * get the high part of the ticket (index into queues array, * offset by some arbitrary amount) * SANITY CHECK: be sure index + OFFSET fits into 16 bits as positive */ high = (index + IOFFSET)&0x7fff; if (high != index + IOFFSET){ ERRBUF3("qtktref: index %u larger than %u", index, 0x7fff - IOFFSET); return(QE_INTINCON); } /* * get the low part of the ticket (nonce) * SANITY CHECK: be sure nonce fits into 16 bits */ low = noncectr & 0xffff; if ((low != noncectr++) || low == 0){ ERRBUF3("qtktref: generation number %u exceeds %u\n", noncectr - 1, 0xffff - NOFFSET); return(QE_INTINCON); } /* construct and return the ticket */ return((QTICKET) ((high << 16) | low)); } /* * check a ticket number and turn it into an index * * PARAMETERS: QTICKET qno queue ticket from the user * RETURNED: int index from the ticket * ERRORS: QE_BADTICKET queue ticket is invalid because: * * index out of range [0 .. MAXQ) * * index is for unused slot * * nonce is of old queue * (qe_errbuf has disambiguating string) * QE_INTINCON queue is internally inconsistent because: * * one of head, count is uninitialized * * nonce is 0 * (qe_errbuf has disambiguating string) * EXCEPTIONS: none */ static int readref(QTICKET qno) { register unsigned index; /* index of current queue */ register QUEUE *q; /* pointer to queue structure */ /* get the index number and check it for validity */ index = ((qno >> 16) & 0xffff) - IOFFSET; if (index >= MAXQ){ ERRBUF3("readref: index %u exceeds %d", index, MAXQ); return(QE_BADTICKET); } if (queues[index] == NULL){ ERRBUF2("readref: ticket refers to unused queue index %u", index); return(QE_BADTICKET); } /* * you have a valid index; now validate the nonce; note we * store the ticket in the queue, so just check that (same * thing) */ if (queues[index]->ticket != qno){ ERRBUF3("readref: ticket refers to old queue (new=%u, old=%u)", ((queues[index]->ticket)&0xffff) - NOFFSET, (qno&0xffff) - NOFFSET); return(QE_BADTICKET); } /* * check for internal consistencies */ if ((q = queues[index])->head < 0 || q->head >= MAXELT || q->count < 0 || q->count > MAXELT){ ERRBUF3("readref: internal inconsistency: head=%u,count=%u", q->head, q->count); return(QE_INTINCON); } if (((q->ticket)&0xffff) == 0){ ERRBUF("readref: internal inconsistency: nonce=0"); return(QE_INTINCON); } /* all's well -- return index */ return(index); } /* * create a new queue * * PARAMETERS: none * RETURNED: QTICKET token (if > 0); error number (if < 0) * ERRORS: QE_BADPARAM parameter is NULL * QE_TOOMANYQS too many queues allocated already * QE_NOROOM no memory to allocate new queue * (qe_errbuf has descriptive string) * EXCEPTIONS: none */ QTICKET create_queue(void) { register int cur; /* index of current queue */ register QTICKET tkt; /* new ticket for current queue */ /* check for array full */ for(cur = 0; cur < MAXQ; cur++) if (queues[cur] == NULL) break; if (cur == MAXQ){ ERRBUF2("create_queue: too many queues (max %d)", MAXQ); return(QE_TOOMANYQS); } /* allocate a new queue */ if ((queues[cur] = malloc(sizeof(QUEUE))) == NULL){ ERRBUF("create_queue: malloc: no more memory"); return(QE_NOROOM); } /* generate ticket */ if (QE_ISERROR(tkt = qtktref(cur))){ /* error in ticket generation -- clean up and return */ (void) free(queues[cur]); queues[cur] = NULL; return(tkt); } /* now initialize queue entry */ queues[cur]->head = queues[cur]->count = 0; queues[cur]->ticket = tkt; return(tkt); } /* * delete an existing queue * * PARAMETERS: QTICKET qno ticket for the queue to be deleted * RETURNED: int error code * ERRORS: QE_BADPARAM parameter refers to deleted, unallocated, * or invalid queue (from readref()). * QE_INTINCON queue is internally inconsistent (from * readref()). * EXCEPTIONS: none */ int delete_queue(QTICKET qno) { register int cur; /* index of current queue */ /* * check that qno refers to an existing queue; * readref sets error code */ if (QE_ISERROR(cur = readref(qno))) return(cur); /* * free the queue and reset the array element */ (void) free(queues[cur]); queues[cur] = NULL; return(QE_NONE); } /* * add an element to an existing queue * * PARAMETERS: QTICKET qno ticket for the queue involved * int n element to be appended * RETURNED: int error code * ERRORS: QE_BADPARAM parameter refers to deleted, unallocated, * or invalid queue (from readref()). * QE_INTINCON queue is internally inconsistent (from * readref()). * QE_TOOFULL queue has MAXELT elements and a new one * can't be added * EXCEPTIONS: none */ int put_on_queue(QTICKET qno, int n) { register int cur; /* index of current queue */ register QUEUE *q; /* pointer to queue structure */ /* * check that qno refers to an existing queue; * readref sets error code */ if (QE_ISERROR(cur = readref(qno))) return(cur); /* * add new element to tail of queue */ if ((q = queues[cur])->count == MAXELT){ /* queue is full; give error */ ERRBUF2("put_on_queue: queue full (max %d elts)", MAXELT); return(QE_TOOFULL); } else{ /* append element to end */ q->que[(q->head+q->count)%MAXELT] = n; /* one more in the queue */ q->count++; } return(QE_NONE); } /* * take an element off the front of an existing queue * * PARAMETERS: QTICKET qno ticket for the queue involved * RETURNED: int error code or value * ERRORS: QE_BADPARAM bogus parameter because: * * parameter refers to deleted, invalid, * or unallocated queue (from readref()) * * pointer points to NULL address for * returned element * (qe_errbuf has descriptive string) * QE_INTINCON queue is internally inconsistent (from * readref()). * QE_EMPTY no elements so none can be retrieved * EXCEPTIONS: none */ int take_off_queue(QTICKET qno) { register int cur; /* index of current queue */ register QUEUE *q; /* pointer to queue structure */ register int n; /* index of element to be returned */ /* * check that qno refers to an existing queue; * readref sets error code */ if (QE_ISERROR(cur = readref(qno))) return(cur); /* * now pop the element at the head of the queue */ if ((q = queues[cur])->count == 0){ /* it's empty */ ERRBUF("take_off_queue: queue empty"); return(QE_EMPTY); } else{ /* get the last element */ q->count--; n = q->head; q->head = (q->head + 1) % MAXELT; return(q->que[n]); } /* should never reach here (sure ...) */ ERRBUF("take_off_queue: reached end of routine despite no path there"); return(QE_INTINCON); }