trunk/src/list.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 2000-2018 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  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 *node = mp_pool_get(dnode_pool);

  return node;
}

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

/*
 * 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)
    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 it's 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)
    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->data = NULL;
  m->next = NULL;
  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, const void *data)
{
  dlink_node *node;

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

  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, that's 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)
    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;

  DLINK_FOREACH(m, list->head)
  {
    if (m->data == data)
    {
      dlinkDelete(m, list);
      return m;
    }
  }

  return NULL;
}
Revision:	8290
Committed:	Sun Feb 25 09:34:06 2018 UTC (8 years, 5 months ago) by michael
Content type:	text/x-csrc
File size:	5580 byte(s)
Log Message:	- list.c:dlinkDelete(): reset m->data as well
#	User	Rev	Content
1	adx	30	/*
2	michael	2916	* ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3	adx	30	*
4	michael	8279	* Copyright (c) 2000-2018 ircd-hybrid development team
5	adx	30	*
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	michael	4565	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
19	adx	30	* USA
20			*/
21
22	michael	2916	/*! \file list.c
23			* \brief Maintains doubly-linked lists.
24			* \version $Id$
25			*/
26
27	adx	30	#include "stdinc.h"
28			#include "list.h"
29	michael	1654	#include "mempool.h"
30	adx	30
31	michael	2916
32	michael	1654	static mp_pool_t *dnode_pool;
33	adx	30
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	michael	1654	dnode_pool = mp_pool_new(sizeof(dlink_node), MP_CHUNK_SIZE_DNODE);
45	adx	30	}
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	michael	4815	dlink_node *node = mp_pool_get(dnode_pool);
57	adx	30
58	michael	4815	return node;
59	adx	30	}
60
61			/* free_dlink_node()
62			*
63			* inputs - pointer to dlink_node
64			* output - NONE
65	michael	2916	* side effects - free given dlink_node
66	adx	30	*/
67			void
68	michael	4815	free_dlink_node(dlink_node *node)
69	adx	30	{
70	michael	4815	mp_pool_release(node);
71	adx	30	}
72	michael	1011
73			/*
74			* dlink_ routines are stolen from squid, except for dlinkAddBefore,
75			* which is mine.
76			* -- adrian
77			*/
78			void
79			dlinkAdd(void data, dlink_node m, dlink_list *list)
80			{
81			m->data = data;
82			m->prev = NULL;
83			m->next = list->head;
84
85			/* Assumption: If list->tail != NULL, list->head != NULL */
86	michael	3335	if (list->head)
87	michael	1011	list->head->prev = m;
88			else if (list->tail == NULL)
89			list->tail = m;
90
91			list->head = m;
92			list->length++;
93			}
94
95			void
96			dlinkAddBefore(dlink_node b, void data, dlink_node m, dlink_list list)
97			{
98	michael	7634	/* Shortcut - if it's the first one, call dlinkAdd only */
99	michael	1011	if (b == list->head)
100			dlinkAdd(data, m, list);
101			else
102			{
103			m->data = data;
104			b->prev->next = m;
105			m->prev = b->prev;
106			b->prev = m;
107			m->next = b;
108			list->length++;
109			}
110			}
111
112			void
113			dlinkAddTail(void data, dlink_node m, dlink_list *list)
114			{
115			m->data = data;
116			m->next = NULL;
117			m->prev = list->tail;
118
119			/* Assumption: If list->tail != NULL, list->head != NULL */
120	michael	3335	if (list->tail)
121	michael	1011	list->tail->next = m;
122			else if (list->head == NULL)
123			list->head = m;
124
125			list->tail = m;
126			list->length++;
127			}
128
129			/* Execution profiles show that this function is called the most
130			* often of all non-spontaneous functions. So it had better be
131			* efficient. */
132			void
133			dlinkDelete(dlink_node m, dlink_list list)
134			{
135			/* Assumption: If m->next == NULL, then list->tail == m
136			* and: If m->prev == NULL, then list->head == m
137			*/
138			if (m->next)
139			m->next->prev = m->prev;
140			else
141			{
142			assert(list->tail == m);
143			list->tail = m->prev;
144			}
145
146			if (m->prev)
147			m->prev->next = m->next;
148			else
149			{
150			assert(list->head == m);
151			list->head = m->next;
152			}
153
154			/* Set this to NULL does matter */
155	michael	8290	m->data = NULL;
156			m->next = NULL;
157			m->prev = NULL;
158
159	michael	1011	list->length--;
160			}
161
162			/*
163			* dlinkFind
164			* inputs - list to search
165			* - data
166			* output - pointer to link or NULL if not found
167			* side effects - Look for ptr in the linked listed pointed to by link.
168			*/
169			dlink_node *
170	michael	4785	dlinkFind(dlink_list list, const void data)
171	michael	1011	{
172	michael	8059	dlink_node *node;
173	michael	1011
174	michael	4815	DLINK_FOREACH(node, list->head)
175			if (node->data == data)
176			return node;
177	michael	1011
178			return NULL;
179			}
180
181			void
182			dlinkMoveList(dlink_list from, dlink_list to)
183			{
184			/* There are three cases */
185			/* case one, nothing in from list */
186			if (from->head == NULL)
187			return;
188
189			/* case two, nothing in to list */
190	michael	7634	/* actually if to->head is NULL and to->tail isn't, that's a bug */
191	michael	1011	if (to->head == NULL)
192			{
193			to->head = from->head;
194			to->tail = from->tail;
195			from->head = from->tail = NULL;
196			to->length = from->length;
197			from->length = 0;
198			return;
199			}
200
201			/* third case play with the links */
202			from->tail->next = to->head;
203			from->head->prev = to->head->prev;
204			to->head->prev = from->tail;
205			to->head = from->head;
206			from->head = from->tail = NULL;
207			to->length += from->length;
208			from->length = 0;
209			/* I think I got that right */
210			}
211
212	michael	1126	void
213			dlink_move_node(dlink_node m, dlink_list list_del, dlink_list *list_add)
214			{
215			/* Assumption: If m->next == NULL, then list_del->tail == m
216			* and: If m->prev == NULL, then list_del->head == m
217			*/
218			if (m->next)
219			m->next->prev = m->prev;
220			else
221			{
222	michael	1654	assert(list_del->tail == m);
223	michael	1126	list_del->tail = m->prev;
224			}
225
226			if (m->prev)
227			m->prev->next = m->next;
228			else
229			{
230	michael	1654	assert(list_del->head == m);
231	michael	1126	list_del->head = m->next;
232			}
233
234			/* Set this to NULL does matter */
235			m->prev = NULL;
236			m->next = list_add->head;
237
238			/* Assumption: If list_add->tail != NULL, list_add->head != NULL */
239	michael	5003	if (list_add->head)
240	michael	1126	list_add->head->prev = m;
241			else if (list_add->tail == NULL)
242			list_add->tail = m;
243
244			list_add->head = m;
245			list_add->length++;
246			list_del->length--;
247			}
248
249	michael	1011	dlink_node *
250			dlinkFindDelete(dlink_list list, void data)
251			{
252	michael	8059	dlink_node *m;
253	michael	1011
254			DLINK_FOREACH(m, list->head)
255			{
256	michael	7391	if (m->data == data)
257	michael	1011	{
258	michael	7391	dlinkDelete(m, list);
259			return m;
260	michael	2714	}
261	michael	1011	}
262
263			return NULL;
264			}