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.4 2007-08-28 17:08:12 pippijn Exp $";

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