trunk/src/list.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 2000-2014 ircd-hybrid development team
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program 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 General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 *  USA
 */

/*! \file list.c
 * \brief Maintains doubly-linked lists.
 * \version $Id$
 */

#include "stdinc.h"
#include "list.h"
#include "mempool.h"


static mp_pool_t *dnode_pool;


/* init_dlink_nodes()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - initializes the dnode BlockHeap
 */
void
init_dlink_nodes(void)
{
  dnode_pool = mp_pool_new(sizeof(dlink_node), MP_CHUNK_SIZE_DNODE);
}

/* make_dlink_node()
 *
 * inputs       - NONE
 * output       - pointer to new dlink_node
 * side effects - NONE
 */
dlink_node *
make_dlink_node(void)
{
  dlink_node *ptr = mp_pool_get(dnode_pool);

  memset(ptr, 0, sizeof(*ptr));
  return ptr;
}

/* free_dlink_node()
 *
 * inputs       - pointer to dlink_node
 * output       - NONE
 * side effects - free given dlink_node
 */
void
free_dlink_node(dlink_node *ptr)
{
  mp_pool_release(ptr);
}

/*
 * dlink_ routines are stolen from squid, except for dlinkAddBefore,
 * which is mine.
 *   -- adrian
 */
void
dlinkAdd(void *data, dlink_node *m, dlink_list *list)
{
  m->data = data;
  m->prev = NULL;
  m->next = list->head;

  /* Assumption: If list->tail != NULL, list->head != NULL */
  if (list->head != NULL)
    list->head->prev = m;
  else if (list->tail == NULL)
    list->tail = m;

  list->head = m;
  list->length++;
}

void
dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list)
{
  /* Shortcut - if its the first one, call dlinkAdd only */
  if (b == list->head)
    dlinkAdd(data, m, list);
  else
  {
    m->data = data;
    b->prev->next = m;
    m->prev = b->prev;
    b->prev = m;
    m->next = b;
    list->length++;
  }
}

void
dlinkAddTail(void *data, dlink_node *m, dlink_list *list)
{
  m->data = data;
  m->next = NULL;
  m->prev = list->tail;

  /* Assumption: If list->tail != NULL, list->head != NULL */
  if (list->tail != NULL)
    list->tail->next = m;
  else if (list->head == NULL)
    list->head = m;

  list->tail = m;
  list->length++;
}

/* Execution profiles show that this function is called the most
 * often of all non-spontaneous functions. So it had better be
 * efficient. */
void
dlinkDelete(dlink_node *m, dlink_list *list)
{
  /* Assumption: If m->next == NULL, then list->tail == m
   *      and:   If m->prev == NULL, then list->head == m
   */
  if (m->next)
    m->next->prev = m->prev;
  else
  {
    assert(list->tail == m);
    list->tail = m->prev;
  }

  if (m->prev)
    m->prev->next = m->next;
  else
  {
    assert(list->head == m);
    list->head = m->next;
  }

  /* Set this to NULL does matter */
  m->next = m->prev = NULL;
  list->length--;
}

/*
 * dlinkFind
 * inputs       - list to search
 *              - data
 * output       - pointer to link or NULL if not found
 * side effects - Look for ptr in the linked listed pointed to by link.
 */
dlink_node *
dlinkFind(dlink_list *list, void *data)
{
  dlink_node *ptr;

  DLINK_FOREACH(ptr, list->head)
    if (ptr->data == data)
      return ptr;

  return NULL;
}

void
dlinkMoveList(dlink_list *from, dlink_list *to)
{
  /* There are three cases */
  /* case one, nothing in from list */
  if (from->head == NULL)
    return;

  /* case two, nothing in to list */
  /* actually if to->head is NULL and to->tail isn't, thats a bug */
  if (to->head == NULL)
  {
    to->head = from->head;
    to->tail = from->tail;
    from->head = from->tail = NULL;
    to->length = from->length;
    from->length = 0;
    return;
  }

  /* third case play with the links */
  from->tail->next = to->head;
  from->head->prev = to->head->prev;
  to->head->prev = from->tail;
  to->head = from->head;
  from->head = from->tail = NULL;
  to->length += from->length;
  from->length = 0;
  /* I think I got that right */
}

void
dlink_move_node(dlink_node *m, dlink_list *list_del, dlink_list *list_add)
{
  /* Assumption: If m->next == NULL, then list_del->tail == m
   *      and:   If m->prev == NULL, then list_del->head == m
   */
  if (m->next)
    m->next->prev = m->prev;
  else
  {
    assert(list_del->tail == m);
    list_del->tail = m->prev;
  }

  if (m->prev)
    m->prev->next = m->next;
  else
  {
    assert(list_del->head == m);
    list_del->head = m->next;
  }

  /* Set this to NULL does matter */
  m->prev = NULL;
  m->next = list_add->head;

  /* Assumption: If list_add->tail != NULL, list_add->head != NULL */
  if (list_add->head != NULL)
    list_add->head->prev = m;
  else if (list_add->tail == NULL)
    list_add->tail = m;

  list_add->head = m;
  list_add->length++;
  list_del->length--;
}

dlink_node *
dlinkFindDelete(dlink_list *list, void *data)
{
  dlink_node *m = NULL;

  DLINK_FOREACH(m, list->head)
  {
    if (m->data != data)
      continue;

    if (m->next)
      m->next->prev = m->prev;
    else
    {
      assert(list->tail == m);
      list->tail = m->prev;
    }

    if (m->prev)
      m->prev->next = m->next;
    else
    {
      assert(list->head == m);
      list->head = m->next;
    }

    /* Set this to NULL does matter */
    m->next = m->prev = NULL;
    list->length--;

    return m;
  }

  return NULL;
}
Revision:	2916
Committed:	Sat Jan 25 21:09:18 2014 UTC (11 years, 7 months ago) by michael
Content type:	text/x-csrc
File size:	5919 byte(s)
Log Message:	- Clean up all files in include/ (fixed indentation, removed whitespaces/tabs) - Fixed copyright years
#	Content
1	/*
2	* ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3	*
4	* Copyright (c) 2000-2014 ircd-hybrid development team
5	*
6	* This program is free software; you can redistribute it and/or modify
7	* it under the terms of the GNU General Public License as published by
8	* the Free Software Foundation; either version 2 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with this program; if not, write to the Free Software
18	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
19	* USA
20	*/
21
22	/*! \file list.c
23	* \brief Maintains doubly-linked lists.
24	* \version $Id$
25	*/
26
27	#include "stdinc.h"
28	#include "list.h"
29	#include "mempool.h"
30
31
32	static mp_pool_t *dnode_pool;
33
34
35	/* init_dlink_nodes()
36	*
37	* inputs - NONE
38	* output - NONE
39	* side effects - initializes the dnode BlockHeap
40	*/
41	void
42	init_dlink_nodes(void)
43	{
44	dnode_pool = mp_pool_new(sizeof(dlink_node), MP_CHUNK_SIZE_DNODE);
45	}
46
47	/* make_dlink_node()
48	*
49	* inputs - NONE
50	* output - pointer to new dlink_node
51	* side effects - NONE
52	*/
53	dlink_node *
54	make_dlink_node(void)
55	{
56	dlink_node *ptr = mp_pool_get(dnode_pool);
57
58	memset(ptr, 0, sizeof(*ptr));
59	return ptr;
60	}
61
62	/* free_dlink_node()
63	*
64	* inputs - pointer to dlink_node
65	* output - NONE
66	* side effects - free given dlink_node
67	*/
68	void
69	free_dlink_node(dlink_node *ptr)
70	{
71	mp_pool_release(ptr);
72	}
73
74	/*
75	* dlink_ routines are stolen from squid, except for dlinkAddBefore,
76	* which is mine.
77	* -- adrian
78	*/
79	void
80	dlinkAdd(void data, dlink_node m, dlink_list *list)
81	{
82	m->data = data;
83	m->prev = NULL;
84	m->next = list->head;
85
86	/* Assumption: If list->tail != NULL, list->head != NULL */
87	if (list->head != NULL)
88	list->head->prev = m;
89	else if (list->tail == NULL)
90	list->tail = m;
91
92	list->head = m;
93	list->length++;
94	}
95
96	void
97	dlinkAddBefore(dlink_node b, void data, dlink_node m, dlink_list list)
98	{
99	/* Shortcut - if its the first one, call dlinkAdd only */
100	if (b == list->head)
101	dlinkAdd(data, m, list);
102	else
103	{
104	m->data = data;
105	b->prev->next = m;
106	m->prev = b->prev;
107	b->prev = m;
108	m->next = b;
109	list->length++;
110	}
111	}
112
113	void
114	dlinkAddTail(void data, dlink_node m, dlink_list *list)
115	{
116	m->data = data;
117	m->next = NULL;
118	m->prev = list->tail;
119
120	/* Assumption: If list->tail != NULL, list->head != NULL */
121	if (list->tail != NULL)
122	list->tail->next = m;
123	else if (list->head == NULL)
124	list->head = m;
125
126	list->tail = m;
127	list->length++;
128	}
129
130	/* Execution profiles show that this function is called the most
131	* often of all non-spontaneous functions. So it had better be
132	* efficient. */
133	void
134	dlinkDelete(dlink_node m, dlink_list list)
135	{
136	/* Assumption: If m->next == NULL, then list->tail == m
137	* and: If m->prev == NULL, then list->head == m
138	*/
139	if (m->next)
140	m->next->prev = m->prev;
141	else
142	{
143	assert(list->tail == m);
144	list->tail = m->prev;
145	}
146
147	if (m->prev)
148	m->prev->next = m->next;
149	else
150	{
151	assert(list->head == m);
152	list->head = m->next;
153	}
154
155	/* Set this to NULL does matter */
156	m->next = m->prev = NULL;
157	list->length--;
158	}
159
160	/*
161	* dlinkFind
162	* inputs - list to search
163	* - data
164	* output - pointer to link or NULL if not found
165	* side effects - Look for ptr in the linked listed pointed to by link.
166	*/
167	dlink_node *
168	dlinkFind(dlink_list list, void data)
169	{
170	dlink_node *ptr;
171
172	DLINK_FOREACH(ptr, list->head)
173	if (ptr->data == data)
174	return ptr;
175
176	return NULL;
177	}
178
179	void
180	dlinkMoveList(dlink_list from, dlink_list to)
181	{
182	/* There are three cases */
183	/* case one, nothing in from list */
184	if (from->head == NULL)
185	return;
186
187	/* case two, nothing in to list */
188	/* actually if to->head is NULL and to->tail isn't, thats a bug */
189	if (to->head == NULL)
190	{
191	to->head = from->head;
192	to->tail = from->tail;
193	from->head = from->tail = NULL;
194	to->length = from->length;
195	from->length = 0;
196	return;
197	}
198
199	/* third case play with the links */
200	from->tail->next = to->head;
201	from->head->prev = to->head->prev;
202	to->head->prev = from->tail;
203	to->head = from->head;
204	from->head = from->tail = NULL;
205	to->length += from->length;
206	from->length = 0;
207	/* I think I got that right */
208	}
209
210	void
211	dlink_move_node(dlink_node m, dlink_list list_del, dlink_list *list_add)
212	{
213	/* Assumption: If m->next == NULL, then list_del->tail == m
214	* and: If m->prev == NULL, then list_del->head == m
215	*/
216	if (m->next)
217	m->next->prev = m->prev;
218	else
219	{
220	assert(list_del->tail == m);
221	list_del->tail = m->prev;
222	}
223
224	if (m->prev)
225	m->prev->next = m->next;
226	else
227	{
228	assert(list_del->head == m);
229	list_del->head = m->next;
230	}
231
232	/* Set this to NULL does matter */
233	m->prev = NULL;
234	m->next = list_add->head;
235
236	/* Assumption: If list_add->tail != NULL, list_add->head != NULL */
237	if (list_add->head != NULL)
238	list_add->head->prev = m;
239	else if (list_add->tail == NULL)
240	list_add->tail = m;
241
242	list_add->head = m;
243	list_add->length++;
244	list_del->length--;
245	}
246
247	dlink_node *
248	dlinkFindDelete(dlink_list list, void data)
249	{
250	dlink_node *m = NULL;
251
252	DLINK_FOREACH(m, list->head)
253	{
254	if (m->data != data)
255	continue;
256
257	if (m->next)
258	m->next->prev = m->prev;
259	else
260	{
261	assert(list->tail == m);
262	list->tail = m->prev;
263	}
264
265	if (m->prev)
266	m->prev->next = m->next;
267	else
268	{
269	assert(list->head == m);
270	list->head = m->next;
271	}
272
273	/* Set this to NULL does matter */
274	m->next = m->prev = NULL;
275	list->length--;
276
277	return m;
278	}
279
280	return NULL;
281	}