/[svn]/ircd-hybrid-7.2/src/list.c
ViewVC logotype

Contents of /ircd-hybrid-7.2/src/list.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1011 - (show annotations)
Fri Sep 18 10:14:09 2009 UTC (10 years, 2 months ago) by michael
File MIME type: text/x-chdr
File size: 5131 byte(s)
- move list manipulation routines from tools.c to list.c
- mem_frob() goes to memory.c
- sort out redundant/unneeded header includes

1 /*
2 * ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
3 * list.c: Various assorted functions for various structures.
4 *
5 * Copyright (C) 2002 by the past and present ircd coders, and others.
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20 * USA
21 *
22 * $Id$
23 */
24
25 #include "stdinc.h"
26 #include "list.h"
27 #include "balloc.h"
28
29 static BlockHeap *dnode_heap;
30
31
32 /* init_dlink_nodes()
33 *
34 * inputs - NONE
35 * output - NONE
36 * side effects - initializes the dnode BlockHeap
37 */
38 void
39 init_dlink_nodes(void)
40 {
41 dnode_heap = BlockHeapCreate("dlink node", sizeof(dlink_node), DNODE_HEAP_SIZE);
42 }
43
44 /* make_dlink_node()
45 *
46 * inputs - NONE
47 * output - pointer to new dlink_node
48 * side effects - NONE
49 */
50 dlink_node *
51 make_dlink_node(void)
52 {
53 dlink_node *lp = BlockHeapAlloc(dnode_heap);
54
55 return lp;
56 }
57
58 /* free_dlink_node()
59 *
60 * inputs - pointer to dlink_node
61 * output - NONE
62 * side effects - free given dlink_node
63 */
64 void
65 free_dlink_node(dlink_node *ptr)
66 {
67 BlockHeapFree(dnode_heap, ptr);
68 }
69
70 /*
71 * dlink_ routines are stolen from squid, except for dlinkAddBefore,
72 * which is mine.
73 * -- adrian
74 */
75 void
76 dlinkAdd(void *data, dlink_node *m, dlink_list *list)
77 {
78 m->data = data;
79 m->prev = NULL;
80 m->next = list->head;
81
82 /* Assumption: If list->tail != NULL, list->head != NULL */
83 if (list->head != NULL)
84 list->head->prev = m;
85 else if (list->tail == NULL)
86 list->tail = m;
87
88 list->head = m;
89 list->length++;
90 }
91
92 void
93 dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list)
94 {
95 /* Shortcut - if its the first one, call dlinkAdd only */
96 if (b == list->head)
97 dlinkAdd(data, m, list);
98 else
99 {
100 m->data = data;
101 b->prev->next = m;
102 m->prev = b->prev;
103 b->prev = m;
104 m->next = b;
105 list->length++;
106 }
107 }
108
109 void
110 dlinkAddTail(void *data, dlink_node *m, dlink_list *list)
111 {
112 m->data = data;
113 m->next = NULL;
114 m->prev = list->tail;
115
116 /* Assumption: If list->tail != NULL, list->head != NULL */
117 if (list->tail != NULL)
118 list->tail->next = m;
119 else if (list->head == NULL)
120 list->head = m;
121
122 list->tail = m;
123 list->length++;
124 }
125
126 /* Execution profiles show that this function is called the most
127 * often of all non-spontaneous functions. So it had better be
128 * efficient. */
129 void
130 dlinkDelete(dlink_node *m, dlink_list *list)
131 {
132 /* Assumption: If m->next == NULL, then list->tail == m
133 * and: If m->prev == NULL, then list->head == m
134 */
135 if (m->next)
136 m->next->prev = m->prev;
137 else
138 {
139 assert(list->tail == m);
140 list->tail = m->prev;
141 }
142
143 if (m->prev)
144 m->prev->next = m->next;
145 else
146 {
147 assert(list->head == m);
148 list->head = m->next;
149 }
150
151 /* Set this to NULL does matter */
152 m->next = m->prev = NULL;
153 list->length--;
154 }
155
156 /*
157 * dlinkFind
158 * inputs - list to search
159 * - data
160 * output - pointer to link or NULL if not found
161 * side effects - Look for ptr in the linked listed pointed to by link.
162 */
163 dlink_node *
164 dlinkFind(dlink_list *list, void *data)
165 {
166 dlink_node *ptr;
167
168 DLINK_FOREACH(ptr, list->head)
169 if (ptr->data == data)
170 return ptr;
171
172 return NULL;
173 }
174
175 void
176 dlinkMoveList(dlink_list *from, dlink_list *to)
177 {
178 /* There are three cases */
179 /* case one, nothing in from list */
180 if (from->head == NULL)
181 return;
182
183 /* case two, nothing in to list */
184 /* actually if to->head is NULL and to->tail isn't, thats a bug */
185 if (to->head == NULL)
186 {
187 to->head = from->head;
188 to->tail = from->tail;
189 from->head = from->tail = NULL;
190 to->length = from->length;
191 from->length = 0;
192 return;
193 }
194
195 /* third case play with the links */
196 from->tail->next = to->head;
197 from->head->prev = to->head->prev;
198 to->head->prev = from->tail;
199 to->head = from->head;
200 from->head = from->tail = NULL;
201 to->length += from->length;
202 from->length = 0;
203 /* I think I got that right */
204 }
205
206 dlink_node *
207 dlinkFindDelete(dlink_list *list, void *data)
208 {
209 dlink_node *m;
210
211 DLINK_FOREACH(m, list->head)
212 {
213 if (m->data == data)
214 {
215 if (m->next)
216 m->next->prev = m->prev;
217 else
218 {
219 assert(list->tail == m);
220 list->tail = m->prev;
221 }
222 if (m->prev)
223 m->prev->next = m->next;
224 else
225 {
226 assert(list->head == m);
227 list->head = m->next;
228 }
229 /* Set this to NULL does matter */
230 m->next = m->prev = NULL;
231 list->length--;
232
233 return m;
234 }
235 }
236
237 return NULL;
238 }
239
240

Properties

Name Value
svn:eol-style native
svn:keywords Id Revision

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.26