head 1.35; access; symbols PTH_2_0_7:1.34 PTH_2_0_6:1.33 PTH_2_0_5:1.33 PTH_2_0_4:1.33 PTH_2_0_3:1.32 PTH_2_0_2:1.32 PTH_2_0_1:1.32 PTH_2_0_0:1.31 PTH_2_0b2:1.30 PTH_2_0b1:1.30 PTH_2_0b0:1.30 PTH_1_4:1.30.0.2 PTH_1_4_1:1.30 PTH_1_4_0:1.29 PTH_1_3_7:1.26 PTH_1_4a3:1.27 PTH_1_3_6:1.26 PTH_1_4a2:1.27 PTH_1_3_5:1.26 PTH_1_4a1:1.27 PTH_1_3_4:1.26 PTH_1_3:1.26.0.2 PTH_1_3_3:1.26 PTH_1_3_2:1.24 PTH_1_3_1:1.24 PTH_1_3_0:1.24 PTH_1_3b3:1.24 PTH_1_2_3:1.21.2.1 PTH_1_3b2:1.24 PTH_1_3b1:1.24 PTH_1_3a5:1.24 PTH_1_3a4:1.24 PTH_1_3a3:1.24 PTH_1_2_2:1.21.2.1 PTH_1_3a2:1.24 PTH_1_2_1:1.21.2.1 PTH_1_3a1:1.22 PTH_1_2:1.21.0.2 PTH_1_2_0:1.21 PTH_1_2b8:1.20 PTH_1_2b7:1.20 PTH_1_1_6:1.16.2.2 PTH_1_2b6:1.20 PTH_1_2b5:1.20 PTH_1_2b4:1.20 PTH_1_2b3:1.20 PTH_1_2b2:1.19 PTH_1_2b1:1.19 PTH_1_1_5:1.16.2.2 PTH_1_0_6:1.13 PTH_1_0_5:1.13 PTH_1_0:1.13.0.2 PTH_1_1:1.16.0.2 PTH_1_1_4:1.16 PTH_1_1_3:1.14 PTH_1_1_2:1.14 PTH_1_1_1:1.14 PTH_1_1_0:1.14 PTH_1_1b7:1.13 PTH_1_1b6:1.13 PTH_1_1b5:1.13 PTH_1_1b4:1.13 PTH_1_1b3:1.13 PTH_1_1b2:1.13 PTH_1_1b1:1.13 PTH_1_0_4:1.13 PTH_1_0_3:1.13 PTH_1_0_2:1.13 PTH_1_0_1:1.13 PTH_1_0_0:1.13 PTH_1_0b8:1.13 PTH_1_0b7:1.13 PTH_1_0b6:1.13 PTH_1_0b5:1.13 PTH_1_0b4:1.13 PTH_1_0b3:1.11 PTH_1_0b2:1.11 PTH_1_0b1:1.10 PTH_0_9_21:1.10 PTH_0_9_20:1.10 PTH_0_9_19:1.9 PTH_0_9_18:1.9 PTH_0_9_17:1.8 PTH_0_9_16:1.8 PTH_0_9_15:1.8 PTH_0_9_14:1.8 PTH_0_9_13:1.7 PTH_0_9_12:1.6 PTH_0_9_11:1.6 PTH_0_9_10:1.6 PTH_0_9_9:1.5 PTH_0_9_8:1.5 PTH_0_9_7:1.3 PTH_0_9_6:1.3 PTH_0_9_5:1.2 PTH_0_9_4:1.2 PTH_0_9_3:1.2 PTH_0_9_2:1.2 PTH_0_9_1:1.1.1.1 PTH_0_9_0:1.1.1.1 RSE:1.1.1; locks; strict; comment @ * @; 1.35 date 2007.01.01.18.23.53; author rse; state Exp; branches; next 1.34; commitid 9DhdiirNzQPBIP0s; 1.34 date 2006.06.08.17.54.53; author rse; state Exp; branches; next 1.33; commitid x8N3mLVdQgkbdeAr; 1.33 date 2004.12.31.19.34.45; author rse; state Exp; branches; next 1.32; 1.32 date 2004.07.13.10.50.49; author rse; state Exp; branches; next 1.31; 1.31 date 2003.01.01.15.49.12; author rse; state Exp; branches; next 1.30; 1.30 date 2002.01.27.11.03.40; author rse; state Exp; branches; next 1.29; 1.29 date 2001.03.24.15.28.53; author rse; state Exp; branches; next 1.28; 1.28 date 2001.03.24.14.51.04; author rse; state Exp; branches; next 1.27; 1.27 date 2000.03.12.16.27.25; author rse; state Exp; branches; next 1.26; 1.26 date 2000.03.10.09.24.43; author rse; state Exp; branches; next 1.25; 1.25 date 2000.03.10.09.20.51; author rse; state Exp; branches; next 1.24; 1.24 date 99.12.30.21.59.00; author rse; state Exp; branches; next 1.23; 1.23 date 99.11.09.08.11.31; author rse; state Exp; branches; next 1.22; 1.22 date 99.11.01.10.27.19; author rse; state Exp; branches; next 1.21; 1.21 date 99.10.31.11.46.13; author rse; state Exp; branches 1.21.2.1; next 1.20; 1.20 date 99.09.17.08.01.55; author rse; state Exp; branches; next 1.19; 1.19 date 99.09.02.11.23.33; author rse; state Exp; branches; next 1.18; 1.18 date 99.09.01.15.17.49; author rse; state Exp; branches; next 1.17; 1.17 date 99.09.01.10.45.34; author rse; state Exp; branches; next 1.16; 1.16 date 99.08.30.17.17.17; author rse; state Exp; branches 1.16.2.1; next 1.15; 1.15 date 99.08.28.14.30.30; author rse; state Exp; branches; next 1.14; 1.14 date 99.08.19.15.08.53; author rse; state Exp; branches; next 1.13; 1.13 date 99.07.08.10.34.01; author rse; state Exp; branches 1.13.2.1; next 1.12; 1.12 date 99.07.08.10.19.11; author rse; state Exp; branches; next 1.11; 1.11 date 99.07.04.12.05.35; author rse; state Exp; branches; next 1.10; 1.10 date 99.06.24.10.54.29; author rse; state Exp; branches; next 1.9; 1.9 date 99.06.19.15.11.35; author rse; state Exp; branches; next 1.8; 1.8 date 99.06.01.15.43.22; author rse; state Exp; branches; next 1.7; 1.7 date 99.06.01.09.55.26; author rse; state Exp; branches; next 1.6; 1.6 date 99.05.28.09.05.12; author rse; state Exp; branches; next 1.5; 1.5 date 99.05.24.07.58.13; author rse; state Exp; branches; next 1.4; 1.4 date 99.05.24.07.28.00; author rse; state Exp; branches; next 1.3; 1.3 date 99.05.22.14.37.53; author rse; state Exp; branches; next 1.2; 1.2 date 99.05.14.13.43.31; author rse; state Exp; branches; next 1.1; 1.1 date 99.05.13.12.18.16; author rse; state Exp; branches 1.1.1.1; next ; 1.21.2.1 date 99.11.01.10.25.01; author rse; state Exp; branches; next ; 1.16.2.1 date 99.09.01.16.22.21; author rse; state Exp; branches; next 1.16.2.2; 1.16.2.2 date 99.09.02.11.22.51; author rse; state Exp; branches; next ; 1.13.2.1 date 99.09.04.12.47.40; author rse; state Exp; branches; next ; 1.1.1.1 date 99.05.13.12.18.16; author rse; state Exp; branches; next ; desc @@ 1.35 log @Adjusted all copyright messages for new year 2007. @ text @/* ** GNU Pth - The GNU Portable Threads ** Copyright (c) 1999-2007 Ralf S. Engelschall ** ** This file is part of GNU Pth, a non-preemptive thread scheduling ** library which can be found at http://www.gnu.org/software/pth/. ** ** This library is free software; you can redistribute it and/or ** modify it under the terms of the GNU Lesser General Public ** License as published by the Free Software Foundation; either ** version 2.1 of the License, or (at your option) any later version. ** ** This library is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU ** Lesser General Public License for more details. ** ** You should have received a copy of the GNU Lesser General Public ** License along with this library; if not, write to the Free Software ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 ** USA, or contact Ralf S. Engelschall . ** ** pth_pqueue.c: Pth thread priority queues */ /* ``Real hackers can write assembly code in any language'' -- Unknown */ #include "pth_p.h" #if cpp /* thread priority queue */ struct pth_pqueue_st { pth_t q_head; int q_num; }; typedef struct pth_pqueue_st pth_pqueue_t; #endif /* cpp */ /* initialize a priority queue; O(1) */ intern void pth_pqueue_init(pth_pqueue_t *q) { if (q != NULL) { q->q_head = NULL; q->q_num = 0; } return; } /* insert thread into priority queue; O(n) */ intern void pth_pqueue_insert(pth_pqueue_t *q, int prio, pth_t t) { pth_t c; int p; if (q == NULL) return; if (q->q_head == NULL || q->q_num == 0) { /* add as first element */ t->q_prev = t; t->q_next = t; t->q_prio = prio; q->q_head = t; } else if (q->q_head->q_prio < prio) { /* add as new head of queue */ t->q_prev = q->q_head->q_prev; t->q_next = q->q_head; t->q_prev->q_next = t; t->q_next->q_prev = t; t->q_prio = prio; t->q_next->q_prio = prio - t->q_next->q_prio; q->q_head = t; } else { /* insert after elements with greater or equal priority */ c = q->q_head; p = c->q_prio; while ((p - c->q_next->q_prio) >= prio && c->q_next != q->q_head) { c = c->q_next; p -= c->q_prio; } t->q_prev = c; t->q_next = c->q_next; t->q_prev->q_next = t; t->q_next->q_prev = t; t->q_prio = p - prio; if (t->q_next != q->q_head) t->q_next->q_prio -= t->q_prio; } q->q_num++; return; } /* remove thread with maximum priority from priority queue; O(1) */ intern pth_t pth_pqueue_delmax(pth_pqueue_t *q) { pth_t t; if (q == NULL) return NULL; if (q->q_head == NULL) t = NULL; else if (q->q_head->q_next == q->q_head) { /* remove the last element and make queue empty */ t = q->q_head; t->q_next = NULL; t->q_prev = NULL; t->q_prio = 0; q->q_head = NULL; q->q_num = 0; } else { /* remove head of queue */ t = q->q_head; t->q_prev->q_next = t->q_next; t->q_next->q_prev = t->q_prev; t->q_next->q_prio = t->q_prio - t->q_next->q_prio; t->q_prio = 0; q->q_head = t->q_next; q->q_num--; } return t; } /* remove thread from priority queue; O(n) */ intern void pth_pqueue_delete(pth_pqueue_t *q, pth_t t) { if (q == NULL) return; if (q->q_head == NULL) return; else if (q->q_head == t) { if (t->q_next == t) { /* remove the last element and make queue empty */ t->q_next = NULL; t->q_prev = NULL; t->q_prio = 0; q->q_head = NULL; q->q_num = 0; } else { /* remove head of queue */ t->q_prev->q_next = t->q_next; t->q_next->q_prev = t->q_prev; t->q_next->q_prio = t->q_prio - t->q_next->q_prio; t->q_prio = 0; q->q_head = t->q_next; q->q_num--; } } else { t->q_prev->q_next = t->q_next; t->q_next->q_prev = t->q_prev; if (t->q_next != q->q_head) t->q_next->q_prio += t->q_prio; t->q_prio = 0; q->q_num--; } return; } /* determine priority required to favorite a thread; O(1) */ #if cpp #define pth_pqueue_favorite_prio(q) \ ((q)->q_head != NULL ? (q)->q_head->q_prio + 1 : PTH_PRIO_MAX) #endif /* move a thread inside queue to the top; O(n) */ intern int pth_pqueue_favorite(pth_pqueue_t *q, pth_t t) { if (q == NULL) return FALSE; if (q->q_head == NULL || q->q_num == 0) return FALSE; /* element is already at top */ if (q->q_num == 1) return TRUE; /* move to top */ pth_pqueue_delete(q, t); pth_pqueue_insert(q, pth_pqueue_favorite_prio(q), t); return TRUE; } /* increase priority of all(!) threads in queue; O(1) */ intern void pth_pqueue_increase(pth_pqueue_t *q) { if (q == NULL) return; if (q->q_head == NULL) return; /* yes, that's all ;-) */ q->q_head->q_prio += 1; return; } /* return number of elements in priority queue: O(1) */ #if cpp #define pth_pqueue_elements(q) \ ((q) == NULL ? (-1) : (q)->q_num) #endif /* walk to first thread in queue; O(1) */ #if cpp #define pth_pqueue_head(q) \ ((q) == NULL ? NULL : (q)->q_head) #endif /* walk to last thread in queue */ intern pth_t pth_pqueue_tail(pth_pqueue_t *q) { if (q == NULL) return NULL; if (q->q_head == NULL) return NULL; return q->q_head->q_prev; } /* walk to next or previous thread in queue; O(1) */ intern pth_t pth_pqueue_walk(pth_pqueue_t *q, pth_t t, int direction) { pth_t tn; if (q == NULL || t == NULL) return NULL; tn = NULL; if (direction == PTH_WALK_PREV) { if (t != q->q_head) tn = t->q_prev; } else if (direction == PTH_WALK_NEXT) { tn = t->q_next; if (tn == q->q_head) tn = NULL; } return tn; } /* check whether a thread is in a queue; O(n) */ intern int pth_pqueue_contains(pth_pqueue_t *q, pth_t t) { pth_t tc; int found; found = FALSE; for (tc = pth_pqueue_head(q); tc != NULL; tc = pth_pqueue_walk(q, tc, PTH_WALK_NEXT)) { if (tc == t) { found = TRUE; break; } } return found; } @ 1.34 log @Adjusted all copyright messages for new year 2006 @ text @d3 1 a3 1 ** Copyright (c) 1999-2006 Ralf S. Engelschall @ 1.33 log @Adjusted all copyright messages for new year 2005. @ text @d3 1 a3 1 ** Copyright (c) 1999-2005 Ralf S. Engelschall @ 1.32 log @Adjusted all copyright messages for new year 2004. @ text @d3 1 a3 1 ** Copyright (c) 1999-2004 Ralf S. Engelschall @ 1.31 log @Adjusted all copyright messages for new year 2003. @ text @d3 1 a3 1 ** Copyright (c) 1999-2003 Ralf S. Engelschall @ 1.30 log @bump copyright year @ text @d3 1 a3 1 ** Copyright (c) 1999-2002 Ralf S. Engelschall @ 1.29 log @*** empty log message *** @ text @d3 1 a3 1 ** Copyright (c) 1999-2001 Ralf S. Engelschall @ 1.28 log @*** empty log message *** @ text @d41 1 a41 1 /* initialize a priorit queue; O(1) */ @ 1.27 log @*** empty log message *** @ text @d3 1 a3 1 ** Copyright (c) 1999-2000 Ralf S. Engelschall @ 1.26 log @*** empty log message *** @ text @d164 1 a164 1 /* determine priority required to favorite a thread */ d170 1 a170 1 /* move a thread inside queue to the top */ d204 1 a204 1 /* walk to first thread in queue */ d220 1 a220 1 /* walk to next or previous thread in queue */ d240 1 a240 1 /* check whether a thread is in a queue */ @ 1.25 log @*** empty log message *** @ text @d211 8 a218 4 #if cpp #define pth_pqueue_tail(q) \ ((q) == NULL ? NULL : ((q)->q_head == NULL ? NULL : (q)->q_head->q_prev)) #endif @ 1.24 log @*** empty log message *** @ text @d120 1 d148 1 d158 1 d208 6 @ 1.23 log @*** empty log message *** @ text @d3 1 a3 1 ** Copyright (c) 1999 Ralf S. Engelschall @ 1.22 log @*** empty log message *** @ text @d25 1 a25 1 /* ``Real hackers can write assembly d57 1 a57 1 if (q == NULL) d101 1 a101 1 if (q == NULL) d129 1 a129 1 if (q == NULL) d170 1 a170 1 if (q == NULL) d176 1 a176 1 return TRUE; d234 1 a234 1 for (tc = pth_pqueue_head(q); tc != NULL; @ 1.21 log @*** empty log message *** @ text @d2 1 a2 2 ** pth_pqueue.c -- Pth thread priority queues ** d22 2 @ 1.21.2.1 log @*** empty log message *** @ text @d2 2 a3 1 ** GNU Pth - The GNU Portable Threads a22 2 ** ** pth_pqueue.c: Pth thread priority queues @ 1.20 log @*** empty log message *** @ text @d12 1 a12 1 ** version 2 of the License, or (at your option) any later version. @ 1.19 log @*** empty log message *** @ text @d10 1 a10 1 ** modify it under the terms of the GNU Library General Public d17 1 a17 1 ** Library General Public License for more details. d19 1 a19 1 ** You should have received a copy of the GNU Library General Public @ 1.18 log @*** empty log message *** @ text @d88 2 a89 1 t->q_next->q_prio -= t->q_prio; @ 1.17 log @*** empty log message *** @ text @d88 1 d153 1 a153 1 t->q_next->q_prio = t->q_prio + t->q_next->q_prio; @ 1.16 log @*** empty log message *** @ text @d151 2 a152 1 t->q_next->q_prio = t->q_prio - t->q_next->q_prio; @ 1.16.2.1 log @*** empty log message *** @ text @a87 1 t->q_next->q_prio -= t->q_prio; d151 1 a151 2 if (t->q_next != q->q_head) t->q_next->q_prio += t->q_prio; @ 1.16.2.2 log @*** empty log message *** @ text @d88 1 a88 2 if (t->q_next != q->q_head) t->q_next->q_prio -= t->q_prio; @ 1.15 log @*** empty log message *** @ text @d157 6 d175 1 a175 1 pth_pqueue_insert(q, q->q_head->q_prio+1, t); @ 1.14 log @*** empty log message *** @ text @d186 4 a189 6 intern int pth_pqueue_elements(pth_pqueue_t *q) { if (q == NULL) return -1; return q->q_num; } d192 4 a195 6 intern pth_t pth_pqueue_head(pth_pqueue_t *q) { if (q == NULL) return NULL; return q->q_head; } @ 1.13 log @*** empty log message *** @ text @d24 3 a26 1 @ 1.13.2.1 log @*** empty log message *** @ text @a85 2 if (t->q_next != q->q_head) t->q_next->q_prio -= t->q_prio; d149 1 a149 2 if (t->q_next != q->q_head) t->q_next->q_prio += t->q_prio; @ 1.12 log @*** empty log message *** @ text @d2 1 a2 1 ** pth_pqueue.c -- PTH thread priority queues @ 1.11 log @*** empty log message *** @ text @d6 2 a7 2 ** This file is part of PTH, a non-preemptive thread scheduling library ** which can be found at http://www.gnu.org/software/pth/. @ 1.10 log @*** empty log message *** @ text @d7 1 a7 1 ** which can be found at http://www.engelschall.com/sw/pth/. @ 1.9 log @*** empty log message *** @ text @d155 16 @ 1.8 log @*** empty log message *** @ text @d203 17 @ 1.7 log @*** empty log message *** @ text @d29 1 a29 1 /* thread priority queue */ @ 1.6 log @*** empty log message *** @ text @d20 1 a20 1 ** License along with this library; if not, write to the Free @ 1.5 log @*** empty log message *** @ text @d27 11 d39 1 a39 1 void pth_pqueue_init(pth_pqueue_t *q) d49 1 a49 1 void pth_pqueue_insert(pth_pqueue_t *q, int prio, pth_t t) d92 1 a92 1 pth_t pth_pqueue_delmax(pth_pqueue_t *q) d122 1 a122 1 void pth_pqueue_delete(pth_pqueue_t *q, pth_t t) d156 1 a156 1 void pth_pqueue_increase(pth_pqueue_t *q) d168 1 a168 1 int pth_pqueue_elements(pth_pqueue_t *q) d176 1 a176 1 pth_t pth_pqueue_head(pth_pqueue_t *q) d184 1 a184 1 pth_t pth_pqueue_walk(pth_pqueue_t *q, pth_t t, int direction) @ 1.4 log @*** empty log message *** @ text @d6 1 a6 1 ** This file is part of PTH, a non-preemtive thread scheduling library @ 1.3 log @*** empty log message *** @ text @d139 1 @ 1.2 log @*** empty log message *** @ text @a0 40 /* ==================================================================== * Copyright (c) 1999 Ralf S. Engelschall. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. All advertising materials mentioning features or use of this * software must display the following acknowledgment: * "This product includes software developed by * Ralf S. Engelschall ." * * 4. Redistributions of any form whatsoever must retain the following * acknowledgment: * "This product includes software developed by * Ralf S. Engelschall ." * * THIS SOFTWARE IS PROVIDED BY RALF S. ENGELSCHALL ``AS IS'' AND ANY * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RALF S. ENGELSCHALL OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. * ==================================================================== */ d2 21 a22 2 ** Non-Preemtive Scheduler Library (PTH) ** pth_pqueue.c -- priority queue code @ 1.1 log @Initial revision @ text @d184 28 @ 1.1.1.1 log @Import of PTH into CVS @ text @@