gw-prioqueue.c File Reference

#include "gw-config.h"
#include <pthread.h>
#include "thread.h"
#include "gwmem.h"
#include "gwassert.h"
#include "gwthread.h"
#include "gw-prioqueue.h"

Include dependency graph for gw-prioqueue.c:

Go to the source code of this file.

Data Structures
struct	element
struct	gw_prioqueue
Functions
void	queue_lock (gw_prioqueue_t *queue)
void	queue_unlock (gw_prioqueue_t *queue)
void	make_bigger (gw_prioqueue_t *queue, long items)
int	compare (struct element *a, struct element *b, int(*cmp)(const void *, const void *))
void	upheap (gw_prioqueue_t *queue, register long index)
void	downheap (gw_prioqueue_t *queue, register long index)
gw_prioqueue_t *	gw_prioqueue_create (int(*cmp)(const void *, const void *))
void	gw_prioqueue_destroy (gw_prioqueue_t *queue, void(*item_destroy)(void *))
long	gw_prioqueue_len (gw_prioqueue_t *queue)
void	gw_prioqueue_insert (gw_prioqueue_t *queue, void *item)
void	gw_prioqueue_foreach (gw_prioqueue_t *queue, void(*fn)(const void *, long))
void *	gw_prioqueue_remove (gw_prioqueue_t *queue)
void *	gw_prioqueue_get (gw_prioqueue_t *queue)
void *	gw_prioqueue_consume (gw_prioqueue_t *queue)
void	gw_prioqueue_add_producer (gw_prioqueue_t *queue)
void	gw_prioqueue_remove_producer (gw_prioqueue_t *queue)
long	gw_prioqueue_producer_count (gw_prioqueue_t *queue)

---

Function Documentation

int compare (  struct element *  a, struct element *  b, int(*)(const void *, const void *)  cmp )  [static]

Definition at line 116 of file gw-prioqueue.c. References element::item, and element::seq. Referenced by downheap(), and upheap(). { int rc; rc = cmp(a->item, b->item); if (rc == 0) { /* check sequence to guarantee order */ if (a->seq < b->seq) rc = 1; else if (a->seq > b->seq) rc = -1; } return rc; }

void downheap (  gw_prioqueue_t *  queue, register long  index )  [static]

Heapize down - our prioqueue - start index Definition at line 154 of file gw-prioqueue.c. References gw_prioqueue::cmp, compare(), gw_prioqueue_t, gw_prioqueue::len, and gw_prioqueue::tab. Referenced by gw_prioqueue_consume(), and gw_prioqueue_remove(). { struct element *v = queue->tab[index]; register long j; while (index <= queue->len / 2) { j = 2 * index; /* take the biggest child item */ if (j < queue->len && compare(queue->tab[j], queue->tab[j + 1], queue->cmp) < 0) j++; /* break if our item bigger */ if (compare(v, queue->tab[j], queue->cmp) >= 0) break; queue->tab[index] = queue->tab[j]; index = j; } queue->tab[index] = v; }

Here is the call graph for this function:

void gw_prioqueue_add_producer (  gw_prioqueue_t *  queue  )

Add producer to the priority queue - priority queue Definition at line 329 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, gw_prioqueue::producers, queue_lock(), and queue_unlock(). { gw_assert(queue != NULL); queue_lock(queue); queue->producers++; queue_unlock(queue); }

Here is the call graph for this function:

void* gw_prioqueue_consume (  gw_prioqueue_t *  queue  )

Remove biggest item from the priority queue, but block if producers available and none items in the queue - priority queue Returns: biggest item or NULL if none items and none producers in the queue Definition at line 303 of file gw-prioqueue.c. References downheap(), gw_assert, gw_prioqueue_t, gwthread_self(), element::item, gw_prioqueue::len, gw_prioqueue::mutex, Mutex::mutex, gw_prioqueue::nonempty, Mutex::owner, gw_prioqueue::producers, queue_lock(), queue_unlock(), and gw_prioqueue::tab. { void *ret; gw_assert(queue != NULL); queue_lock(queue); while (queue->len == 1 && queue->producers > 0) { queue->mutex->owner = -1; pthread_cond_wait(&queue->nonempty, &queue->mutex->mutex); queue->mutex->owner = gwthread_self(); } if (queue->len > 1) { ret = queue->tab[1]->item; gw_free(queue->tab[1]); queue->tab[1] = queue->tab[--queue->len]; downheap(queue, 1); } else { ret = NULL; } queue_unlock(queue); return ret; }

Here is the call graph for this function:

gw_prioqueue_t* gw_prioqueue_create (  int(*)(const void *, const void *)  cmp  )

Create priority queue - compare function Returns: newly created priority queue Definition at line 174 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, make_bigger(), gw_prioqueue::mutex, mutex_create, and gw_prioqueue::producers. Referenced by main(), smsc_at2_create(), and smsc_emi2_create(). { gw_prioqueue_t *ret; gw_assert(cmp != NULL); ret = gw_malloc(sizeof(*ret)); ret->producers = 0; pthread_cond_init(&ret->nonempty, NULL); ret->mutex = mutex_create(); ret->tab = NULL; ret->size = 0; ret->len = 0; ret->seq = 0; ret->cmp = cmp; /* put NULL item at pos 0 that is our stop marker */ make_bigger(ret, 1); ret->tab[0] = gw_malloc(sizeof(**ret->tab)); ret->tab[0]->item = NULL; ret->tab[0]->seq = ret->seq++; ret->len++; return ret; }

Here is the call graph for this function:

void gw_prioqueue_destroy (  gw_prioqueue_t *  queue, void(*)(void *)  item_destroy )

Destroy priority queue - queue to destroy - item destructor Definition at line 201 of file gw-prioqueue.c. References gw_prioqueue_t, element::item, item_destroy(), gw_prioqueue::len, gw_prioqueue::mutex, mutex_destroy(), gw_prioqueue::nonempty, and gw_prioqueue::tab. Referenced by at2_device_thread(), emi2_sender(), smsc_at2_create(), and smsc_emi2_create(). { long i; if (queue == NULL) return; for (i = 0; i < queue->len; i++) { if (item_destroy != NULL && queue->tab[i]->item != NULL) item_destroy(queue->tab[i]->item); gw_free(queue->tab[i]); } mutex_destroy(queue->mutex); pthread_cond_destroy(&queue->nonempty); gw_free(queue->tab); gw_free(queue); }

Here is the call graph for this function:

void gw_prioqueue_foreach (  gw_prioqueue_t *  queue, void(*)(const void *, long)  fn )

Definition at line 252 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, element::item, gw_prioqueue::len, queue_lock(), queue_unlock(), and gw_prioqueue::tab. Referenced by main(). { register long i; gw_assert(queue != NULL && fn != NULL); queue_lock(queue); for (i = 1; i < queue->len; i++) fn(queue->tab[i]->item, i - 1); queue_unlock(queue); }

Here is the call graph for this function:

void* gw_prioqueue_get (  gw_prioqueue_t *  queue  )

Definition at line 286 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, element::item, gw_prioqueue::len, queue_lock(), queue_unlock(), and gw_prioqueue::tab. { void *ret; gw_assert(queue != NULL); queue_lock(queue); if (queue->len > 1) ret = queue->tab[1]->item; else ret = NULL; queue_unlock(queue); return ret; }

Here is the call graph for this function:

void gw_prioqueue_insert (  gw_prioqueue_t *  queue, void *  item )

Insert item into the priority queue - priority queue - to be inserted item Definition at line 235 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, element::item, gw_prioqueue::len, make_bigger(), gw_prioqueue::nonempty, queue_lock(), queue_unlock(), element::seq, gw_prioqueue::seq, gw_prioqueue::tab, and upheap(). Referenced by main(). { gw_assert(queue != NULL); gw_assert(item != NULL); queue_lock(queue); make_bigger(queue, 1); queue->tab[queue->len] = gw_malloc(sizeof(**queue->tab)); queue->tab[queue->len]->item = item; queue->tab[queue->len]->seq = queue->seq++; upheap(queue, queue->len); queue->len++; pthread_cond_signal(&queue->nonempty); queue_unlock(queue); }

Here is the call graph for this function:

long gw_prioqueue_len (  gw_prioqueue_t *  queue  )

Return priority queue length - priority queue Returns: length of this priority queue Definition at line 220 of file gw-prioqueue.c. References gw_prioqueue_t, gw_prioqueue::len, queue_lock(), and queue_unlock(). Referenced by at2_device_thread(), at2_queued_cb(), at2_send_messages(), emi2_wait(), main(), and queued_cb(). { long len; if (queue == NULL) return 0; queue_lock(queue); len = queue->len - 1; queue_unlock(queue); return len; }

Here is the call graph for this function:

long gw_prioqueue_producer_count (  gw_prioqueue_t *  queue  )

Return producer count for the priority queue - priority queue Returns: producer count Definition at line 351 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, gw_prioqueue::producers, queue_lock(), and queue_unlock(). { long ret; gw_assert(queue != NULL); queue_lock(queue); ret = queue->producers; queue_unlock(queue); return ret; }

Here is the call graph for this function:

void* gw_prioqueue_remove (  gw_prioqueue_t *  queue  )

Remove biggest item from the priority queue, but not block if producers available and none items in the queue - priority queue Returns: - biggest item or NULL if none items in the queue Definition at line 265 of file gw-prioqueue.c. References downheap(), gw_assert, gw_prioqueue_t, element::item, gw_prioqueue::len, queue_lock(), queue_unlock(), and gw_prioqueue::tab. Referenced by at2_send_messages(), at2_shutdown_cb(), emi2_do_send(), emi2_sender(), main(), open_send_connection(), and shutdown_cb(). { void *ret; gw_assert(queue != NULL); queue_lock(queue); if (queue->len <= 1) { queue_unlock(queue); return NULL; } ret = queue->tab[1]->item; gw_free(queue->tab[1]); queue->tab[1] = queue->tab[--queue->len]; downheap(queue, 1); queue_unlock(queue); return ret; }

Here is the call graph for this function:

void gw_prioqueue_remove_producer (  gw_prioqueue_t *  queue  )

Remove producer from the priority queue - priority queue Definition at line 339 of file gw-prioqueue.c. References gw_assert, gw_prioqueue_t, gw_prioqueue::nonempty, gw_prioqueue::producers, queue_lock(), and queue_unlock(). { gw_assert(queue != NULL); queue_lock(queue); gw_assert(queue->producers > 0); queue->producers--; pthread_cond_broadcast(&queue->nonempty); queue_unlock(queue); }

Here is the call graph for this function:

void make_bigger (  gw_prioqueue_t *  queue, long  items )  [static]

Definition at line 103 of file gw-prioqueue.c. References gw_prioqueue_t, gw_prioqueue::len, gw_prioqueue::size, size, and gw_prioqueue::tab. { size_t size = queue->size; size_t new_size = sizeof(*queue->tab) * (queue->len + items); if (size >= new_size) return; queue->tab = gw_realloc(queue->tab, new_size); queue->size = new_size; }

void queue_lock (  gw_prioqueue_t *  queue  )  [inline, static]

Definition at line 91 of file gw-prioqueue.c. References gw_prioqueue_t, gw_prioqueue::mutex, and mutex_lock. Referenced by gw_prioqueue_add_producer(), gw_prioqueue_consume(), gw_prioqueue_foreach(), gw_prioqueue_get(), gw_prioqueue_insert(), gw_prioqueue_len(), gw_prioqueue_producer_count(), gw_prioqueue_remove(), and gw_prioqueue_remove_producer(). { mutex_lock(queue->mutex); }

void queue_unlock (  gw_prioqueue_t *  queue  )  [inline, static]

Definition at line 97 of file gw-prioqueue.c. References gw_prioqueue_t, gw_prioqueue::mutex, and mutex_unlock. Referenced by gw_prioqueue_add_producer(), gw_prioqueue_consume(), gw_prioqueue_foreach(), gw_prioqueue_get(), gw_prioqueue_insert(), gw_prioqueue_len(), gw_prioqueue_producer_count(), gw_prioqueue_remove(), and gw_prioqueue_remove_producer(). { mutex_unlock(queue->mutex); }

void upheap (  gw_prioqueue_t *  queue, register long  index )  [static]

Heapize up - our prioqueue + - start index Definition at line 138 of file gw-prioqueue.c. References gw_prioqueue::cmp, compare(), gw_prioqueue_t, element::item, and gw_prioqueue::tab. Referenced by gw_prioqueue_insert(). { struct element *v = queue->tab[index]; while (queue->tab[index / 2]->item != NULL && compare(queue->tab[index / 2], v, queue->cmp) < 0) { queue->tab[index] = queue->tab[index / 2]; index /= 2; } queue->tab[index] = v; }

Here is the call graph for this function:

See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.