1 /* 2 ** Copyright (C) 2004-2020 by Carnegie Mellon University. 3 ** 4 ** @OPENSOURCE_LICENSE_START@ 5 ** See license information in ../../LICENSE.txt 6 ** @OPENSOURCE_LICENSE_END@ 7 */ 8 9 /* 10 ** skdeque.h 11 ** 12 ** Methods for working with thread-safe double-ended queues 13 ** 14 */ 15 #ifndef _SKDEQUE_H 16 #define _SKDEQUE_H 17 #ifdef __cplusplus 18 extern "C" { 19 #endif 20 21 #include <silk/silk.h> 22 23 RCSIDENTVAR(rcsID_SKDEQUE_H, "$SiLK: skdeque.h ef14e54179be 2020-04-14 21:57:45Z mthomas $"); 24 25 /** 26 * @file 27 * 28 * Implementation of a thread-safe, double-ended queue. 29 * 30 * This file is part of libsilk-thrd. 31 * 32 * 33 * A deque maintains a list of void pointers. It does not know the 34 * contents of these pointers, and as such the deque knows nothing 35 * about the memory management behind them. A deque never attemps to 36 * copy or free anything behind the pointer. It is the caller's 37 * responsibility to ensure that an object in a deque is not 38 * free()'ed until the object has been popped from the deque. 39 * 40 * 41 * Within this header file, the item most-recently pushed is 42 * considered to be "last", and "behind" all the other items, and the 43 * item which would be returned by a pop is considered to be "first", 44 * and "in front of" all the other items. 45 */ 46 47 /** 48 * The type of deques. 49 * 50 * Unlike most SiLK types, the pointer is part of the typedef. 51 */ 52 typedef struct sk_deque_st *skDeque_t; 53 54 55 /** 56 * Return values from skSkdeque functions. 57 */ 58 typedef enum { 59 /** success */ 60 SKDQ_SUCCESS = 0, 61 /** deque is empty */ 62 SKDQ_EMPTY = -1, 63 /** unspecified error */ 64 SKDQ_ERROR = -2, 65 /** deque was destroyed */ 66 SKDQ_DESTROYED = -3, 67 /** deque was unblocked */ 68 SKDQ_UNBLOCKED = -4, 69 /** deque pop timed out */ 70 SKDQ_TIMEDOUT = -5 71 } skDQErr_t; 72 73 /*** Deque creation functions ***/ 74 75 /* 76 * For all creation functions, a NULL return value indicates an error 77 * condition. 78 */ 79 80 /** 81 * Create a deque. Return NULL on memory alloation error. 82 */ 83 skDeque_t 84 skDequeCreate( 85 void); 86 87 88 /** 89 * Creates a copy of a deque. Operations on both deques will 90 * affect each other. Return NULL on error. 91 */ 92 skDeque_t 93 skDequeCopy( 94 skDeque_t deque); 95 96 /** 97 * Creates a new pseudo-deque which acts like a deque with all the 98 * elements of q1 in front of q2. q1 and q2 continue behaving 99 * normally. Return NULL on error. 100 */ 101 skDeque_t 102 skDequeCreateMerged( 103 skDeque_t q1, 104 skDeque_t q2); 105 106 107 /*** Deque destruction ***/ 108 109 /** 110 * Destroy and free a deque. (Not reponsible for freeing the 111 * elements within the deque). Returns SKDQ_ERROR if 'deque' is 112 * NULL. 113 */ 114 skDQErr_t 115 skDequeDestroy( 116 skDeque_t deque); 117 118 119 /*** Deque data manipulation functions ***/ 120 121 /** 122 * Return the status of a deque. 123 */ 124 skDQErr_t 125 skDequeStatus( 126 skDeque_t deque); 127 128 /** 129 * Returns the size of a deque. Undefined on a bad (destroyed or 130 * error-ridden) deque. 131 */ 132 uint32_t 133 skDequeSize( 134 skDeque_t deque); 135 136 /** 137 * Pop an element from the front of 'deque'. The call will block 138 * until an item is available in 'deque'. It is the responsibility 139 * of the program using the deque to free any elements popped from 140 * it. 141 */ 142 skDQErr_t 143 skDequePopFront( 144 skDeque_t deque, 145 void **item); 146 147 /** 148 * Like skDequePopFront(), but does not block and returns 149 * SKDQ_EMPTY if 'deque' is currently empty. 150 */ 151 skDQErr_t 152 skDequePopFrontNB( 153 skDeque_t deque, 154 void **item); 155 156 /** 157 * Like skDequePopFront() except, when 'deque' is empty, waits 158 * 'seconds' seconds for an item to appear in 'deque'. If 'deque' 159 * is still empty after 'seconds' seconds, returns SKDQ_EMPTY. 160 */ 161 skDQErr_t 162 skDequePopFrontTimed( 163 skDeque_t deque, 164 void **item, 165 uint32_t seconds); 166 167 /** 168 * Like skDequePopFront(), but returns the last element of 'deque'. 169 */ 170 skDQErr_t 171 skDequePopBack( 172 skDeque_t deque, 173 void **item); 174 175 /** 176 * Like skDequePopFrontNB(), but returns the last element of 177 * 'deque'. 178 */ 179 skDQErr_t 180 skDequePopBackNB( 181 skDeque_t deque, 182 void **item); 183 184 /** 185 * Like skDequePopFrontTimed(), but returns the last element of 186 * 'deque'. 187 */ 188 skDQErr_t 189 skDequePopBackTimed( 190 skDeque_t deque, 191 void **item, 192 uint32_t seconds); 193 194 /** 195 * Unblock threads blocked on dequeue pops (each of which will 196 * return SKDQ_UNBLOCKED). They will remain unblocked, ignoring 197 * blocking pushes, until re-blocked. 198 */ 199 skDQErr_t 200 skDequeUnblock( 201 skDeque_t deque); 202 203 /** 204 * Reblock a deque unblocked by skDequeUnblock. Deques are created 205 * in a blockable state. 206 */ 207 skDQErr_t 208 skDequeBlock( 209 skDeque_t deque); 210 211 /** 212 * Return the first element of 'deque' without removing it, or 213 * SKDQ_EMPTY if the deque is empty. This function does not remove 214 * items from the deque. Do not free() an item until it has been 215 * popped. 216 */ 217 skDQErr_t 218 skDequeFront( 219 skDeque_t deque, 220 void **item); 221 222 /** 223 * Like skDequeFront(), but returns the last element of 'deque'. 224 */ 225 skDQErr_t 226 skDequeBack( 227 skDeque_t deque, 228 void **item); 229 230 /** 231 * Push 'item' onto the front of 'deque'. Deques maintain the item 232 * pointer only. In order for the item to be of any use when it is 233 * later popped, it must survive its stay in the queue (not be 234 * freed). 235 */ 236 skDQErr_t 237 skDequePushFront( 238 skDeque_t deque, 239 void *item); 240 241 /** 242 * Like skDequePushFront(), but pushes 'item' onto the end of 'deque'. 243 */ 244 skDQErr_t 245 skDequePushBack( 246 skDeque_t deque, 247 void *item); 248 249 #ifdef __cplusplus 250 } 251 #endif 252 #endif /* _SKDEQUE_H */ 253 254 /* 255 ** Local Variables: 256 ** mode:c 257 ** indent-tabs-mode:nil 258 ** c-basic-offset:4 259 ** End: 260 */ 261