sources/liblfds/queue/queue_query.c File Reference

#include "queue_internal.h"

Go to the source code of this file.

Functions
void	queue_query (struct queue_state *qs, enum queue_query_type query_type, void *query_input, void *query_output)
void	queue_internal_validate (struct queue_state *qs, struct validation_info *vi, enum data_structure_validity *queue_validity, enum data_structure_validity *freelist_validity)

---

Function Documentation

void queue_internal_validate	(	struct queue_state *	qs,
		struct validation_info *	vi,
		enum data_structure_validity *	queue_validity,
		enum data_structure_validity *	freelist_validity
	)

Definition at line 38 of file queue_query.c.

References and, queue_state::dequeue, freelist_query(), FREELIST_QUERY_ELEMENT_COUNT, FREELIST_QUERY_VALIDATE, queue_state::fs, validation_info::max_elements, validation_info::min_elements, queue_element::next, QUEUE_POINTER, VALIDITY_INVALID_ADDITIONAL_ELEMENTS, VALIDITY_INVALID_LOOP, VALIDITY_INVALID_MISSING_ELEMENTS, and VALIDITY_VALID.

Referenced by queue_query().

{
  struct queue_element
    *qe,
    *qe_slow,
    *qe_fast;

  atom_t
    element_count = 0,
    total_elements;

  struct validation_info
    freelist_vi;

  /* TRD : vi can be 0 */
  *queue_validity = VALIDITY_VALID;

  qe_slow = qe_fast = (struct queue_element *) qs->dequeue[QUEUE_POINTER];

  /* TRD : first, check for a loop
           we have two pointers
           both of which start at the dequeue end of the queue
           we enter a loop
           and on each iteration
           we advance one pointer by one element
           and the other by two

           we exit the loop when both pointers are 0
           (have reached the end of the queue)

           or

           if we fast pointer 'sees' the slow pointer
           which means we have a loop
  */

  if( qe_slow != 0 )
    do
    {
      qe_slow = qe_slow->next[QUEUE_POINTER];

      if( qe_fast != 0 )
        qe_fast = qe_fast->next[QUEUE_POINTER];

      if( qe_fast != 0 )
        qe_fast = qe_fast->next[QUEUE_POINTER];
    }
    while( qe_slow != 0 and qe_fast != qe_slow );

  if( qe_fast != 0 and qe_slow != 0 and qe_fast == qe_slow )
    *queue_validity = VALIDITY_INVALID_LOOP;

  /* TRD : now check for expected number of elements
           vi can be 0, in which case we do not check
           we know we don't have a loop from our earlier check
  */

  if( *queue_validity == VALIDITY_VALID and vi != 0 )
  {
    qe = (struct queue_element *) qs->dequeue[QUEUE_POINTER];

    while( qe != 0 )
    {
      element_count++;
      qe = (struct queue_element *) qe->next[QUEUE_POINTER];
    }

    /* TRD : remember there is a dummy element in the queue */
    element_count--;

    if( element_count < vi->min_elements )
      *queue_validity = VALIDITY_INVALID_MISSING_ELEMENTS;

    if( element_count > vi->max_elements )
      *queue_validity = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
  }

  /* TRD : now we validate the freelist

           we may be able to check for the expected number of
           elements in the freelist

           if the caller has given us an expected min and max
           number of elements in the queue, then the total number
           of elements in the freelist, minus that min and max,
           gives us the expected number of elements in the
           freelist
  */

  if( vi != 0 )
  {
    freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, 0, (void *) &total_elements );

    /* TRD : remember there is a dummy element in the queue */
    total_elements--;

    freelist_vi.min_elements = total_elements - vi->max_elements;
    freelist_vi.max_elements = total_elements - vi->min_elements;

    freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, (void *) &freelist_vi, (void *) freelist_validity );
  }

  if( vi == 0 )
    freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, 0, (void *) freelist_validity );

  return;
}

void queue_query	(	struct queue_state *	qs,
		enum queue_query_type	query_type,
		void *	query_input,
		void *	query_output
	)

Definition at line 10 of file queue_query.c.

References freelist_query(), FREELIST_QUERY_ELEMENT_COUNT, queue_state::fs, queue_internal_validate(), QUEUE_QUERY_ELEMENT_COUNT, and QUEUE_QUERY_VALIDATE.

Referenced by hlx_group_get_size().

{
  /* TRD : query_type can be any value in its range */
  /* TRD : query_input can be 0 */

  switch( query_type )
  {
    case QUEUE_QUERY_ELEMENT_COUNT:
      freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, 0, query_output );
    break;

    case QUEUE_QUERY_VALIDATE:
      /* TRD : query_input can be 0 */

      queue_internal_validate( qs, (struct validation_info *) query_input, (enum data_structure_validity *) query_output, ((enum data_structure_validity *) query_output)+1 );
    break;
  }

  return;
}