c - Thread-safe implementation of is_empty in a queue datastructure -

i trying create thread-safe queue, , while bulk of operations

 queue *queue_create_empty(void);  void queue_enqueue(queue *q, const void *value, const size_t value_size);  void *queue_dequeue(queue *q);  void queue_destroy(queue *q, void (*freefunc)(void *value)); 

i finding 1 particularily elusive,

 bool queue_is_empty(const queue *q); 

in particular if function definition is

 bool queue_is_empty(const queue *q) {      assert(q);       pthread_mutex_lock(q->mutex);      bool ret = q->is_empty;      pthread_mutex_unlock(q->mutex);       /*        * here there possibility of race condition, queue may       * empty @ point, , therefore return value misleading       */      return ret;  } 

then there possibility of race-condition. last comment

here there possibility of race condition, queue may empty @ point, , therefore return value misleading

describes issue.

i have defined datastructure such,

 typedef struct queue {      element *head;      element *tail;       /* lock read/write operations */      pthread_mutex_t *mutex;       /* condition variable whether or not queue empty */      /* negation in variable names poor practice */      /* solution here considering conditional variable api */      /* (signal/broadcast) */      pthread_cond_t *not_empty;       /* flag used gauge when wait on not_empty condition variable */      bool is_empty;       /* flag set whenever queue destroyed */      bool cancel;  } queue; 

and implementation of other functions have worked around inadequate queue_is_empty function checking value of q->is_empty since have taken lock on structure before checking value.

the queue_dequeue function serves example of 1 want know if queue empty. see first if-statement.

 void *queue_dequeue(queue *q) {      assert(q);       void *value = null;      pthread_mutex_lock(q->mutex);       /* have mutex-lock here, can atomically check flag */      if (q->is_empty) {          /* not have check cancel flag here, if thread awoken */          /* in destruction context waiting thread awoken, later */          /* if statement checks flag before modification of queue */           /* allows other threads access lock, signalling thread */          /* when thread awoken wait queue not empty, or */          /* queue destroyed */          pthread_cond_wait(q->not_empty, q->mutex);      }       /* have mutex lock again may atomically check both flags */      if (!q->cancel && !q->is_empty) {          value = q->head->value;          if (q->head->next) {                          q->head = q->head->next;              free(q->head->previous);               /* make dereferencing dangling pointers crash program */              q->head->previous = null;          } else {              free(q->head);              q->head = null;              q->is_empty = true;          }              }       pthread_mutex_unlock(q->mutex);      return value;   } 

how expose thread-safe queue_is_empty function?

you've discovered reason why locking, threading , concurrency in general hard. it's easy create few wrapper functions obtain , release locks , prevent crashes data corruption, it's hard locking right when depend on state earlier accesses.

i'd argue function queue_is_empty incorrect because exists @ all. cannot possibly return useful value because, discovered, return value stale before return it. since function cannot return useful return value should not exist. , need think hard api provide.

one option make locking responsibility of callers. caller have like:

queue_lock(q); if (!queue_is_empty(q))     do_something(q); queue_unlock(q); 

you run issues error handling , returns functions, lock state changes around functions not part of queue interface, etc. , have more 1 of locks need manage lock ordering prevent deadlocks.

another option reduce api provide safe operations. enqueue , dequeue work correctly. need is_empty? for? avoid waiting queue element when queue empty? can not solve dequeue_without_waiting instead? etc.