/[svn]/ircd-hybrid/libio/misc/list.c
ViewVC logotype

Contents of /ircd-hybrid/libio/misc/list.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 501 - (show annotations)
Thu Mar 2 10:40:42 2006 UTC (15 years, 3 months ago) by michael
File MIME type: text/x-chdr
File size: 4762 byte(s)
- Removed all inlined versions of dlink* functions
- Added an assert()s to dlinkDelete()
- NDEBUG is now undefined by default for testing and beta versions

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
27 static BlockHeap *dnode_heap = NULL;
28
29 /* init_dlink_nodes()
30 *
31 * inputs - NONE
32 * output - NONE
33 * side effects - initializes the dnode BlockHeap
34 */
35 void
36 init_dlink_nodes(void)
37 {
38 dnode_heap = BlockHeapCreate("dlink node", sizeof(dlink_node), DNODE_HEAP_SIZE);
39 }
40
41 /* make_dlink_node()
42 *
43 * inputs - NONE
44 * output - pointer to new dlink_node
45 * side effects - NONE
46 */
47 dlink_node *
48 make_dlink_node(void)
49 {
50 return BlockHeapAlloc(dnode_heap);
51 }
52
53 /* free_dlink_node()
54 *
55 * inputs - pointer to dlink_node
56 * output - NONE
57 * side effects - free given dlink_node
58 */
59 void
60 free_dlink_node(dlink_node *ptr)
61 {
62 BlockHeapFree(dnode_heap, ptr);
63 }
64
65 /*
66 * dlink_ routines are stolen from squid, except for dlinkAddBefore,
67 * which is mine.
68 * -- adrian
69 */
70 void
71 dlinkAdd(void *data, dlink_node *m, dlink_list *list)
72 {
73 m->data = data;
74 m->prev = NULL;
75 m->next = list->head;
76
77 /* Assumption: If list->tail != NULL, list->head != NULL */
78 if (list->head != NULL)
79 list->head->prev = m;
80 else /* if (list->tail == NULL) */
81 list->tail = m;
82
83 list->head = m;
84 ++list->length;
85 }
86
87 void
88 dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list)
89 {
90 /* Shortcut - if its the first one, call dlinkAdd only */
91 if (b == list->head)
92 dlinkAdd(data, m, list);
93 else
94 {
95 m->data = data;
96 b->prev->next = m;
97 m->prev = b->prev;
98 b->prev = m;
99 m->next = b;
100 ++list->length;
101 }
102 }
103
104 void
105 dlinkAddTail(void *data, dlink_node *m, dlink_list *list)
106 {
107 m->data = data;
108 m->next = NULL;
109 m->prev = list->tail;
110 /* Assumption: If list->tail != NULL, list->head != NULL */
111 if (list->tail != NULL)
112 list->tail->next = m;
113 else /* if (list->head == NULL) */
114 list->head = m;
115
116 list->tail = m;
117 ++list->length;
118 }
119
120 /* Execution profiles show that this function is called the most
121 * often of all non-spontaneous functions. So it had better be
122 * efficient. */
123 void
124 dlinkDelete(dlink_node *m, dlink_list *list)
125 {
126 /* Assumption: If m->next == NULL, then list->tail == m
127 * and: If m->prev == NULL, then list->head == m
128 */
129 if (m->next)
130 m->next->prev = m->prev;
131 else {
132 assert(list->tail == m);
133 list->tail = m->prev;
134 }
135 if (m->prev)
136 m->prev->next = m->next;
137 else {
138 assert(list->head == m);
139 list->head = m->next;
140 }
141
142 /* Set this to NULL does matter */
143 m->next = m->prev = NULL;
144 assert(list->length > 0);
145 --list->length;
146 }
147
148 /*
149 * dlinkFind
150 * inputs - list to search
151 * - data
152 * output - pointer to link or NULL if not found
153 * side effects - Look for ptr in the linked listed pointed to by link.
154 */
155 dlink_node *
156 dlinkFind(dlink_list *list, void *data)
157 {
158 dlink_node *ptr;
159
160 DLINK_FOREACH(ptr, list->head)
161 if (ptr->data == data)
162 return ptr;
163
164 return NULL;
165 }
166
167 void
168 dlinkMoveList(dlink_list *from, dlink_list *to)
169 {
170 /* There are three cases */
171 /* case one, nothing in from list */
172 if(from->head == NULL)
173 return;
174
175 /* case two, nothing in to list */
176 /* actually if to->head is NULL and to->tail isn't, thats a bug */
177
178 if(to->head == NULL)
179 {
180 to->head = from->head;
181 to->tail = from->tail;
182 from->head = from->tail = NULL;
183 to->length = from->length;
184 from->length = 0;
185 return;
186 }
187
188 /* third case play with the links */
189
190 from->tail->next = to->head;
191 from->head->prev = to->head->prev;
192 to->head->prev = from->tail;
193 to->head = from->head;
194 from->head = from->tail = NULL;
195 to->length += from->length;
196 from->length = 0;
197 /* I think I got that right */
198 }
199
200 dlink_node *
201 dlinkFindDelete(dlink_list *list, void *data)
202 {
203 dlink_node *m = NULL;
204
205 DLINK_FOREACH(m, list->head)
206 {
207 if (m->data == data)
208 {
209 dlinkDelete(m, list);
210 return m;
211 }
212 }
213
214 return NULL;
215 }

Properties

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

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