ermyth/src/dlink.C

/*
 * dlink.C: Linked lists.
 *
 * Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
 * Rights to this code are as documented in COPYING.
 *
 *
 * Portions of this file were derived from sources bearing the following license:
 * Rights to this code are documented in doc/pod/license.pod.
 * Copyright © 2005-2007 Atheme Project (http://www.atheme.org)           
 */

static char const rcsid[] = "$Id: dlink.C,v 1.5 2007-09-16 18:54:44 pippijn Exp $";

#include "atheme.h"
#include <ermyth/system.h>
#include "internal.h"

void
init_dlink_nodes (void)
{
#if 0
  node_heap = BlockHeapCreate (sizeof (node_t), HEAP_NODE);
#endif
}

/* creates a new node */
node_t *
node_create (void)
{
  node_t *n;

  /* allocate it */
  n = new node_t;

  /* initialize */
  n->data = n->next = n->prev = NULL;

  /* up the count */
  system_state.node++;

  /* return a pointer to the new node */
  return n;
}

/* frees a node */
void
node_free (node_t *n)
{
  return_if_fail (n != NULL);

  /* free it */
  delete n;

  /* down the count */
  system_state.node--;
}

/* adds a node to the end of a list */
void
node_add (void *data, node_t *n, list_t *l)
{
  node_t *tn;

  return_if_fail (n != NULL);
  return_if_fail (l != NULL);

  n->next = n->prev = NULL;
  n->data = data;

  /* first node? */
  if (!l->head)
    {
      l->head = n;
      l->tail = n;
      l->count++;
      return;
    }

  /* Speed increase. */
  tn = l->tail;

  /* set the our `prev' to the last node */
  n->prev = tn;

  /* set the last node's `next' to us */
  n->prev->next = n;

  /* set the list's `tail' to us */
  l->tail = n;

  /* up the count */
  l->count++;
}

/* adds a node to the head of a list */
void
node_add_head (void *data, node_t *n, list_t *l)
{
  node_t *tn;

  return_if_fail (n != NULL);
  return_if_fail (l != NULL);

  n->next = n->prev = NULL;
  n->data = data;

  /* first node? */
  if (!l->head)
    {
      l->head = n;
      l->tail = n;
      l->count++;
      return;
    }

  tn = l->head;
  n->next = tn;
  tn->prev = n;
  l->head = n;
  l->count++;
}

/* adds a node to a list before another node, or to the end */
void
node_add_before (void *data, node_t *n, list_t *l, node_t *before)
{
  return_if_fail (n != NULL);
  return_if_fail (l != NULL);

  if (before == NULL)
    node_add (data, n, l);
  else if (before == l->head)
    node_add_head (data, n, l);
  else
    {
      n->data = data;
      n->prev = before->prev;
      n->next = before;
      before->prev = n;
      l->count++;
    }
}

void
node_del (node_t *n, list_t *l)
{
  return_if_fail (n != NULL);
  return_if_fail (l != NULL);

  /* are we the head? */
  if (!n->prev)
    l->head = n->next;
  else
    n->prev->next = n->next;

  /* are we the tail? */
  if (!n->next)
    l->tail = n->prev;
  else
    n->next->prev = n->prev;

  /* down the count */
  l->count--;
}

/* finds a node by `data' */
node_t *
node_find (void *data, list_t *l)
{
  node_t *n;

  return_val_if_fail (l != NULL, NULL);

  LIST_FOREACH (n, l->head)
    if (n->data == data)
      return n;

  return NULL;
}

void
node_move (node_t *m, list_t *oldlist, list_t *newlist)
{
  return_if_fail (m != NULL);
  return_if_fail (oldlist != NULL);
  return_if_fail (newlist != NULL);

  /* 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
    oldlist->tail = m->prev;

  if (m->prev)
    m->prev->next = m->next;
  else
    oldlist->head = m->next;

  m->prev = NULL;
  m->next = newlist->head;
  if (newlist->head != NULL)
    newlist->head->prev = m;
  else if (newlist->tail == NULL)
    newlist->tail = m;
  newlist->head = m;

  oldlist->count--;
  newlist->count++;
}

/* vim:cinoptions=>s,e0,n0,f0,{0,}0,^0,=s,ps,t0,c3,+s,(2s,us,)20,*30,gs,hs
 * vim:ts=8
 * vim:sw=8
 * vim:noexpandtab
 */
Revision:	1.6
Committed:	Sat Sep 22 14:27:30 2007 UTC (16 years, 8 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.5:	+2 -1 lines
Log Message:	split up ermyth into ermyth-modules, libermyth (currently just ermyth-util) and ermyth-core
#	User	Rev	Content
1	pippijn	1.1	/*
2			* dlink.C: Linked lists.
3	pippijn	1.5	*
4			* Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
5			* Rights to this code are as documented in COPYING.
6			*
7			*
8			* Portions of this file were derived from sources bearing the following license:
9	pippijn	1.2	* Rights to this code are documented in doc/pod/license.pod.
10	pippijn	1.4	* Copyright © 2005-2007 Atheme Project (http://www.atheme.org)
11	pippijn	1.1	*/
12
13	pippijn	1.6	static char const rcsid[] = "$Id: dlink.C,v 1.5 2007-09-16 18:54:44 pippijn Exp $";
14	pippijn	1.1
15			#include "atheme.h"
16	pippijn	1.6	#include <ermyth/system.h>
17	pippijn	1.1	#include "internal.h"
18
19			void
20			init_dlink_nodes (void)
21			{
22	pippijn	1.4	#if 0
23	pippijn	1.1	node_heap = BlockHeapCreate (sizeof (node_t), HEAP_NODE);
24	pippijn	1.4	#endif
25	pippijn	1.1	}
26
27			/* creates a new node */
28			node_t *
29			node_create (void)
30			{
31			node_t *n;
32
33			/* allocate it */
34	pippijn	1.4	n = new node_t;
35	pippijn	1.1
36			/* initialize */
37			n->data = n->next = n->prev = NULL;
38
39			/* up the count */
40	pippijn	1.4	system_state.node++;
41	pippijn	1.1
42			/* return a pointer to the new node */
43			return n;
44			}
45
46			/* frees a node */
47			void
48			node_free (node_t *n)
49			{
50			return_if_fail (n != NULL);
51
52			/* free it */
53	pippijn	1.4	delete n;
54	pippijn	1.1
55			/* down the count */
56	pippijn	1.4	system_state.node--;
57	pippijn	1.1	}
58
59			/* adds a node to the end of a list */
60			void
61			node_add (void data, node_t n, list_t *l)
62			{
63			node_t *tn;
64
65			return_if_fail (n != NULL);
66			return_if_fail (l != NULL);
67
68			n->next = n->prev = NULL;
69			n->data = data;
70
71			/* first node? */
72			if (!l->head)
73			{
74			l->head = n;
75			l->tail = n;
76			l->count++;
77			return;
78			}
79
80			/* Speed increase. */
81			tn = l->tail;
82
83			/* set the our `prev' to the last node */
84			n->prev = tn;
85
86			/* set the last node's `next' to us */
87			n->prev->next = n;
88
89			/* set the list's `tail' to us */
90			l->tail = n;
91
92			/* up the count */
93			l->count++;
94			}
95
96			/* adds a node to the head of a list */
97			void
98			node_add_head (void data, node_t n, list_t *l)
99			{
100			node_t *tn;
101
102			return_if_fail (n != NULL);
103			return_if_fail (l != NULL);
104
105			n->next = n->prev = NULL;
106			n->data = data;
107
108			/* first node? */
109			if (!l->head)
110			{
111			l->head = n;
112			l->tail = n;
113			l->count++;
114			return;
115			}
116
117			tn = l->head;
118			n->next = tn;
119			tn->prev = n;
120			l->head = n;
121			l->count++;
122			}
123
124			/* adds a node to a list before another node, or to the end */
125			void
126			node_add_before (void data, node_t n, list_t l, node_t before)
127			{
128			return_if_fail (n != NULL);
129			return_if_fail (l != NULL);
130
131			if (before == NULL)
132			node_add (data, n, l);
133			else if (before == l->head)
134			node_add_head (data, n, l);
135			else
136			{
137			n->data = data;
138			n->prev = before->prev;
139			n->next = before;
140			before->prev = n;
141			l->count++;
142			}
143			}
144
145			void
146			node_del (node_t n, list_t l)
147			{
148			return_if_fail (n != NULL);
149			return_if_fail (l != NULL);
150
151			/* are we the head? */
152			if (!n->prev)
153			l->head = n->next;
154			else
155			n->prev->next = n->next;
156
157			/* are we the tail? */
158			if (!n->next)
159			l->tail = n->prev;
160			else
161			n->next->prev = n->prev;
162
163			/* down the count */
164			l->count--;
165			}
166
167			/* finds a node by `data' */
168			node_t *
169			node_find (void data, list_t l)
170			{
171			node_t *n;
172
173			return_val_if_fail (l != NULL, NULL);
174
175	pippijn	1.4	LIST_FOREACH (n, l->head)
176			if (n->data == data)
177			return n;
178	pippijn	1.1
179			return NULL;
180			}
181
182			void
183			node_move (node_t m, list_t oldlist, list_t *newlist)
184			{
185			return_if_fail (m != NULL);
186			return_if_fail (oldlist != NULL);
187			return_if_fail (newlist != NULL);
188
189			/* Assumption: If m->next == NULL, then list->tail == m
190			* and: If m->prev == NULL, then list->head == m
191			*/
192			if (m->next)
193			m->next->prev = m->prev;
194			else
195			oldlist->tail = m->prev;
196
197			if (m->prev)
198			m->prev->next = m->next;
199			else
200			oldlist->head = m->next;
201
202			m->prev = NULL;
203			m->next = newlist->head;
204			if (newlist->head != NULL)
205			newlist->head->prev = m;
206			else if (newlist->tail == NULL)
207			newlist->tail = m;
208			newlist->head = m;
209
210			oldlist->count--;
211			newlist->count++;
212			}
213
214			/* vim:cinoptions=>s,e0,n0,f0,{0,}0,^0,=s,ps,t0,c3,+s,(2s,us,)20,*30,gs,hs
215			* vim:ts=8
216			* vim:sw=8
217			* vim:noexpandtab
218			*/