ircd-hybrid-7.2/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 "balloc.h"

static BlockHeap *dnode_heap;


/* init_dlink_nodes()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - initializes the dnode BlockHeap
 */
void
init_dlink_nodes(void)
{
  dnode_heap = BlockHeapCreate("dlink node", sizeof(dlink_node), DNODE_HEAP_SIZE);
}

/* make_dlink_node()
 *
 * inputs       - NONE
 * output       - pointer to new dlink_node
 * side effects - NONE
 */
dlink_node *
make_dlink_node(void)
{
  dlink_node *lp = BlockHeapAlloc(dnode_heap);

  return lp;
}

/* free_dlink_node()
 *
 * inputs       - pointer to dlink_node
 * output       - NONE
 * side effects - free given dlink_node 
 */
void
free_dlink_node(dlink_node *ptr)
{
  BlockHeapFree(dnode_heap, 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 */
}

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;
}


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