trunk/src/list.c

/*
 *  ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
 *  list.c: Various assorted functions for various structures.
 *
 *  Copyright (C) 2002 by the past and present ircd coders, and others.
 *
 *  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
 *
 *  $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;

  DLINK_FOREACH(m, list->head)
  {
    if (m->data == data)
    {
      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:	1654
Committed:	Fri Nov 16 19:39:37 2012 UTC (12 years, 9 months ago) by michael
Content type:	text/x-csrc
File size:	5940 byte(s)
Log Message:	- Implemented memory pool allocator which basically is taken from Tor's mempool allocator for Tor cells - Fixed compile warnings in conf_class.c - ./configure --enable-assert works again
#	User	Rev	Content
1	adx	30	/*
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	knight	31	* $Id$
23	adx	30	*/
24
25			#include "stdinc.h"
26			#include "list.h"
27	michael	1654	#include "mempool.h"
28	adx	30
29	michael	1654	static mp_pool_t *dnode_pool;
30	adx	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	michael	1654	dnode_pool = mp_pool_new(sizeof(dlink_node), MP_CHUNK_SIZE_DNODE);
42	adx	30	}
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	michael	1654	dlink_node *ptr = mp_pool_get(dnode_pool);
54	adx	30
55	michael	1654	memset(ptr, 0, sizeof(*ptr));
56			return ptr;
57	adx	30	}
58
59			/* free_dlink_node()
60			*
61			* inputs - pointer to dlink_node
62			* output - NONE
63			* side effects - free given dlink_node
64			*/
65			void
66			free_dlink_node(dlink_node *ptr)
67			{
68	michael	1654	mp_pool_release(ptr);
69	adx	30	}
70	michael	1011
71			/*
72			* dlink_ routines are stolen from squid, except for dlinkAddBefore,
73			* which is mine.
74			* -- adrian
75			*/
76			void
77			dlinkAdd(void data, dlink_node m, dlink_list *list)
78			{
79			m->data = data;
80			m->prev = NULL;
81			m->next = list->head;
82
83			/* Assumption: If list->tail != NULL, list->head != NULL */
84			if (list->head != NULL)
85			list->head->prev = m;
86			else if (list->tail == NULL)
87			list->tail = m;
88
89			list->head = m;
90			list->length++;
91			}
92
93			void
94			dlinkAddBefore(dlink_node b, void data, dlink_node m, dlink_list list)
95			{
96			/* Shortcut - if its the first one, call dlinkAdd only */
97			if (b == list->head)
98			dlinkAdd(data, m, list);
99			else
100			{
101			m->data = data;
102			b->prev->next = m;
103			m->prev = b->prev;
104			b->prev = m;
105			m->next = b;
106			list->length++;
107			}
108			}
109
110			void
111			dlinkAddTail(void data, dlink_node m, dlink_list *list)
112			{
113			m->data = data;
114			m->next = NULL;
115			m->prev = list->tail;
116
117			/* Assumption: If list->tail != NULL, list->head != NULL */
118			if (list->tail != NULL)
119			list->tail->next = m;
120			else if (list->head == NULL)
121			list->head = m;
122
123			list->tail = m;
124			list->length++;
125			}
126
127			/* Execution profiles show that this function is called the most
128			* often of all non-spontaneous functions. So it had better be
129			* efficient. */
130			void
131			dlinkDelete(dlink_node m, dlink_list list)
132			{
133			/* Assumption: If m->next == NULL, then list->tail == m
134			* and: If m->prev == NULL, then list->head == m
135			*/
136			if (m->next)
137			m->next->prev = m->prev;
138			else
139			{
140			assert(list->tail == m);
141			list->tail = m->prev;
142			}
143
144			if (m->prev)
145			m->prev->next = m->next;
146			else
147			{
148			assert(list->head == m);
149			list->head = m->next;
150			}
151
152			/* Set this to NULL does matter */
153			m->next = m->prev = NULL;
154			list->length--;
155			}
156
157			/*
158			* dlinkFind
159			* inputs - list to search
160			* - data
161			* output - pointer to link or NULL if not found
162			* side effects - Look for ptr in the linked listed pointed to by link.
163			*/
164			dlink_node *
165			dlinkFind(dlink_list list, void data)
166			{
167			dlink_node *ptr;
168
169			DLINK_FOREACH(ptr, list->head)
170			if (ptr->data == data)
171			return ptr;
172
173			return NULL;
174			}
175
176			void
177			dlinkMoveList(dlink_list from, dlink_list to)
178			{
179			/* There are three cases */
180			/* case one, nothing in from list */
181			if (from->head == NULL)
182			return;
183
184			/* case two, nothing in to list */
185			/* actually if to->head is NULL and to->tail isn't, thats a bug */
186			if (to->head == NULL)
187			{
188			to->head = from->head;
189			to->tail = from->tail;
190			from->head = from->tail = NULL;
191			to->length = from->length;
192			from->length = 0;
193			return;
194			}
195
196			/* third case play with the links */
197			from->tail->next = to->head;
198			from->head->prev = to->head->prev;
199			to->head->prev = from->tail;
200			to->head = from->head;
201			from->head = from->tail = NULL;
202			to->length += from->length;
203			from->length = 0;
204			/* I think I got that right */
205			}
206
207	michael	1126	void
208			dlink_move_node(dlink_node m, dlink_list list_del, dlink_list *list_add)
209			{
210			/* Assumption: If m->next == NULL, then list_del->tail == m
211			* and: If m->prev == NULL, then list_del->head == m
212			*/
213			if (m->next)
214			m->next->prev = m->prev;
215			else
216			{
217	michael	1654	assert(list_del->tail == m);
218	michael	1126	list_del->tail = m->prev;
219			}
220
221			if (m->prev)
222			m->prev->next = m->next;
223			else
224			{
225	michael	1654	assert(list_del->head == m);
226	michael	1126	list_del->head = m->next;
227			}
228
229			/* Set this to NULL does matter */
230			m->prev = NULL;
231			m->next = list_add->head;
232
233			/* Assumption: If list_add->tail != NULL, list_add->head != NULL */
234			if (list_add->head != NULL)
235			list_add->head->prev = m;
236			else if (list_add->tail == NULL)
237			list_add->tail = m;
238
239			list_add->head = m;
240			list_add->length++;
241			list_del->length--;
242			}
243
244	michael	1011	dlink_node *
245			dlinkFindDelete(dlink_list list, void data)
246			{
247			dlink_node *m;
248
249			DLINK_FOREACH(m, list->head)
250			{
251			if (m->data == data)
252			{
253			if (m->next)
254			m->next->prev = m->prev;
255			else
256			{
257			assert(list->tail == m);
258			list->tail = m->prev;
259			}
260			if (m->prev)
261			m->prev->next = m->next;
262			else
263			{
264			assert(list->head == m);
265			list->head = m->next;
266			}
267			/* Set this to NULL does matter */
268			m->next = m->prev = NULL;
269			list->length--;
270
271			return m;
272			}
273			}
274
275			return NULL;
276			}
277
278