00001 #ifndef LIBNAGIOS_squeue_h__ 00002 #define LIBNAGIOS_squeue_h__ 00003 #include <sys/time.h> 00004 #include <time.h> 00005 #include "pqueue.h" 00006 /** 00007 * @file squeue.h 00008 * @brief Scheduling queue function declarations 00009 * 00010 * This library is based on the pqueue api, which implements a 00011 * priority queue based on a binary heap, providing O(lg n) times 00012 * for insert() and remove(), and O(1) time for peek(). 00013 * @note There is no "find". Callers must maintain pointers to their 00014 * scheduled events if they wish to be able to remove them. 00015 * 00016 * @{ 00017 */ 00018 00019 /* 00020 * All opaque types here. 00021 * The pqueue library can be useful on its own though, so we 00022 * don't block that from user view. 00023 */ 00024 typedef pqueue_t squeue_t; 00025 struct squeue_event; 00026 typedef struct squeue_event squeue_event; 00027 00028 /** 00029 * Options for squeue_destroy()'s flag parameter 00030 */ 00031 #define SQUEUE_FREE_DATA (1 << 0) /** Call free() on all data pointers */ 00032 00033 /** 00034 * Get the scheduled runtime of this event 00035 * @param[in] evt The event to get runtime of 00036 * @return struct timeval on success, NULL on errors 00037 */ 00038 extern const struct timeval *squeue_event_runtime(squeue_event *evt); 00039 00040 /** 00041 * Get data of an squeue_event struct 00042 * @param[in] evt The event to operate on 00043 * @return The data object pointed to by the event 00044 */ 00045 extern void *squeue_event_data(squeue_event *evt); 00046 00047 /** 00048 * Creates a scheduling queue optimized for handling events within 00049 * the given timeframe. Callers should take care to create a queue 00050 * of a decent but not overly large size, as too small or too large 00051 * a queue will impact performance negatively. A queue can hold any 00052 * number of events. A good value for "horizon" would be the max 00053 * seconds into the future one expects to schedule things, although 00054 * with few scheduled items in that timeframe you'd be better off 00055 * using a more narrow horizon. 00056 * 00057 * @param size Hint about how large this queue will get 00058 * @return A pointer to a scheduling queue 00059 */ 00060 extern squeue_t *squeue_create(unsigned int size); 00061 00062 /** 00063 * Destroys a scheduling queue completely 00064 * @param[in] q The doomed queue 00065 * @param[in] flags Flags determining the the level of destruction 00066 */ 00067 extern void squeue_destroy(squeue_t *q, int flags); 00068 00069 /** 00070 * Enqueue an event with microsecond precision. 00071 * It's up to the caller to keep the event pointer in case he/she 00072 * wants to remove the event from the queue later. 00073 * 00074 * @param q The scheduling queue to add to 00075 * @param tv When this event should occur 00076 * @param data Pointer to any kind of data 00077 * @return The complete scheduled event 00078 */ 00079 extern squeue_event *squeue_add_tv(squeue_t *q, struct timeval *tv, void *data); 00080 00081 /** 00082 * Adds an event to the scheduling queue. 00083 * See notes for squeue_add_tv() for details 00084 * 00085 * @param q The scheduling queue to add to 00086 * @param when The unix timestamp when this event is to occur 00087 * @param data Pointer to any kind of data 00088 * @return The complete scheduled event 00089 */ 00090 extern squeue_event *squeue_add(squeue_t *q, time_t when, void *data); 00091 00092 /** 00093 * Adds an event to the scheduling queue with millisecond precision 00094 * See notes on squeue_add_tv() for details 00095 * 00096 * @param[in] q The scheduling queue to add to 00097 * @param[in] when Unix timestamp when this event should occur 00098 * @param[in] usec Millisecond of above this event should occur 00099 * @param[in] data Pointer to any kind of data 00100 * @return NULL on errors. squeue_event pointer on success 00101 */ 00102 extern squeue_event *squeue_add_usec(squeue_t *q, time_t when, time_t usec, void *data); 00103 00104 /** 00105 * Adds an event to the scheduling queue with millisecond precision 00106 * See notes on squeue_add_tv() for details 00107 * 00108 * @param[in] q The scheduling queue to add to 00109 * @param[in] when Unix timestamp when this event should occur 00110 * @param[in] msec Millisecond of above this event should occur 00111 * @param[in] data Pointer to any kind of data 00112 * @return NULL on errors. squeue_event pointer on success 00113 */ 00114 extern squeue_event *squeue_add_msec(squeue_t *q, time_t when, time_t msec, void *data); 00115 00116 /** 00117 * Returns the data of the next scheduled event from the scheduling 00118 * queue without removing it from the queue. 00119 * 00120 * @param q The scheduling queue to peek into 00121 */ 00122 extern void *squeue_peek(squeue_t *q); 00123 00124 /** 00125 * Pops the next scheduled event from the scheduling queue and 00126 * returns the data for it. 00127 * This is equivalent to squeue_peek() + squeue_pop() 00128 * @note This causes the squeue_event to be free()'d. 00129 * 00130 * @param q The scheduling queue to pop from 00131 */ 00132 extern void *squeue_pop(squeue_t *q); 00133 00134 /** 00135 * Removes the given event from the scheduling queue 00136 * @note This causes the associated squeue_event() to be free()'d. 00137 * @param[in] q The scheduling queue to remove from 00138 * @param[in] evt The event to remove 00139 */ 00140 extern int squeue_remove(squeue_t *q, squeue_event *evt); 00141 00142 /** 00143 * Returns the number of events in the scheduling queue. This 00144 * function never fails. 00145 * 00146 * @param[in] q The scheduling queue to inspect 00147 * @return number of events in the inspected queue 00148 */ 00149 extern unsigned int squeue_size(squeue_t *q); 00150 00151 00152 /** 00153 * Returns true if passed timeval is after the time for the event 00154 * 00155 * @param[in] evt The queue event to inspect 00156 * @param[in] reftime The reference time to compare to the queue event time 00157 * @return 1 if reftime > event time, 0 otherwise 00158 */ 00159 extern int squeue_evt_when_is_after(squeue_event *evt, struct timeval *reftime); 00160 #endif 00161 /** @} */