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 "memory.h"


/* make_dlink_node()
 *
 * inputs       - NONE
 * output       - pointer to new dlink_node
 * side effects - NONE
 */
dlink_node *
make_dlink_node(void)
{
  dlink_node *node = xcalloc(sizeof(*node));

  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)
{
  xfree(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)
{
  assert(list->length > 0);

  /* 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:	8385
Committed:	Fri Mar 16 20:09:55 2018 UTC (7 years, 5 months ago) by michael
Content type:	text/x-csrc
File size:	5338 byte(s)
Log Message:	- Rip out mempool
#	Content
1	/*
2	* ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3	*
4	* Copyright (c) 2000-2018 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
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 "memory.h"
30
31
32	/* make_dlink_node()
33	*
34	* inputs - NONE
35	* output - pointer to new dlink_node
36	* side effects - NONE
37	*/
38	dlink_node *
39	make_dlink_node(void)
40	{
41	dlink_node node = xcalloc(sizeof(node));
42
43	return node;
44	}
45
46	/* free_dlink_node()
47	*
48	* inputs - pointer to dlink_node
49	* output - NONE
50	* side effects - free given dlink_node
51	*/
52	void
53	free_dlink_node(dlink_node *node)
54	{
55	xfree(node);
56	}
57
58	/*
59	* dlink_ routines are stolen from squid, except for dlinkAddBefore,
60	* which is mine.
61	* -- adrian
62	*/
63	void
64	dlinkAdd(void data, dlink_node m, dlink_list *list)
65	{
66	m->data = data;
67	m->prev = NULL;
68	m->next = list->head;
69
70	/* Assumption: If list->tail != NULL, list->head != NULL */
71	if (list->head)
72	list->head->prev = m;
73	else if (list->tail == NULL)
74	list->tail = m;
75
76	list->head = m;
77	list->length++;
78	}
79
80	void
81	dlinkAddBefore(dlink_node b, void data, dlink_node m, dlink_list list)
82	{
83	/* Shortcut - if it's the first one, call dlinkAdd only */
84	if (b == list->head)
85	dlinkAdd(data, m, list);
86	else
87	{
88	m->data = data;
89	b->prev->next = m;
90	m->prev = b->prev;
91	b->prev = m;
92	m->next = b;
93	list->length++;
94	}
95	}
96
97	void
98	dlinkAddTail(void data, dlink_node m, dlink_list *list)
99	{
100	m->data = data;
101	m->next = NULL;
102	m->prev = list->tail;
103
104	/* Assumption: If list->tail != NULL, list->head != NULL */
105	if (list->tail)
106	list->tail->next = m;
107	else if (list->head == NULL)
108	list->head = m;
109
110	list->tail = m;
111	list->length++;
112	}
113
114	/* Execution profiles show that this function is called the most
115	* often of all non-spontaneous functions. So it had better be
116	* efficient. */
117	void
118	dlinkDelete(dlink_node m, dlink_list list)
119	{
120	assert(list->length > 0);
121
122	/* Assumption: If m->next == NULL, then list->tail == m
123	* and: If m->prev == NULL, then list->head == m
124	*/
125	if (m->next)
126	m->next->prev = m->prev;
127	else
128	{
129	assert(list->tail == m);
130	list->tail = m->prev;
131	}
132
133	if (m->prev)
134	m->prev->next = m->next;
135	else
136	{
137	assert(list->head == m);
138	list->head = m->next;
139	}
140
141	/* Set this to NULL does matter */
142	m->data = NULL;
143	m->next = NULL;
144	m->prev = NULL;
145
146	list->length--;
147	}
148
149	/*
150	* dlinkFind
151	* inputs - list to search
152	* - data
153	* output - pointer to link or NULL if not found
154	* side effects - Look for ptr in the linked listed pointed to by link.
155	*/
156	dlink_node *
157	dlinkFind(dlink_list list, const void data)
158	{
159	dlink_node *node;
160
161	DLINK_FOREACH(node, list->head)
162	if (node->data == data)
163	return node;
164
165	return NULL;
166	}
167
168	void
169	dlinkMoveList(dlink_list from, dlink_list to)
170	{
171	/* There are three cases */
172	/* case one, nothing in from list */
173	if (from->head == NULL)
174	return;
175
176	/* case two, nothing in to list */
177	/* actually if to->head is NULL and to->tail isn't, that's a bug */
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	from->tail->next = to->head;
190	from->head->prev = to->head->prev;
191	to->head->prev = from->tail;
192	to->head = from->head;
193	from->head = from->tail = NULL;
194	to->length += from->length;
195	from->length = 0;
196	/* I think I got that right */
197	}
198
199	void
200	dlink_move_node(dlink_node m, dlink_list list_del, dlink_list *list_add)
201	{
202	/* Assumption: If m->next == NULL, then list_del->tail == m
203	* and: If m->prev == NULL, then list_del->head == m
204	*/
205	if (m->next)
206	m->next->prev = m->prev;
207	else
208	{
209	assert(list_del->tail == m);
210	list_del->tail = m->prev;
211	}
212
213	if (m->prev)
214	m->prev->next = m->next;
215	else
216	{
217	assert(list_del->head == m);
218	list_del->head = m->next;
219	}
220
221	/* Set this to NULL does matter */
222	m->prev = NULL;
223	m->next = list_add->head;
224
225	/* Assumption: If list_add->tail != NULL, list_add->head != NULL */
226	if (list_add->head)
227	list_add->head->prev = m;
228	else if (list_add->tail == NULL)
229	list_add->tail = m;
230
231	list_add->head = m;
232	list_add->length++;
233	list_del->length--;
234	}
235
236	dlink_node *
237	dlinkFindDelete(dlink_list list, void data)
238	{
239	dlink_node *m;
240
241	DLINK_FOREACH(m, list->head)
242	{
243	if (m->data == data)
244	{
245	dlinkDelete(m, list);
246	return m;
247	}
248	}
249
250	return NULL;
251	}