1 /* Pushdown stacks for integers, pointers, and characters.
2 *
3 * Contents:
4 * 1. The <ESL_STACK> object.
5 * 2. The main API, including pushing/popping.
6 * 3. Shuffling stacks.
7 * 4. Using stacks for thread communication [HAVE_PTHREAD]
8 * 5. Unit tests.
9 * 6. Test driver.
10 * 7. Example.
11 */
12 #include "esl_config.h"
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #ifdef HAVE_PTHREAD
18 #include <pthread.h>
19 #endif
20 #ifdef HAVE_UNISTD_H
21 #include <unistd.h> /* usleep() in unit tests */
22 #endif
23
24 #include "easel.h"
25 #include "esl_random.h"
26
27 #include "esl_stack.h"
28
29
30 /*****************************************************************
31 *# 1. The <ESL_STACK> object.
32 *****************************************************************/
33
34 /* Function: esl_stack_ICreate()
35 * Synopsis: Create an integer stack.
36 * Incept: SRE, Sun Dec 26 09:11:50 2004 [Zaragoza]
37 *
38 * Purpose: Creates an integer stack.
39 *
40 * Returns: a pointer to the new stack.
41 *
42 * Throws: <NULL> on an allocation failure.
43 */
44 ESL_STACK *
esl_stack_ICreate(void)45 esl_stack_ICreate(void)
46 {
47 ESL_STACK *ns = NULL;
48 int status;
49
50 ESL_ALLOC(ns, sizeof(ESL_STACK));
51 ns->nalloc = ESL_STACK_INITALLOC;
52 ns->pdata = NULL;
53 ns->cdata = NULL;
54 ns->idata = NULL;
55 ns->n = 0;
56 #ifdef HAVE_PTHREAD
57 ns->do_mutex = FALSE;
58 ns->do_cond = FALSE;
59 ns->mutex = NULL;
60 ns->cond = NULL;
61 #endif
62
63 ESL_ALLOC(ns->idata, sizeof(int) * ns->nalloc);
64 return ns;
65
66 ERROR:
67 esl_stack_Destroy(ns);
68 return NULL;
69 }
70
71 /* Function: esl_stack_CCreate()
72 * Synopsis: Create a character stack.
73 * Incept: SRE, Sun Dec 26 09:15:35 2004 [Zaragoza]
74 *
75 * Purpose: Creates a character stack.
76 *
77 * Returns: a pointer to the new stack.
78 *
79 * Throws: <NULL> on an allocation failure.
80 */
81 ESL_STACK *
esl_stack_CCreate(void)82 esl_stack_CCreate(void)
83 {
84 ESL_STACK *cs = NULL;
85 int status;
86
87 ESL_ALLOC(cs, sizeof(ESL_STACK));
88 cs->nalloc = ESL_STACK_INITALLOC;
89 cs->idata = NULL;
90 cs->pdata = NULL;
91 cs->cdata = NULL;
92 cs->n = 0;
93 #ifdef HAVE_PTHREAD
94 cs->do_mutex = FALSE;
95 cs->do_cond = FALSE;
96 cs->mutex = NULL;
97 cs->cond = NULL;
98 #endif
99
100 ESL_ALLOC(cs->cdata, sizeof(char) * cs->nalloc);
101 return cs;
102
103 ERROR:
104 esl_stack_Destroy(cs);
105 return NULL;
106 }
107
108 /* Function: esl_stack_PCreate()
109 * Synopsis: Create a pointer stack.
110 * Incept: SRE, Sun Dec 26 09:16:07 2004 [Zaragoza]
111 *
112 * Purpose: Creates a pointer stack.
113 *
114 * Returns: a pointer to the new stack.
115 *
116 * Throws: <NULL> on an allocation failure.
117 */
118 ESL_STACK *
esl_stack_PCreate(void)119 esl_stack_PCreate(void)
120 {
121 ESL_STACK *ps = NULL;
122 int status;
123
124 ESL_ALLOC(ps, sizeof(ESL_STACK));
125 ps->nalloc = ESL_STACK_INITALLOC;
126 ps->idata = NULL;
127 ps->cdata = NULL;
128 ps->pdata = NULL;
129 ps->n = 0;
130 #ifdef HAVE_PTHREAD
131 ps->do_mutex = FALSE;
132 ps->do_cond = FALSE;
133 ps->mutex = NULL;
134 ps->cond = NULL;
135 #endif
136
137 ESL_ALLOC(ps->pdata, sizeof(void *) * ps->nalloc);
138 return ps;
139
140 ERROR:
141 esl_stack_Destroy(ps);
142 return NULL;
143 }
144
145 /* Function: esl_stack_Reuse()
146 * Synopsis: Reuse a stack.
147 * Incept: SRE, Tue Dec 28 04:21:36 2004 [Zaragoza]
148 *
149 * Purpose: Empties stack <s> so it can be reused without
150 * creating a new one. The stack <s>
151 * can be of any data type; it retains its original
152 * type.
153 *
154 * Returns: <eslOK>
155 */
156 int
esl_stack_Reuse(ESL_STACK * s)157 esl_stack_Reuse(ESL_STACK *s)
158 {
159 s->n = 0; /* it's that simple in this implementation */
160 return eslOK;
161 }
162
163 /* Function: esl_stack_Destroy()
164 * Synopsis: Free a stack.
165 * Incept: SRE, Sun Dec 26 09:16:24 2004 [Zaragoza]
166 *
167 * Purpose: Destroys a created stack <s>, of any data type.
168 */
169 void
esl_stack_Destroy(ESL_STACK * s)170 esl_stack_Destroy(ESL_STACK *s)
171 {
172 if (s)
173 {
174 if (s->idata) free(s->idata);
175 if (s->cdata) free(s->cdata);
176 if (s->pdata) free(s->pdata);
177 #ifdef HAVE_PTHREAD
178 if (s->mutex) { pthread_mutex_destroy(s->mutex); free(s->mutex); }
179 if (s->cond) { pthread_cond_destroy(s->cond); free(s->cond); }
180 #endif
181 free(s);
182 }
183 }
184 /*------------------ end, ESL_STACK object ----------------------*/
185
186
187
188 /*****************************************************************
189 *# 2. The main API, including pushing/popping.
190 *****************************************************************/
191
192 /* Function: esl_stack_IPush()
193 * Synopsis: Push an integer onto a stack.
194 * Incept: SRE, Sun Dec 26 09:17:17 2004 [Zaragoza]
195 *
196 * Purpose: Push an integer <x> onto an integer stack <ns>.
197 *
198 * Returns: <eslOK> on success.
199 *
200 * Throws: <eslEMEM> on reallocation failure.
201 * <eslESYS> if a pthread call fails. In this case, the
202 * state of a pthread mutex and/or cond may be wedged.
203 */
204 int
esl_stack_IPush(ESL_STACK * ns,int x)205 esl_stack_IPush(ESL_STACK *ns, int x)
206 {
207 int *ptr = NULL;
208 int status;
209
210 #ifdef HAVE_PTHREAD
211 if (ns->do_mutex) if (pthread_mutex_lock(ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
212 #endif
213
214 if (ns->n == ns->nalloc) {
215 ESL_RALLOC(ns->idata, ptr, sizeof(int) * ns->nalloc * 2);
216 ns->nalloc += ns->nalloc; /* reallocate by doubling */
217 }
218 ns->idata[ns->n] = x;
219 ns->n++;
220
221 #ifdef HAVE_PTHREAD
222 if (ns->do_cond) if (pthread_cond_signal(ns->cond) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_signal() failure");
223 if (ns->do_mutex) if (pthread_mutex_unlock(ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
224 #endif
225 return eslOK;
226
227 ERROR:
228 #ifdef HAVE_PTHREAD
229 if (ns->do_mutex) if (pthread_mutex_unlock(ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
230 #endif
231 return status;
232 }
233
234 /* Function: esl_stack_CPush()
235 * Synopsis: Push a char onto a stack.
236 * Incept: SRE, Sun Dec 26 09:18:24 2004 [Zaragoza]
237 *
238 * Purpose: Push a character <c> onto a character stack <cs>.
239 *
240 * Returns: <eslOK> on success.
241 *
242 * Throws: <eslEMEM> on reallocation failure.
243 * <eslESYS> if a pthread call fails. In this case, the
244 * state of a pthread mutex and/or cond may be wedged.
245 */
246 int
esl_stack_CPush(ESL_STACK * cs,char c)247 esl_stack_CPush(ESL_STACK *cs, char c)
248 {
249 char *ptr = NULL;
250 int status;
251
252 #ifdef HAVE_PTHREAD
253 if (cs->do_mutex) if (pthread_mutex_lock(cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
254 #endif
255
256 if (cs->n == cs->nalloc) {
257 ESL_RALLOC(cs->cdata, ptr, sizeof(char) * cs->nalloc * 2);
258 cs->nalloc += cs->nalloc; /* reallocate by doubling */
259 }
260 cs->cdata[cs->n] = c;
261 cs->n++;
262
263 #ifdef HAVE_PTHREAD
264 if (cs->do_cond) if (pthread_cond_signal(cs->cond) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_signal() failure");
265 if (cs->do_mutex) if (pthread_mutex_unlock(cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
266 #endif
267 return eslOK;
268
269 ERROR:
270 #ifdef HAVE_PTHREAD
271 if (cs->do_mutex) if (pthread_mutex_unlock(cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
272 #endif
273 return status;
274 }
275
276 /* Function: esl_stack_PPush()
277 * Synopsis: Push a pointer onto a stack.
278 * Incept: SRE, Sun Dec 26 09:18:49 2004 [Zaragoza]
279 *
280 * Purpose: Push a pointer <p> onto a pointer stack <ps>.
281 *
282 * Returns: <eslOK> on success.
283 *
284 * Throws: <eslEMEM> on reallocation failure.
285 * <eslESYS> if a pthread call fails. In this case, the
286 * state of a pthread mutex and/or cond may be wedged.
287 */
288 int
esl_stack_PPush(ESL_STACK * ps,void * p)289 esl_stack_PPush(ESL_STACK *ps, void *p)
290 {
291 void *ptr = NULL;
292 int status;
293
294 #ifdef HAVE_PTHREAD
295 if (ps->do_mutex) if (pthread_mutex_lock(ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
296 #endif
297
298 if (ps->n == ps->nalloc) {
299 ESL_RALLOC(ps->pdata, ptr, sizeof(void *) * ps->nalloc * 2);
300 ps->nalloc += ps->nalloc; /* reallocate by doubling */
301 }
302 ps->pdata[ps->n] = p;
303 ps->n++;
304
305 #ifdef HAVE_PTHREAD
306 if (ps->do_cond) if (pthread_cond_signal(ps->cond) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_signal() failure");
307 if (ps->do_mutex) if (pthread_mutex_unlock(ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
308 #endif
309 return eslOK;
310
311 ERROR:
312 #ifdef HAVE_PTHREAD
313 if (ps->do_mutex) if (pthread_mutex_unlock(ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
314 #endif
315 return status;
316 }
317
318 /* Function: esl_stack_IPop()
319 * Synopsis: Pop an integer off a stack.
320 * Incept: SRE, Sun Dec 26 09:19:12 2004 [Zaragoza]
321 *
322 * Purpose: Pops an integer off the integer stack <ns>, and returns
323 * it through <ret_x>.
324 *
325 * Returns: <eslOK> on success.
326 * <eslEOD> if stack is empty.
327 *
328 * Throws: <eslESYS> if a pthread mutex lock/unlock or conditional wait fails.
329 */
330 int
esl_stack_IPop(ESL_STACK * ns,int * ret_x)331 esl_stack_IPop(ESL_STACK *ns, int *ret_x)
332 {
333 int status;
334 #ifdef HAVE_PTHREAD
335 if (ns->do_mutex && pthread_mutex_lock(ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
336 if (ns->do_cond && ! ns->n && pthread_cond_wait(ns->cond, ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_wait() failure");
337 #endif
338
339 if (ns->n == 0)
340 {
341 *ret_x = 0;
342 status = eslEOD;
343 }
344 else
345 {
346 ns->n--;
347 *ret_x = ns->idata[ns->n];
348 status = eslOK;
349 }
350
351 #ifdef HAVE_PTHREAD
352 if (ns->do_mutex && pthread_mutex_unlock(ns->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
353 #endif
354 return status;
355 }
356
357 /* Function: esl_stack_CPop()
358 * Synopsis: Pop a char off a stack.
359 * Incept: SRE, Sun Dec 26 09:21:27 2004 [Zaragoza]
360 *
361 * Purpose: Pops a character off the character stack <cs>, and returns
362 * it through <ret_c>.
363 *
364 * Returns: <eslOK> on success.
365 * <eslEOD> if stack is empty.
366 *
367 * Throws: <eslESYS> if a pthread mutex lock/unlock or conditional wait fails.
368 */
369 int
esl_stack_CPop(ESL_STACK * cs,char * ret_c)370 esl_stack_CPop(ESL_STACK *cs, char *ret_c)
371 {
372 int status;
373 #ifdef HAVE_PTHREAD
374 if (cs->do_mutex && pthread_mutex_lock(cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
375 if (cs->do_cond && ! cs->n && pthread_cond_wait(cs->cond, cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_wait() failure");
376 #endif
377
378 if (cs->n == 0)
379 {
380 *ret_c = 0;
381 status = eslEOD;
382 }
383 else
384 {
385 cs->n--;
386 *ret_c = cs->cdata[cs->n];
387 status = eslOK;
388 }
389
390 #ifdef HAVE_PTHREAD
391 if (cs->do_mutex && pthread_mutex_unlock(cs->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
392 #endif
393 return status;
394 }
395
396 /* Function: esl_stack_PPop()
397 * Synopsis: Pop a pointer off a stack.
398 * Incept: SRE, Sun Dec 26 09:21:56 2004 [Zaragoza]
399 *
400 * Purpose: Pops a pointer off the pointer stack <ps>, and returns
401 * it through <ret_p>.
402 *
403 * Returns: <eslOK> on success.
404 * <eslEOD> if stack is empty.
405 *
406 * Throws: <eslESYS> if a pthread mutex lock/unlock or conditional wait fails.
407 */
408 int
esl_stack_PPop(ESL_STACK * ps,void ** ret_p)409 esl_stack_PPop(ESL_STACK *ps, void **ret_p)
410 {
411 int status;
412 #ifdef HAVE_PTHREAD
413 if (ps->do_mutex && pthread_mutex_lock(ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
414 if (ps->do_cond && ! ps->n && pthread_cond_wait(ps->cond, ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_wait() failure");
415 #endif
416
417 if (ps->n == 0)
418 {
419 *ret_p = NULL;
420 status = eslEOD;
421 }
422 else
423 {
424 ps->n--;
425 *ret_p = ps->pdata[ps->n];
426 status = eslOK;
427 }
428
429 #ifdef HAVE_PTHREAD
430 if (ps->do_mutex && pthread_mutex_unlock(ps->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
431 #endif
432 return status;
433 }
434
435 /* Function: esl_stack_ObjectCount()
436 * Synopsis: Return the number of objects in a stack.
437 * Incept: SRE, Sun Dec 26 09:22:41 2004 [Zaragoza]
438 *
439 * Purpose: Returns the number of data objects stored in the
440 * stack <s>. The stack may be of any datatype.
441 */
442 int
esl_stack_ObjectCount(ESL_STACK * s)443 esl_stack_ObjectCount(ESL_STACK *s)
444 {
445 return s->n;
446 }
447
448 /* Function: esl_stack_Convert2String()
449 * Synopsis: Convert a char stack to a string.
450 * Incept: SRE, Sun Dec 26 09:23:36 2004 [Zaragoza]
451 *
452 * Purpose: Converts a character stack <cs> to a NUL-terminated
453 * string, and returns a pointer to the string. The
454 * characters in the string are in the same order they
455 * were pushed onto the stack. The stack is destroyed by
456 * this operation, as if <esl_stack_Destroy()> had been
457 * called on it. The caller becomes responsible for
458 * free'ing the returned string.
459 *
460 * Because the stack is destroyed by this call, use care in
461 * a multithreaded context. You don't want to have another
462 * thread waiting to do something to this stack as another
463 * thread is destroying it. Treat this call like
464 * you'd treat <esl_stack_Destroy()>. Its internals are
465 * not mutex-protected (unlike push/pop functions).
466 *
467 * Returns: Pointer to the string; caller must <free()> this.
468 *
469 * Throws: NULL if a reallocation fails.
470 */
471 char *
esl_stack_Convert2String(ESL_STACK * cs)472 esl_stack_Convert2String(ESL_STACK *cs)
473 {
474 char *s = NULL;
475 void *tmp = NULL;
476 int status;
477
478 /* Take stack away; it's already a string, just not nul-terminated */
479 s = cs->cdata;
480 cs->cdata = NULL; /* esl_stack_Destroy() will now ignore the NULL cdata field */
481
482 /* NUL-terminate; which might require a +1 realloc if we're unlucky */
483 if (cs->n == cs->nalloc)
484 ESL_RALLOC(s, tmp, sizeof(char) * (cs->nalloc +1));
485 s[cs->n] = '\0';
486
487 /* Destroy the stack; return the string. */
488 esl_stack_Destroy(cs);
489 return s;
490
491 ERROR:
492 esl_stack_Destroy(cs);
493 return NULL;
494 }
495
496 /* Function: esl_stack_DiscardTopN()
497 * Synopsis: Discard the top elements on a stack.
498 * Incept: SRE, Tue Dec 28 04:33:06 2004 [St. Louis]
499 *
500 * Purpose: Throw away the top <n> elements on stack <s>.
501 * Equivalent to <n> calls to a <Pop()> function.
502 * If <n> equals or exceeds the number of elements
503 * currently in the stack, the stack is emptied
504 * as if <esl_stack_Reuse()> had been called.
505 *
506 * Returns: <eslOK> on success.
507 *
508 * Throws: <eslESYS> if mutex lock/unlock fails, if pthreaded.
509 */
510 int
esl_stack_DiscardTopN(ESL_STACK * s,int n)511 esl_stack_DiscardTopN(ESL_STACK *s, int n)
512 {
513 #ifdef HAVE_PTHREAD
514 if (s->do_mutex && pthread_mutex_lock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
515 #endif
516
517 if (n <= s->n) s->n -= n;
518 else s->n = 0;
519
520 #ifdef HAVE_PTHREAD
521 if (s->do_mutex && pthread_mutex_unlock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
522 #endif
523 return eslOK;
524 }
525
526 /* Function: esl_stack_DiscardSelected()
527 * Synopsis: Remove arbitrary elements from a stack.
528 * Incept: SRE, Tue Jan 18 09:57:47 2011 [Janelia]
529 *
530 * Purpose: For each element in the stack, call \verb+(*discard_func)(&element, param)+.
531 * If <TRUE>, discard the element.
532 *
533 * Passing a pointer to an arbitrary <(*discard_func)>
534 * allows arbitrary rules. The <(*discard_func)> gets two
535 * arguments: a pointer (which is either a pointer to an
536 * element for int and char stacks, or an actual pointer
537 * element from a pointer stack), and <param>, a <void *>
538 * to whatever arguments the caller needs the selection
539 * function to have.
540 *
541 * When discarding elements from a pointer stack, the
542 * <*discard_func()> will generally assume responsibility
543 * for the memory allocated to those elements. It may want
544 * to free() or Destroy() them, for example, if they're
545 * truly being discarded.
546 *
547 * Args: s - stack to discard from
548 * discard_func - ptr to function that returns TRUE if elem is to be discarded
549 * param - ptr to any parameters that (*discard_func)() needs.
550 *
551 * Returns: <eslOK> on success.
552 *
553 * Throws: <eslESYS> if a pthread mutex lock/unlock fails.
554 */
555 int
esl_stack_DiscardSelected(ESL_STACK * s,int (* discard_func)(void *,void *),void * param)556 esl_stack_DiscardSelected(ESL_STACK *s, int (*discard_func)(void *, void *), void *param)
557 {
558 int opos;
559 int npos = 0;
560
561 #ifdef HAVE_PTHREAD
562 if (s->do_mutex && pthread_mutex_lock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
563 #endif
564
565 if (s->idata)
566 {
567 for (opos = 0, npos = 0 ; opos < s->n; opos++)
568 if (! (*discard_func)(s->idata+opos, param))
569 s->idata[npos++] = s->idata[opos];
570 }
571 else if (s->pdata)
572 {
573 for (opos = 0, npos = 0 ; opos < s->n; opos++)
574 if (! (*discard_func)(s->pdata[opos], param))
575 s->pdata[npos++] = s->pdata[opos];
576 }
577 else if (s->cdata)
578 {
579 for (opos = 0, npos = 0 ; opos < s->n; opos++)
580 if (! (*discard_func)(s->cdata+opos, param))
581 s->cdata[npos++] = s->cdata[opos];
582 }
583 s->n = npos;
584
585 #ifdef HAVE_PTHREAD
586 if (s->do_mutex && pthread_mutex_unlock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
587 #endif
588 return eslOK;
589 }
590 /*------------- end, main API, pushing/popping ------------------*/
591
592
593
594 /*****************************************************************
595 *# 3. Shuffling stacks
596 *****************************************************************/
597
598 /* Function: esl_stack_Shuffle()
599 * Synopsis: Randomly shuffle the elements in a stack.
600 * Incept: SRE, Mon Mar 31 11:01:06 2008 [Janelia]
601 *
602 * Purpose: Randomly shuffle the elements in stack <s>, using
603 * random numbers from generator <r>.
604 *
605 * Returns: <eslOK> on success, and the stack is randomly
606 * shuffled.
607 */
608 int
esl_stack_Shuffle(ESL_RANDOMNESS * r,ESL_STACK * s)609 esl_stack_Shuffle(ESL_RANDOMNESS *r, ESL_STACK *s)
610 {
611 int n = s->n;
612 int w;
613
614 #ifdef HAVE_PTHREAD
615 if (s->do_mutex && pthread_mutex_lock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
616 #endif
617
618 while (n > 1) {
619 w = esl_rnd_Roll(r, n); /* shuffling algorithm: swap last elem with w, decrement n. */
620 if (s->idata != NULL) ESL_SWAP(s->idata[w], s->idata[n-1], int);
621 else if (s->cdata != NULL) ESL_SWAP(s->cdata[w], s->cdata[n-1], char);
622 else if (s->pdata != NULL) ESL_SWAP(s->pdata[w], s->pdata[n-1], void *);
623 n--;
624 }
625
626 #ifdef HAVE_PTHREAD
627 if (s->do_mutex && pthread_mutex_unlock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
628 #endif
629 return eslOK;
630 }
631
632
633
634 /*****************************************************************
635 *# 4. Using stacks for thread communication.
636 *****************************************************************/
637
638 #if defined HAVE_PTHREAD
639 /* Function: esl_stack_UseMutex()
640 * Synopsis: Protect this stack in a threaded program.
641 * Incept: SRE, Mon Jan 17 14:18:43 2011 [Janelia]
642 *
643 * Purpose: Declare that this stack is going to be operated on by more
644 * than one thread in a multithreaded program, and that all
645 * operations that change its internal state (such as
646 * pushing and popping) need to be protected by a mutex.
647 *
648 * Args: s - the stack to protect
649 *
650 * Returns: <eslOK> on success.
651 *
652 * Throws: <eslEMEM> on allocation failure.
653 * <eslESYS> if <pthread_mutex_init()> fails.
654 */
655 int
esl_stack_UseMutex(ESL_STACK * s)656 esl_stack_UseMutex(ESL_STACK *s)
657 {
658 int pstatus;
659 int status;
660
661 ESL_ALLOC(s->mutex, sizeof(pthread_mutex_t));
662 if ((pstatus = pthread_mutex_init(s->mutex, NULL)) != 0) ESL_XEXCEPTION(eslESYS, "pthread_mutex_init failed with code %d\n", pstatus);
663 s->do_mutex = TRUE;
664 return eslOK;
665
666 ERROR:
667 if (s->mutex) free(s->mutex);
668 s->mutex = NULL;
669 s->do_mutex = FALSE;
670 return status;
671 }
672
673 /* Function: esl_stack_UseCond()
674 * Synopsis: Declare that this stack is used for interthread communication.
675 * Incept: SRE, Mon Jan 17 14:22:06 2011 [Janelia]
676 *
677 * Purpose: Declare that this stack is to be used for communication
678 * between threads. If a thread tries to pop from the stack
679 * and the stack is empty, the Pop will do a <pthread_cond_wait()>
680 * to wait until another thread has done a <Push()>. If a thread
681 * pushes onto the stack, it will do a <pthread_cond_signal()>
682 * to wake up a waiting <Pop()>'er.
683 *
684 * The stack must also have an active mutex. The caller
685 * must call <esl_stack_UseMutex()> before calling
686 * <esl_stack_UseCond().>
687 *
688 * Args: s - the stack to use for push/pop interthread communication
689 *
690 * Returns: <eslOK> on success.
691 *
692 * Throws: <eslEMEM> on allocation failure.
693 * <eslEINVAL> if this stack lacks an active mutex.
694 * <eslESYS> if <pthread_cond_init()> fails.
695 */
696 int
esl_stack_UseCond(ESL_STACK * s)697 esl_stack_UseCond(ESL_STACK *s)
698 {
699 int pstatus;
700 int status;
701
702 if (! s->do_mutex || ! s->mutex) ESL_EXCEPTION(eslEINVAL, "stack has no active mutex; can't call esl_stack_UseCond() on it");
703
704 ESL_ALLOC(s->cond, sizeof(pthread_cond_t));
705 if ((pstatus = pthread_cond_init(s->cond, NULL)) != 0) ESL_XEXCEPTION(eslESYS, "pthread_cond_init failed with code %d\n", pstatus);
706 s->do_cond = TRUE;
707 return eslOK;
708
709 ERROR:
710 if (s->cond) free(s->cond);
711 s->cond = NULL;
712 s->do_cond = FALSE;
713 return status;
714 }
715
716 /* Function: esl_stack_ReleaseCond()
717 * Synopsis: Declare that anyone waiting on this stack may complete.
718 * Incept: SRE, Tue Jan 18 15:57:32 2011 [Janelia]
719 *
720 * Purpose: Release the conditional wait state on stack <s>. In our
721 * idiom for using a stack to coordinate between one or
722 * more client thread adding jobs to a stack, and one or
723 * more worker threads popping them off, we call
724 * <esl_stack_ReleaseCond()> when we know the client(s) are
725 * done. Then the worker(s) seeing an empty job stack may
726 * complete (Pop functions will return eslEOD), rather than
727 * doing a conditional wait waiting for more work to appear
728 * on the stack.
729 *
730 * Returns: <eslOK> on success.
731 *
732 * Throws: <eslESYS> on pthread call failures.
733 */
734 int
esl_stack_ReleaseCond(ESL_STACK * s)735 esl_stack_ReleaseCond(ESL_STACK *s)
736 {
737 if (! s->do_mutex) ESL_EXCEPTION(eslESYS, "no mutex; esl_stack_ReleaseCond() call invalid");
738 if (! s->do_cond) ESL_EXCEPTION(eslESYS, "no conditional wait state is set");
739
740 if (pthread_mutex_lock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_lock() failure");
741 if (pthread_cond_broadcast(s->cond) != 0) ESL_EXCEPTION(eslESYS, "pthread_cond_broadcast() failure");
742
743 /* You can't free s->cond yet; you can only set the flag.
744 * Reason: you may have workers that are ALREADY in a wait state, in pthread_cond_wait(),
745 * and that function depends on s->cond.
746 */
747 s->do_cond = FALSE;
748
749 if (pthread_mutex_unlock(s->mutex) != 0) ESL_EXCEPTION(eslESYS, "pthread_mutex_unlock() failure");
750 return eslOK;
751 }
752 #endif /*HAVE_PTHREAD*/
753 /*-------- end, using stacks for thread communication -----------*/
754
755
756
757 /*****************************************************************
758 * 5. Unit tests
759 *****************************************************************/
760 #ifdef eslSTACK_TESTDRIVE
761
762 #include "esl_random.h"
763
764 static void
utest_integer(void)765 utest_integer(void)
766 {
767 char *msg = "integer stack basic unit test failed";
768 ESL_STACK *s = NULL;
769 int n1 = ESL_STACK_INITALLOC*2+1; /* force two reallocations */
770 int n2 = 0;
771 int i;
772 int val;
773
774 if ((s = esl_stack_ICreate()) == NULL) esl_fatal(msg);
775 for (i = 0; i < n1; i++) if (esl_stack_IPush(s, i) != eslOK) esl_fatal(msg);
776 while (esl_stack_IPop(s, &val) != eslEOD) n2++;
777 if (n1 != n2) esl_fatal(msg);
778 esl_stack_Reuse(s);
779
780 /* same again, with ObjectCount instead of EOD for popping */
781 for (i = 0; i < n1; i++) if (esl_stack_IPush(s, i) != eslOK) esl_fatal(msg);
782 n2 = 0;
783 while (esl_stack_ObjectCount(s)) {
784 if (esl_stack_IPop(s, &val) != eslOK) esl_fatal(msg);
785 n2++;
786 }
787 if (n1 != n2) esl_fatal(msg);
788 esl_stack_Destroy(s);
789 }
790
791 static void
utest_char(void)792 utest_char(void)
793 {
794 char *msg = "char stack basic unit test failed";
795 ESL_STACK *s = NULL;
796 int n1 = ESL_STACK_INITALLOC*2+1; /* force two reallocations */
797 int n2 = 0;
798 int i;
799 char c;
800
801 if ((s = esl_stack_CCreate()) == NULL) esl_fatal(msg);
802 for (i = 0; i < n1; i++) if (esl_stack_CPush(s, 'X') != eslOK) esl_fatal(msg);
803 while (esl_stack_CPop(s, &c) != eslEOD) {
804 if (c != 'X') esl_fatal(msg);
805 n2++;
806 }
807 if (n1 != n2) esl_fatal(msg);
808 esl_stack_Reuse(s);
809
810 /* same again, with ObjectCount instead of EOD for popping */
811 for (i = 0; i < n1; i++) if (esl_stack_CPush(s, 'X') != eslOK) esl_fatal(msg);
812 n2 = 0;
813 while (esl_stack_ObjectCount(s)) {
814 if (esl_stack_CPop(s, &c) != eslOK) esl_fatal(msg);
815 n2++;
816 }
817 if (n1 != n2) esl_fatal(msg);
818 esl_stack_Destroy(s);
819 }
820
821 static void
utest_pointer(void)822 utest_pointer(void)
823 {
824 char *msg = "pointer stack basic unit test failed";
825 ESL_STACK *s = NULL;
826 int n1 = ESL_STACK_INITALLOC*2+1; /* force two reallocations */
827 int n2 = 0;
828 int i;
829 void *p;
830
831 if ((s = esl_stack_PCreate()) == NULL) esl_fatal(msg);
832 for (i = 0; i < n1; i++) {
833 p = malloc(sizeof(int) * 64);
834 if (esl_stack_PPush(s, p) != eslOK) esl_fatal(msg);
835 }
836 while (esl_stack_PPop(s, &p) != eslEOD) { free(p); n2++; }
837 if (n1 != n2) esl_fatal(msg);
838 esl_stack_Reuse(s);
839
840 /* same again, with ObjectCount instead of EOD for popping */
841 for (i = 0; i < n1; i++) {
842 p = malloc(sizeof(int) * 64);
843 if (esl_stack_PPush(s, p) != eslOK) esl_fatal(msg);
844 }
845 n2 = 0;
846 while (esl_stack_ObjectCount(s)) {
847 if (esl_stack_PPop(s, &p) != eslOK) esl_fatal(msg);
848 free(p);
849 n2++;
850 }
851 if (n1 != n2) esl_fatal(msg);
852 esl_stack_Destroy(s);
853 }
854
855 static void
utest_convert2string(void)856 utest_convert2string(void)
857 {
858 char *msg = "stack::convert2string unit test failed";
859 char *str = "ABCDEF";
860 ESL_STACK *s = NULL;
861 int n = strlen(str);
862 int i;
863 char *result = NULL;
864
865 if ((s = esl_stack_CCreate()) == NULL) esl_fatal(msg);
866 for (i = 0; i < n; i++) if (esl_stack_CPush(s, str[i]) != eslOK) esl_fatal(msg);
867 result = esl_stack_Convert2String(s);
868 if (strcmp(result, str) != 0) esl_fatal(msg);
869 free(result); /* after Convert2String, only the string itself remains to be free'd */
870 }
871
872 static void
utest_shuffle(ESL_RANDOMNESS * r)873 utest_shuffle(ESL_RANDOMNESS *r)
874 {
875 char *msg = "stack shuffle unit test failed";
876 ESL_STACK *s = esl_stack_ICreate();
877 int n = ESL_STACK_INITALLOC*2+1; /* exercises reallocation */
878 int *seen = malloc(sizeof(int) * n);
879 int i;
880 int val;
881
882 for (i = 0; i < n; i++) esl_stack_IPush(s, i);
883 esl_stack_Shuffle(r, s);
884
885 for (i = 0; i < n; i++) seen[i] = 0;
886 i = n-1;
887 while (esl_stack_IPop(s, &val) != eslEOD) {
888 seen[val]++;
889 }
890 for (i = 0; i < n; i++) if (seen[i] != 1) esl_fatal(msg);
891
892 free(seen);
893 esl_stack_Destroy(s);
894 }
895
896 /* discard all elems in the stack > thresh */
897 static int
discard_function(void * elemp,void * paramp)898 discard_function(void *elemp, void *paramp)
899 {
900 int elem = * (int *) elemp;
901 int thresh = * (int *) paramp;
902 return (elem > thresh) ? TRUE : FALSE;
903 }
904
905 static void
utest_discard_selected(ESL_RANDOMNESS * r)906 utest_discard_selected(ESL_RANDOMNESS *r)
907 {
908 char *msg = "stack: DiscardSelected() unit test failed";
909 ESL_STACK *ns = esl_stack_ICreate();
910 int n = 1000;
911 int thresh = 42;
912 int npass = 0;
913 int val;
914 int i;
915
916 for (i = 0; i < n; i++)
917 {
918 val = esl_rnd_Roll(r, 100) + 1;
919 if (val <= thresh) npass++;
920 esl_stack_IPush(ns, val);
921 }
922
923 if (esl_stack_DiscardSelected(ns, discard_function, &thresh) != eslOK) esl_fatal(msg);
924
925 if (esl_stack_ObjectCount(ns) != npass) esl_fatal(msg);
926 while (esl_stack_IPop(ns, &val) == eslOK)
927 {
928 if (val > thresh) esl_fatal(msg);
929 npass--;
930 }
931 if (npass != 0) esl_fatal(msg);
932 esl_stack_Destroy(ns);
933 }
934
935
936 #ifdef HAVE_PTHREAD
937 /* Unit test for using a stack as part of an idiom
938 * for a command stack, with one or more threads
939 * adding jobs to the stack, and one or more other threads
940 * pulling jobs off. This idiom is used in the HMMER
941 * hmmpgmd daemon. In this framework, <tt->input>
942 * is a list of jobs to do; <tt->working> is a stack
943 * of jobs waiting to be done; <tt->output> is a
944 * list of jobs done.
945 * pusher_thread() simulates a client, taking
946 * jobs from <tt->input> and adding them to
947 * the <tt->working> stack.
948 * popper_thread() simulates a worker, taking
949 * jobs from <tt->working> and putting them
950 * on the <tt->output> list.
951 *
952 * <tt->working>, therefore, is the read/write stack;
953 * <tt->input> is read-only (it only gets written in
954 * nonthreaded code in main())
955 * <tt->output> is write-only (only gets read in
956 * nonthreaded code in main()).
957 */
958 struct threadtest_s {
959 ESL_STACK *input; /* faux "work unit" queue that the pusher_thread() processes*/
960 ESL_STACK *working; /* interthread communication: pusher puts work on this stack, popper pulls it off */
961 ESL_STACK *output; /* popper_thread() puts "finished" units on this stack */
962 };
963
964 static void *
pusher_thread(void * arg)965 pusher_thread(void *arg)
966 {
967 ESL_RANDOMNESS *r = esl_randomness_CreateFast(0);
968 struct threadtest_s *tt = (struct threadtest_s *) arg;
969 int value;
970
971 while ( esl_stack_IPop(tt->input, &value) == eslOK)
972 {
973 usleep(esl_rnd_Roll(r, 100)+1); /* 1..100 usec delay */
974 esl_stack_IPush(tt->working, value);
975 }
976 esl_randomness_Destroy(r);
977 pthread_exit(NULL);
978 }
979
980 static void *
popper_thread(void * arg)981 popper_thread(void *arg)
982 {
983 ESL_RANDOMNESS *r = esl_randomness_CreateFast(0);
984 struct threadtest_s *tt = (struct threadtest_s *) arg;
985 int value;
986
987 while (esl_stack_IPop(tt->working, &value) == eslOK)
988 {
989 usleep(esl_rnd_Roll(r, 100)+1); /* 1..100 usec delay */
990 esl_stack_IPush(tt->output, value);
991 }
992 esl_randomness_Destroy(r);
993 pthread_exit(NULL);
994 }
995
996 static void
utest_interthread_comm(void)997 utest_interthread_comm(void)
998 {
999 char *msg = "stack::interthread_comm unit test failed";
1000 struct threadtest_s *tt = NULL;
1001 int njobs = 1000;
1002 int *ndone = NULL;
1003 pthread_t tid[4];
1004 int i;
1005 int value;
1006
1007 ndone = malloc(sizeof(int) * njobs);
1008 for (i = 0; i < njobs; i++) ndone[i] = 0;
1009
1010 tt = malloc(sizeof(struct threadtest_s));
1011 tt->input = esl_stack_ICreate();
1012 tt->working = esl_stack_ICreate();
1013 tt->output = esl_stack_ICreate();
1014
1015 esl_stack_UseMutex(tt->input);
1016 esl_stack_UseMutex(tt->working);
1017 esl_stack_UseMutex(tt->output);
1018 esl_stack_UseCond(tt->working);
1019
1020 for (i = 0; i < njobs; i++)
1021 esl_stack_IPush(tt->input, i);
1022
1023 pthread_create(&(tid[0]), NULL, pusher_thread, tt);
1024 pthread_create(&(tid[1]), NULL, pusher_thread, tt);
1025 pthread_create(&(tid[2]), NULL, popper_thread, tt);
1026 pthread_create(&(tid[3]), NULL, popper_thread, tt);
1027
1028 pthread_join(tid[0], NULL);
1029 pthread_join(tid[1], NULL);
1030
1031 esl_stack_ReleaseCond(tt->working);
1032 pthread_join(tid[2], NULL);
1033 pthread_join(tid[3], NULL);
1034
1035 while (esl_stack_IPop(tt->output, &value) == eslOK)
1036 {
1037 if (value < 0 || value >= njobs) esl_fatal(msg);
1038 ndone[value]++;
1039 }
1040 for (i = 0; i < njobs; i++)
1041 if (ndone[i] != 1) esl_fatal(msg);
1042
1043 free(ndone);
1044 esl_stack_Destroy(tt->output);
1045 esl_stack_Destroy(tt->working);
1046 esl_stack_Destroy(tt->input);
1047 free(tt);
1048 return;
1049 }
1050 #endif /* HAVE_PTHREAD -- pthread-specific utests */
1051 #endif /*eslSTACK_TESTDRIVE*/
1052 /*---------------- end of unit tests ----------------------------*/
1053
1054
1055
1056
1057 /*****************************************************************
1058 * 6. Test driver.
1059 *****************************************************************/
1060 #ifdef eslSTACK_TESTDRIVE
1061 /*
1062 * Test driver and API example for the pushdown stack module.
1063 * To compile:
1064 * gcc -g -Wall -I. -L. -DeslSTACK_TESTDRIVE -o testdrive esl_stack.c -leasel -lm
1065 * To run:
1066 * ./testdrive
1067 * Returns 0 (success), or returns nonzero and says why.
1068 */
1069 /* why Pop() into a void *obj_p, instead of directly into int *obj, in
1070 * the test of the pointer stack? On PowerPC/Linux, using gcc -O3,
1071 * trying to Pop() into *obj causes a "dereferencing type-punned
1072 * pointer will break strict-aliasing rules" warning, and the test
1073 * driver crashes with a double free/corruption error in glibc. Lower
1074 * optimization levels don't cause the problem; adding
1075 * -fno-strict-aliasing to the CFLAGS also avoids the problem. I'm
1076 * suspicious that it's a gcc optimizer bug. Pop()'ing into a void *
1077 * avoids the issue altogether. (SRE, Feb 22 2008 J2/119)
1078 */
1079 #include "easel.h"
1080 #include "esl_getopts.h"
1081 #include "esl_random.h"
1082 #include "esl_stack.h"
1083
1084 static ESL_OPTIONS options[] = {
1085 /* name type default env range toggles reqs incomp help docgroup*/
1086 { "-h", eslARG_NONE, FALSE, NULL, NULL, NULL, NULL, NULL, "show brief help on version and usage", 0 },
1087 { "-s", eslARG_INT, "0", NULL, NULL, NULL, NULL, NULL, "set random number seed to <n>", 0 },
1088 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
1089 };
1090 static char usage[] = "[-options]";
1091 static char banner[] = "unit test driver for esl_stack module";
1092
1093 int
main(int argc,char ** argv)1094 main(int argc, char **argv)
1095 {
1096 ESL_GETOPTS *go = esl_getopts_CreateDefaultApp(options, 0, argc, argv, banner, usage);
1097 ESL_RANDOMNESS *rng = esl_randomness_Create(esl_opt_GetInteger(go, "-s"));
1098
1099 fprintf(stderr, "## %s\n", argv[0]);
1100 fprintf(stderr, "# rng seed = %" PRIu32 "\n", esl_randomness_GetSeed(rng));
1101
1102 utest_integer();
1103 utest_char();
1104 utest_pointer();
1105 utest_convert2string();
1106 utest_shuffle(rng);
1107 utest_discard_selected(rng);
1108
1109 #ifdef HAVE_PTHREAD
1110 utest_interthread_comm();
1111 #endif
1112
1113 esl_randomness_Destroy(rng);
1114 esl_getopts_Destroy(go);
1115
1116
1117 fprintf(stderr, "# status = ok\n");
1118 return eslOK;
1119 }
1120 #endif /*eslSTACK_TESTDRIVE*/
1121 /*-------------------- end of test driver -----------------------*/
1122
1123
1124
1125
1126 /*****************************************************************
1127 * 7. Example.
1128 *****************************************************************/
1129 #ifdef eslSTACK_EXAMPLE
1130 /*::cexcerpt::stack_example::begin::*/
1131 /* compile: gcc -g -Wall -I. -o example -DeslSTACK_EXAMPLE esl_stack.c easel.c -lm
1132 * run: ./example
1133 */
1134 #include "easel.h"
1135 #include "esl_stack.h"
1136
1137 int
main(void)1138 main(void)
1139 {
1140 ESL_STACK *ns;
1141 int x;
1142
1143 ns = esl_stack_ICreate();
1144 esl_stack_IPush(ns, 42);
1145 esl_stack_IPush(ns, 7);
1146 esl_stack_IPush(ns, 3);
1147 while (esl_stack_IPop(ns, &x) != eslEOD)
1148 printf("%d\n", x);
1149 esl_stack_Destroy(ns);
1150 return 0;
1151 }
1152 /*::cexcerpt::stack_example::end::*/
1153 #endif /*eslSTACK_EXAMPLE*/
1154 /*------------------------ end of example -----------------------*/
1155
1156