home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / gnat-2.06-src.tgz / tar.out / fsf / gnat / ada / threads / src / queue.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  15KB  |  658 lines
  1. /* Copyright (C) 1992, the Florida State University
  2.    Distributed by the Florida State University under the terms of the
  3.    GNU Library General Public License.
  4.  
  5. This file is part of Pthreads.
  6.  
  7. Pthreads is free software; you can redistribute it and/or
  8. modify it under the terms of the GNU Library General Public
  9. License as published by the Free Software Foundation (version 2).
  10.  
  11. Pthreads is distributed "AS IS" in the hope that it will be
  12. useful, but WITHOUT ANY WARRANTY; without even the implied
  13. warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14. See the GNU Library General Public License for more details.
  15.  
  16. You should have received a copy of the GNU Library General Public
  17. License along with Pthreads; see the file COPYING.  If not, write
  18. to the Free Software Foundation, 675 Mass Ave, Cambridge,
  19. MA 02139, USA.
  20.  
  21. Report problems and direct all questions to:
  22.  
  23.   pthreads-bugs@ada.cs.fsu.edu
  24.  
  25.   @(#)queue.c    2.5 4/12/95
  26.  
  27. */
  28.  
  29. /*
  30.  * Implementation of queues
  31.  */
  32.  
  33. #include "pthread_internals.h"
  34.  
  35. extern pthread_timer_q pthread_timer;
  36. #ifdef RAND_SWITCH
  37. int pthread_n_ready;
  38. #endif
  39.  
  40. /*------------------------------------------------------------*/
  41. /*
  42.  * pthread_q_all_enq - enqueing a pthread into an unsorted queue (linked list)
  43.  */
  44. void pthread_q_all_enq(q, t)
  45.      pthread_queue_t q;
  46.      pthread_t t;
  47. {
  48. #ifdef DEBUG
  49.   if (!t || t->state & T_RETURNED)
  50.     fprintf(stderr, "ERROR: q_all_enq on returned thread attempted\n");
  51. #endif
  52.  
  53.   t->next[ALL_QUEUE] = q->head;
  54.   if (q->head == NO_PTHREAD)
  55.     q->tail = t;
  56.   q->head = t;
  57. }
  58.  
  59. /*------------------------------------------------------------*/
  60. /*
  61.  * pthread_q_primary_enq - enqueing a pthread into a queue sorted by priority
  62.  * (ordering: last in priority level)
  63.  */
  64. void pthread_q_primary_enq(q, t)
  65.      pthread_queue_t q;
  66.      pthread_t t;
  67. {
  68.   pthread_t prev = NO_PTHREAD;
  69.   pthread_t next = q->head;
  70.  
  71. #ifdef DEBUG
  72.   if (!t || t->state & T_RETURNED)
  73.     fprintf(stderr, "ERROR: q_primary_enq on returned thread attempted\n");
  74. #endif
  75.  
  76.   while (next != NO_PTHREAD && next->attr.prio >= t->attr.prio) {
  77.     prev = next;
  78.     next = next->next[PRIMARY_QUEUE];
  79.   }
  80.  
  81.   t->next[PRIMARY_QUEUE] = next;
  82.   if (prev == NO_PTHREAD) {
  83.     q->head = t;
  84.     if (q == &ready)
  85.       state_change = TRUE;
  86.   }
  87.   else
  88.     prev->next[PRIMARY_QUEUE] = t;
  89.  
  90.   if (next == NO_PTHREAD)
  91.     q->tail = t;
  92.  
  93.   t->queue = q;
  94. #ifdef RAND_SWITCH
  95.   if (q == &ready)
  96.     pthread_n_ready++;
  97. #endif
  98. }
  99.  
  100. /*------------------------------------------------------------*/
  101. /*
  102.  * pthread_q_primary_enq_first - enqueing a pthread into a queue
  103.  * sorted by priority
  104.  * (ordering: first in priority level)
  105.  */
  106. void pthread_q_primary_enq_first(q, t)
  107.      pthread_queue_t q;
  108.      pthread_t t;
  109. {
  110.   pthread_t prev = NO_PTHREAD;
  111.   pthread_t next = q->head;
  112.  
  113. #ifdef DEBUG
  114.   if (!t || t->state & T_RETURNED)
  115.     fprintf(stderr, "ERROR: q_primary_enq on returned thread attempted\n");
  116. #endif
  117.  
  118.   while (next != NO_PTHREAD && next->attr.prio > t->attr.prio) {
  119.     prev = next;
  120.     next = next->next[PRIMARY_QUEUE];
  121.   }
  122.  
  123.   t->next[PRIMARY_QUEUE] = next;
  124.   if (prev == NO_PTHREAD) {
  125.     q->head = t;
  126.     if (q == &ready)
  127.       state_change = TRUE;
  128.   }
  129.   else
  130.     prev->next[PRIMARY_QUEUE] = t;
  131.  
  132.   if (next == NO_PTHREAD)
  133.     q->tail = t;
  134.  
  135.   t->queue = q;
  136. #ifdef RAND_SWITCH
  137.   if (q == &ready)
  138.     pthread_n_ready++;
  139. #endif
  140. }
  141.  
  142. #ifdef STAND_ALONE
  143.  
  144. /*------------------------------------------------------------*/
  145. /*
  146.  * pthread_q_timed_enq - enqueing a pthread into a list sorted by time
  147.  */
  148. void pthread_q_timed_enq(q, p)
  149.         pthread_timer_q_t *q;
  150.         pthread_t p;
  151. {
  152.   pthread_t prev=NO_PTHREAD, next=*q;
  153.  
  154.   while (next != NO_PTHREAD && GT_NTIME(p->tp, next->tp)) {
  155.     prev = next;
  156.     next = next->next[TIMER_QUEUE];
  157.   }
  158.   p->next[TIMER_QUEUE] = next;
  159.   if (prev == NO_PTHREAD)
  160.     *q = p;
  161.   else
  162.     prev->next[TIMER_QUEUE] = p;
  163. }
  164.  
  165. #else !STAND_ALONE
  166.  
  167. /*------------------------------------------------------------*/
  168. /*
  169.  * pthread_q_timed_enq - enqueing a pthread into a list sorted by time
  170.  */
  171. void pthread_q_timed_enq(q, in, mode, p)
  172.     pthread_timer_q_t q;
  173.     struct timeval in;
  174.     int mode;
  175.     pthread_t p;
  176. {
  177.   timer_ent_t prev = NO_TIMER;
  178.   timer_ent_t next = q->head;
  179.   timer_ent_t timer_ent;
  180.  
  181. #ifdef DEBUG
  182.   if (!p || p->state & T_RETURNED)
  183.     fprintf(stderr, "ERROR: q_timed_enq on returned thread attempted\n");
  184. #endif
  185.  
  186. #ifdef DEF_RR
  187. #ifdef MALLOC
  188.   if ((timer_ent = (timer_ent_t) pthread_malloc(sizeof(struct timer_ent))) == NULL) {
  189. #else !MALLOC
  190.   if ((timer_ent = (timer_ent_t) malloc(sizeof(struct timer_ent))) == NULL) {
  191. #endif MALLOC
  192.     set_errno(EAGAIN);
  193.     return;
  194.   }
  195.  
  196.   timer_ent->mode = mode;
  197.   timer_ent->thread = p;
  198. #else
  199.   timer_ent = p;
  200. #endif
  201.   timer_ent->tp.tv_sec = in.tv_sec;
  202.   timer_ent->tp.tv_usec = in.tv_usec;
  203.  
  204.   while (next != NO_TIMER && GT_TIME(timer_ent->tp, next->tp)) {
  205.     prev = next;
  206.     next = next->next[TIMER_QUEUE];
  207.   }
  208.  
  209.   timer_ent->next[TIMER_QUEUE] = next;
  210.   if (prev == NO_TIMER)
  211.     q->head = timer_ent;
  212.   else
  213.     prev->next[TIMER_QUEUE] = timer_ent;
  214.  
  215.   if (next == NO_TIMER)
  216.     q->tail = timer_ent;
  217. }
  218.  
  219. #endif STAND_ALONE
  220.  
  221. /*------------------------------------------------------------*/
  222. /*
  223.  * pthread_q_enq_head - enqueue head of queue
  224.  */
  225. void pthread_q_enq_head(q, t, index)
  226.      pthread_queue_t q;
  227.      pthread_t t;
  228.      int index;
  229. {
  230. #ifdef DEBUG
  231.   if (!t || t->state & T_RETURNED)
  232.     fprintf(stderr, "ERROR: q_enq_head on returned thread attempted\n");
  233. #endif
  234.  
  235.   if ((t->next[index] = q->head) == NO_PTHREAD)
  236.     q->tail = t;
  237.   q->head = t;
  238.   if (!(t->queue))
  239.     t->queue = q;
  240.   if (q == &ready) {
  241.     state_change = TRUE;
  242. #ifdef RAND_SWITCH 
  243.     pthread_n_ready++; 
  244. #endif
  245.   }
  246. }
  247.  
  248. #if defined(RR_SWITCH) || defined(RAND_SWITCH)
  249. /*------------------------------------------------------------*/
  250. /*
  251.  * pthread_q_enq_tail - enqueing a pthread into a queue at the tail (RR)
  252.  */
  253. void pthread_q_enq_tail(q)
  254.      pthread_queue_t q;
  255. {
  256.   pthread_t prev = NO_PTHREAD;
  257.   pthread_t next = q->head;
  258.   pthread_t t = mac_pthread_self();
  259.  
  260. #ifdef DEBUG
  261.   if (!t || t->state & T_RETURNED)
  262.     fprintf(stderr, "ERROR: q_primary_enq on returned thread attempted\n");
  263. #endif
  264.  
  265.   while (next != NO_PTHREAD ) {
  266.     prev = next;
  267.     next = next->next[PRIMARY_QUEUE];
  268.   }
  269.  
  270.   t->next[PRIMARY_QUEUE] = NO_PTHREAD;
  271.   if (prev == NO_PTHREAD) {
  272.     q->head = t;
  273.     if (q == &ready)
  274.       state_change = TRUE;
  275.   }
  276.   else
  277.     prev->next[PRIMARY_QUEUE] = t;
  278.  
  279.   if (!(t->queue))
  280.     t->queue = q;
  281.   q->tail = t;
  282. #ifdef RAND_SWITCH 
  283.   if (q == &ready)
  284.     pthread_n_ready++; 
  285. #endif
  286. }
  287. #endif
  288.  
  289. /*------------------------------------------------------------*/
  290. /*
  291.  * pthread_q_deq - dequeue a thread from a queue
  292.  */
  293. void pthread_q_deq(q, t, index)
  294.      pthread_queue_t q;
  295.      pthread_t t;
  296.      int index;
  297. {
  298.   pthread_t prev = NO_PTHREAD;
  299.   pthread_t next = q->head;
  300.   timer_ent_t tmr;
  301.   struct timeval now;
  302.  
  303.   while (next != NO_PTHREAD && next != t) {
  304.     prev = next;
  305.     next = next->next[index];
  306.   }
  307.  
  308.   if (next == NO_PTHREAD) {
  309. #ifdef DEBUG
  310.     fprintf(stderr, "pthread_q_deq(thread %x, index %d) failed\n", t, index);
  311. #endif
  312.     return;
  313.   }
  314.  
  315.   if ((next = next->next[index]) == NO_PTHREAD)
  316.     q->tail = prev;
  317.   
  318.   if (prev == NO_PTHREAD) {
  319.     q->head = next;
  320.     if (q == &ready)
  321.       state_change = TRUE;
  322.   }
  323.   else
  324.     prev->next[index] = next;
  325.   
  326.   t->next[index] = NO_PTHREAD;
  327.   
  328.   if (index == PRIMARY_QUEUE) {
  329.     t->queue = NULL;
  330. #ifdef DEF_RR
  331.     if (t == mac_pthread_self() && t->attr.sched == SCHED_RR &&
  332.     t->state & T_ASYNCTIMER) {
  333.       for (tmr = pthread_timer.head; tmr; tmr = tmr->next[TIMER_QUEUE])
  334.     if (tmr->thread == t && tmr->mode == RR_TIME)
  335.       break;
  336.       if (tmr && !gettimeofday(&now, (struct timezone *) NULL) &&
  337.       GT_TIME(tmr->tp, now))
  338.     MINUS_TIME(t->interval, tmr->tp, now);
  339.       else
  340.     t->interval.tv_usec = t->interval.tv_sec = 0;
  341.  
  342.       pthread_cancel_timed_sigwait(t, FALSE, RR_TIME, FALSE);
  343.     }
  344. #endif
  345.   }
  346.  
  347. #ifdef RAND_SWITCH 
  348.   if (q == &ready)
  349.     pthread_n_ready--; 
  350. #endif
  351. }
  352.  
  353. #ifdef STAND_ALONE
  354.  
  355. /*------------------------------------------------------------*/
  356. /*
  357.  * pthread_q_timed_deq - dequeue thread from (timer) queue
  358.  */
  359. void pthread_q_timed_deq(q, t)
  360. pthread_timer_q_t *q;
  361. pthread_t t;
  362. {
  363.   pthread_t prev=NO_PTHREAD, next= *q;
  364.  
  365.   while(next && next != t) {
  366.     prev = next;
  367.     next = next->next[TIMER_QUEUE];
  368.   }
  369.   if (next == NO_PTHREAD)
  370.     return;
  371.  
  372.   if (prev == NO_PTHREAD)
  373.     *q = next->next[TIMER_QUEUE];
  374.   else
  375.     prev->next[TIMER_QUEUE] = next->next[TIMER_QUEUE];
  376.  
  377.   t->next[TIMER_QUEUE] = NO_PTHREAD;
  378. }
  379.  
  380. #else !STAND_ALONE
  381.  
  382. /*------------------------------------------------------------*/
  383. /*
  384.  * pthread_q_timed_deq - dequeue thread from (timer) queue
  385.  */
  386. void pthread_q_timed_deq(q, t)
  387.     pthread_timer_q_t q;
  388.     pthread_t t;
  389. {
  390.   timer_ent_t temp, prev = NO_TIMER;
  391.   timer_ent_t next = q->head;
  392.  
  393. #ifdef DEF_RR
  394.   while (next != NO_TIMER && next->thread != t) {
  395. #else
  396.   while (next != NO_TIMER && next != t) {
  397. #endif
  398.     prev = next;
  399.     next = next->next[TIMER_QUEUE];
  400.   }
  401.  
  402.   if (next == NO_TIMER) {
  403. #ifdef DEBUG
  404.     fprintf(stderr, "pthread_q_timed_deq(thread %x) failed\n", t);
  405. #endif
  406.     return;
  407.   }
  408.  
  409.   temp = next;
  410.   if ((next = next->next[TIMER_QUEUE]) == NO_TIMER)
  411.     q->tail = prev;
  412.  
  413.   if (prev == NO_TIMER)
  414.     q->head = next;
  415.   else
  416.     prev->next[TIMER_QUEUE] = next;
  417.  
  418. #ifdef DEF_RR
  419. #ifdef MALLOC
  420.   pthread_free(temp);
  421. #else !MALLOC
  422.   free(temp);
  423. #endif
  424.   t->num_timers--;
  425. #endif
  426. }
  427.  
  428. #endif STAND_ALONE
  429.  
  430. /*------------------------------------------------------------*/
  431. /*
  432.  * pthread_q_deq_head - dequeue head of queue and return head
  433.  */
  434. pthread_t pthread_q_deq_head(q, index)
  435.      pthread_queue_t q;
  436.      int index;
  437. {
  438.   pthread_t t;
  439.  
  440.   if ((t = q->head) != NO_PTHREAD) {
  441.     if (q == &ready)
  442.       state_change = TRUE;
  443.     if ((q->head = t->next[index]) == NO_PTHREAD)
  444.       q->tail = NO_PTHREAD;
  445.     else
  446.       t->next[index] = NO_PTHREAD;
  447.  
  448.     if (index == PRIMARY_QUEUE) {
  449.       t->queue = NULL;
  450. #ifdef DEF_RR
  451.       if (t == mac_pthread_self() && t->attr.sched == SCHED_RR &&
  452.       t->state & T_ASYNCTIMER)
  453.         pthread_cancel_timed_sigwait(t, FALSE, RR_TIME, FALSE);
  454. #endif
  455.     }
  456.   }
  457.  
  458. #ifdef RAND_SWITCH  
  459.   if (q == &ready)
  460.     pthread_n_ready--;  
  461. #endif
  462.  
  463.   return(t);
  464. }
  465.  
  466. #ifdef RAND_SWITCH
  467. /*------------------------------------------------------------*/
  468. /*
  469.  * pthread_q_exchange_rand - Remove the current thread from the queue and
  470.  *                   put that at the end of the queue and put the
  471.  * thread #index in the queue at the head.
  472.  */
  473. void pthread_q_exchange_rand(q)
  474.      pthread_queue_t q;
  475. {
  476.   pthread_t t = mac_pthread_self();
  477.   int i, index = (int)random() % pthread_n_ready;
  478.  
  479. #ifdef DEBUG                        
  480.   if (!t || t->state & T_RETURNED)
  481.     fprintf(stderr, "ERROR: q_primary_enq on returned thread attempted\n");
  482. #endif
  483.  
  484.   pthread_q_deq(q, t, PRIMARY_QUEUE);
  485.   pthread_q_enq_tail(q);
  486.   t = q->head;
  487.   for (i = 0; i < index; i++)
  488.     t = t->next[PRIMARY_QUEUE];
  489.  
  490.   pthread_q_deq(q, t, PRIMARY_QUEUE);
  491.   pthread_q_enq_head(q, t, PRIMARY_QUEUE);
  492. }
  493. #endif
  494.  
  495. /*------------------------------------------------------------*/
  496. /*
  497.  * pthread_q_all_find_receiver - find thread in all queue s.t.
  498.  * (a) either a handler is installed and the thread has the signal unmasked,
  499.  * (b) or the signal is in the sigwaitset,
  500.  * and return this thread (or NO_THREAD).
  501.  */
  502. pthread_t pthread_q_all_find_receiver(q, sig)
  503.      pthread_queue_t q;
  504.      int sig;
  505. {
  506.   pthread_t t;
  507.  
  508.   for (t = q->head; t != NO_PTHREAD; t = t->next[ALL_QUEUE])
  509.     if (!sigismember(&t->mask, sig))
  510.       break;
  511.  
  512.   return(t);
  513. }
  514.  
  515. /*------------------------------------------------------------*/
  516. /*
  517.  * pthread_q_sleep_thread - block current thread: move from anywhere in ready
  518.  * queue to some other queue;
  519.  * Assumes SET_KERNEL_FLAG
  520.  */
  521. void pthread_q_sleep_thread(q, p, index)
  522. pthread_queue_t q;
  523. pthread_t p;
  524. int index;
  525. {
  526.   pthread_q_deq(&ready, p, PRIMARY_QUEUE);
  527.   if (index == PRIMARY_QUEUE)
  528.     pthread_q_primary_enq(q, p);
  529.   p->state &= ~T_RUNNING;
  530.   p->state |= T_BLOCKED;
  531. }
  532.  
  533. /*------------------------------------------------------------*/
  534. /*
  535.  * pthread_q_sleep - block current thread: move from head of ready to some 
  536.  * other queue; Assumes SET_KERNEL_FLAG
  537.  */
  538. void pthread_q_sleep(q, index)
  539. pthread_queue_t q;
  540. int index;
  541. {
  542.   pthread_t p;
  543.   
  544.   p = pthread_q_deq_head(&ready, PRIMARY_QUEUE);
  545.   if (index == PRIMARY_QUEUE)
  546.     pthread_q_primary_enq(q, p);
  547.   p->state &= ~T_RUNNING;
  548.   p->state |= T_BLOCKED;
  549. }
  550.  
  551. /*------------------------------------------------------------*/
  552. /* 
  553.  * pthread_q_wakeup -  Wakeup head of the queue and return head.
  554.  * If there one exists, deq him and put him on the run queue ready
  555.  * to execute.  Note: Deq takes care of who runs when., so scheduling
  556.  * goes on fine!
  557.  * Assumes SET_KERNEL_FLAG
  558.  */
  559. void pthread_q_wakeup(q, index)
  560.      pthread_queue_t q;
  561.      int index;
  562. {
  563.   pthread_t p;
  564.  
  565.   p = pthread_q_deq_head(q, index);
  566.   if (p != NO_PTHREAD && !(p->state & T_RUNNING)) {
  567.     p->state &= ~(T_BLOCKED | T_INTR_POINT);
  568.     p->state |= T_RUNNING;
  569.     pthread_q_primary_enq(&ready, p);
  570.   }
  571. }
  572.  
  573. /*------------------------------------------------------------*/
  574. /*
  575.  * pthread_q_wakeup_thread -  same as pthread_q_wakeup but for specific thread
  576.  * return pointer to thread if thread found in queue, NO_PTHREAD otherwise
  577.  */
  578. void pthread_q_wakeup_thread(q, p, index)
  579.      pthread_queue_t q;
  580.      pthread_t p;
  581. {
  582.   if (q != NO_QUEUE)
  583.     pthread_q_deq(q, p, index);
  584.  
  585.   if (p != NO_PTHREAD && !(p->state & T_RUNNING)) {
  586.     p->state &= ~(T_BLOCKED | T_INTR_POINT);
  587.     p->state |= T_RUNNING;
  588.     pthread_q_primary_enq(&ready, p);
  589.   }
  590. }
  591.       
  592. /*------------------------------------------------------------*/
  593. /*
  594.  * pthread_q_timed_wakeup_thread - same as pthread_q_wakeup_thread but 
  595.  * for timer queue
  596.  */
  597. void pthread_q_timed_wakeup_thread(q, p, activate)
  598.      pthread_timer_q_t q;
  599.      pthread_t p;
  600.      int activate;
  601. {
  602.   if (q != NO_TIMER_QUEUE)
  603.     pthread_q_timed_deq(q, p);
  604.  
  605.   if (activate && p != NO_PTHREAD && !(p->state & T_RUNNING)) {
  606.     p->state &= ~(T_BLOCKED | T_INTR_POINT);
  607.     p->state |= T_RUNNING;
  608.     pthread_q_primary_enq(&ready, p);
  609.   }
  610. }
  611.  
  612. /*------------------------------------------------------------*/
  613. /*
  614.  * pthread_q_wakeup_all - Wake up all the threads waiting on a condition   
  615.  * change.  See pthread_q_wakeup.
  616.  * Assumes SET_KERNEL_FLAG
  617.  */
  618. void pthread_q_wakeup_all(q, index)
  619.      pthread_queue_t q;
  620. {
  621.   pthread_t p;
  622.   
  623.   while ((p = pthread_q_deq_head(q, index)) != NO_PTHREAD)
  624.     if (!(p->state & T_RUNNING)) {
  625.       p->state &= ~(T_BLOCKED | T_INTR_POINT);
  626.       p->state |= T_RUNNING;
  627.       pthread_q_primary_enq(&ready, p);
  628.     }
  629. }
  630.  
  631. /*------------------------------------------------------------*/
  632. #ifdef _POSIX_THREADS_PRIO_PROTECT
  633. /*
  634.  * pthread_mutex_q_adjust - Removes p from primary queue and reinserts
  635.  * it in the primary queue in the first place among threads of same
  636.  * priority. Unlocking a mutex should not take it to the end.
  637.  * Assumes that unlocking can only lower the priority.
  638.  * Assumes SET_KERNEL_FLAG
  639.  */
  640. void pthread_mutex_q_adjust(p)
  641.      pthread_t p;
  642. {
  643.   pthread_queue_t q = p->queue;
  644.   pthread_t next = p->next[PRIMARY_QUEUE];
  645.  
  646.   /*
  647.    * If queue has only one thread or new priority is still higher than
  648.    * next priority, no reordering is necessary.
  649.    */
  650.   if (!next || p->attr.prio >= next->attr.prio)
  651.     return;
  652.  
  653.   pthread_q_deq(q, p, PRIMARY_QUEUE);
  654.   pthread_q_primary_enq_first(q, p);
  655. }
  656. /*------------------------------------------------------------*/
  657. #endif
  658.