+/* Clear out contents of FIFO; act as if it was empty. Return PC
+ pointing to one-past-last word. */
+
+unsigned_4
+pke_fifo_flush(struct pke_fifo* fifo)
+{
+ /* don't modify any state! */
+ return fifo->origin + fifo->next;
+}
+
+
+
+/* Clear out contents of FIFO; make it really empty. */
+
+void
+pke_fifo_reset(struct pke_fifo* fifo)
+{
+ int i;
+
+ /* clear fifo quadwords */
+ for(i=0; i<fifo->next; i++)
+ {
+ zfree(fifo->quadwords[i]);
+ fifo->quadwords[i] = NULL;
+ }
+
+ /* reset pointers */
+ fifo->origin = 0;
+ fifo->next = 0;
+}
+
+
+
+/* Make space for the next quadword in the FIFO. Allocate/enlarge
+ FIFO pointer block if necessary. Return a pointer to it. */
+
+struct fifo_quadword*
+pke_fifo_fit(struct pke_fifo* fifo)
+{
+ struct fifo_quadword* fqw;
+
+ /* out of space on quadword pointer array? */
+ if(fifo->next == fifo->length) /* also triggered before fifo->quadwords allocated */
+ {
+ struct fifo_quadword** new_qw;
+ unsigned_4 new_length = fifo->length + PKE_FIFO_GROW_SIZE;
+
+ /* allocate new pointer block */
+ new_qw = zalloc(new_length * sizeof(struct fifo_quadword*));
+ ASSERT(new_qw != NULL);
+
+ /* copy over old contents, if any */
+ if(fifo->quadwords != NULL)
+ {
+ /* copy over old pointers to beginning of new block */
+ memcpy(new_qw, fifo->quadwords,
+ fifo->length * sizeof(struct fifo_quadword*));
+
+ /* free old block */
+ zfree(fifo->quadwords);
+ }
+
+ /* replace pointers & counts */
+ fifo->quadwords = new_qw;
+ fifo->length = new_length;
+ }
+
+ /* sanity check */
+ ASSERT(fifo->quadwords != NULL);
+
+ /* allocate new quadword from heap */
+ fqw = zalloc(sizeof(struct fifo_quadword));
+ ASSERT(fqw != NULL);
+
+ /* push quadword onto fifo */
+ fifo->quadwords[fifo->next] = fqw;
+ fifo->next++;
+ return fqw;
+}
+
+
+
+/* Return a pointer to the FIFO quadword with given absolute index, or
+ NULL if it is out of range */
+
+struct fifo_quadword*
+pke_fifo_access(struct pke_fifo* fifo, unsigned_4 qwnum)
+{
+ struct fifo_quadword* fqw;
+
+ if((qwnum < fifo->origin) || /* before history */
+ (qwnum >= fifo->origin + fifo->next)) /* after last available quadword */
+ fqw = NULL;
+ else
+ {
+ ASSERT(fifo->quadwords != NULL); /* must be allocated already */
+ fqw = fifo->quadwords[qwnum - fifo->origin]; /* pull out pointer from array */
+ ASSERT(fqw != NULL); /* must be allocated already */
+ }
+
+ return fqw;
+}
+
+
+/* Authorize release of any FIFO entries older than given absolute quadword. */
+void
+pke_fifo_old(struct pke_fifo* fifo, unsigned_4 qwnum)
+{
+ /* do we have any too-old FIFO elements? */
+ if(fifo->origin + PKE_FIFO_ARCHEOLOGY < qwnum)
+ {
+ /* count quadwords to forget */
+ int horizon = qwnum - (fifo->origin + PKE_FIFO_ARCHEOLOGY);
+ int i;
+
+ /* free quadwords at indices below horizon */
+ for(i=0; i < horizon; i++)
+ zfree(fifo->quadwords[i]);
+
+ /* move surviving quadword pointers down to beginning of array */
+ for(i=horizon; i < fifo->next; i++)
+ fifo->quadwords[i-horizon] = fifo->quadwords[i];
+
+ /* clear duplicate pointers */
+ for(i=fifo->next - horizon; i < fifo->next; i++)
+ fifo->quadwords[i] = NULL;
+
+ /* adjust FIFO pointers */
+ fifo->origin = fifo->origin + horizon;
+ fifo->next = fifo->next - horizon;
+ }
+}
+
+
+
+