1 /*
2
3 Copyright (C) 2015-2018 Night Dive Studios, LLC.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 */
19 // lllist.C Basic doubly-linked list
20 // Rex E. Bradford (REX)
21 //
22 // This module contains the few routines associated with the simple
23 // llist structure which are not macros. These include:
24 //
25 // llist_insert_queue() - insert a node into a sorted list
26 // llist_move_queue() - move a node within a sorted list
27 // llist_num_nodes() - count # nodes in a list
28 //
29 // See llist.h for the rest of the functionality, or llist.txt
30 // for documentation on how to use llist's.
31 /*
32 * $Header: n:/project/lib/src/dstruct/RCS/lllist.c 1.2 1993/04/16 12:02:19 rex Exp $
33 * $log$
34 */
35
36 #include "llist.h"
37
38 // ----------------------------------------------------------
39 // LITTLE LINKED LIST ROUTINES (SEE MACROS IN LLIST.H TOO)
40 // ----------------------------------------------------------
41 //
42 // llist_insert_queue() inserts a new queue item into list.
43
llist_insert_queue(llist_head * plh,queue * plq)44 void llist_insert_queue(llist_head *plh, queue *plq)
45 {
46 queue *pxx;
47
48 // Point to element past new one in priority
49
50 pxx = (queue *) llist_head(plh);
51 while ((pxx != (queue *)llist_end(plh)) && (plq->priority <= pxx->priority))
52 pxx = pxx->pnext;
53
54 // Patch us in before this element
55
56 llist_insert_before(plq,pxx);
57 }
58
59 // ---------------------------------------------------------
60 //
61 // llist_move_queue() moves a queue item after inserting new priority.
62
llist_move_queue(llist_head * plh,queue * plq)63 uchar llist_move_queue(llist_head *plh, queue *plq)
64 {
65 uchar moved;
66
67 // See if priority warrants moving the queue node
68
69 moved = FALSE;
70 if ((plq->pprev != (queue *)llist_beg(plh)) && (plq->priority > plq->pprev->priority))
71 moved = TRUE;
72 else if ((plq->pnext != (queue *)llist_end(plh)) && (plq->priority < plq->pnext->priority))
73 moved = TRUE;
74
75 // Yes, detach from queue and re-insert
76
77 if (moved)
78 {
79 llist_remove(plq);
80 llist_insert_queue(plh, plq);
81 }
82
83 // Report whether item had to be moved or not
84
85 return(moved);
86 }
87
88 // ----------------------------------------------------------
89 //
90 // llist_num_nodes() counts # nodes in list.
91 //
92 // plh = ptr to list header
93 //
94 // Returns: # nodes in list
95
llist_num_nodes(llist_head * plh)96 int llist_num_nodes(llist_head *plh)
97 {
98 llist *pll;
99 int num;
100
101 num = 0;
102 forallinlist(llist,plh,pll)
103 ++num;
104
105 return(num);
106 }
107