3.4.2.2 Referable Queue Declarable Data Type Definition

The interpreters will require some struct x1f4_datatype_type definition to allow declarations of data of such type.

See struct x1f4_datatype_type.

struct x1f4_datatype_type data_type = {
    "decq",
    flat_decq,
    line_decq,
    link_decq,
    flat_decq,
    HERE_DECQ,
    4,
    NULL
};

The definition specifies some 4 characters long `decq' name and some HERE_DECQ id for the data type. HERE_DECQ is some integral value, better greater than X1f4_E4_LAST.

See Symbolic Types.

The pre-initializing routine (pre-initializing helps with early program execution termination) does little:

int
link_decq(void *context, void *subtext, void **address)
{
    *address = NULL;

    return 0;
}

See Execution Completion Cleanup.

The initializing routine allocates some data of the string representation struct this_type type and sets it to some sensible value (the reference counter to 1). The link field needs be setup as some NULL value and a pointer to some reference tracking routine, call it near_decq.

See Reference Tracking Mechanics.

int
line_decq(void *context, void *subtext, void **address)
{
    int status;
    struct this_type *this_data;

    allocate memory for data, setup the actual queue object, set status to
    operation success

    if (status) {
    } else {
	this_data->node.call = 1;

	setup the this_data->node.pset pointer set, set status to operation
	success

	if (status) {
	    dispose of the actual queue object, free memory for data
	} else {
	    this_data->link.miss = near_decq;
	    this_data->link.slip = NULL;

	    *address = (void *) this_data;
	}
    }

    return status;
}

Declare some routine that actually removes one (variable held) reference and destroys data upon reaching null reference count:

int side_decq(void *, void *, void *);

and the routine that accounts for references being removed:

int
flat_decq(void *context, void *subtext, void **address)
{
    int status;
    struct this_type *this_data;

    this_data = *address;
    if (this_data) {
	status = side_decq(context, subtext, this_data);
	if (status) {
	} else {
	    *address = NULL;
	}
    } else {
	status = 0;
    }

    return status;
}

Upon successful operation the routine sets data to the pre-initialized NULL value.

The routine actually removing references needs to decrement the reference count. Upon reaching zero, the queue object needs dismantled. And that will be it, if not for reference cycles.

See Referable Objects.

If the reference count reaches not zero call some routine to detect cycles and if necessary, break them.

int
side_decq(void *context, void *subtext, void *data)
{
    int status;
    struct this_type *this_data;

    this_data = data;
    if (!this_data) {
	status = 0;
    } else {
	unsigned call;

	call = this_data->node.call;
	call--;
	if (call) {
	    this_data->node.call = call;

	    /*
	     * reference count not zero, need to check for cycles
	     */
	    status = mind_decq(context, subtext, this_data);
	} else {
	    /*
	     * reset reference count so that reference removals triggered by
	     * current operation do not loop endlessly
	     */
	    this_data->node.call = 0;

	    clear the actual queue - remove all its content

	    dispose of the this_data->node.pset pointer set

	    destroy actual queue object

	    free memory for data

	    set status to operation success
	}
    }

    return status;
}

The routine called for non zero reference count detects cycles and if positive (about cycles) sets the reference count to 1 and calls the reference removing routine for object final destruction.

int
mind_decq(void *context, void *subtext, void *data)
{
    int linked, status;

    linked = long_decq(context, subtext, data);
    if (linked) {
	/*
	 * no cycles
	 */
	status = 0;
    } else {
	((struct this_type *) data)->node.call = 1;

	status = side_decq(context, subtext, data);
    }

    return status;
}

The cycle detection routine may need to visit the objects holding reference to the (queue) object.

See Detecting Cycles.

Such objects are known (and visited) by their struct x1f4_nodelink_type feature.

See struct x1f4_nodelink_type.

See Reference Tracking Mechanics.

The objects visited need to be flagged as visited (so that the cycle detection does not run itself endlessly). The flags are pointers, used to build a linked list recording the visited objects, list needed to reset the flags once the cycle detection completes.

Each struct x1f4_nodelink_type record describes some routine, visiting the object embedding the record.

Such routine checks in order whether the object has already been visited, whether the object itself is variable referred and whether the objects referring the object are variable referred, stopping at the first positive test.

For the example queue data type, the visiting routing is the aforementioned near_decq.

int
near_decq(void *context, struct x1f4_nodelink_type **link,
	  struct x1f4_nodelink_type *data)
{
    int linked;

    /*
     * check whether object was already visited
     */
    if (data->slip) {
	/*
	 * need to report possible cycle detected
	 */
	linked = 0;
    } else {
	struct this_type *this_data;

	this_data = (void *)
	    ((char *) data - offsetof(struct this_type, link));

	/*
	 * compare the reference count and the pointer set size
	 */
	if (this_data->node.call != pset size) {
	    linked = 1;
	} else {
	    /*
	     * set visited flag / pointer to previously visited object
	     */
	    data->slip = *link;

	    /*
	     * update the list of visited objects
	     */
	    *link = data;

	    /*
	     * iterate over the set of objects referring the queue one
	     */
	    if (pset size) {
		for each pointer in the pointer set
		    linked = ((struct x1f4_nodelink_type *) pointer)->miss
			(context, link, pointer)
		    if (linked) {
			break;
		    }
	    } else {
		linked = 1;
	    }
	}
    }

    return linked;
}

Finally, the cycle detection routine:

int
long_decq(void *context, void *subtext, void *data)
{
    int linked;
    struct this_type *this_data;

    this_data = data;

    /*
     * compare the reference count and the pointer set size
     */
    if (this_data->node.call != pset size) {
	linked = 1;
    } else {
	/*
	 * iterate over the set of objects referring the queue one
	 */
	if (pset size) {
	    struct x1f4_nodelink_type *link = NULL;

	    linked = 0;

	    for each pointer in the pointer set
		linked = ((struct x1f4_nodelink_type *) pointer)->miss
		    (context, &link, pointer)
		if (linked) {
		    break;
		}

	    /*
	     * by now linked is indicating whether reference cycles had formed.
	     */

	    /*
	     * reset visited flags (may skip if cycles were detected)
	     */
	    if (linked) {
		while (link) {
		    struct x1f4_nodelink_type *next;

		    next = link->slip;
		    link->slip = NULL;

		    link = next;
		}
	    }
	} else {
	    linked = 1;
	}
    }

    return linked;
}