ermyth/src/dlink.C

/*
 * dlink.C: Linked lists.
 * Rights to this code are documented in doc/LICENSE.
 *
 * Copyright © 2005-2007 Atheme Project (http://www.atheme.org)           
 */

static char const rcsid[] = "$Id";

#include "atheme.h"
#include "internal.h"

static BlockHeap *node_heap;

void
init_dlink_nodes (void)
{
  node_heap = BlockHeapCreate (sizeof (node_t), HEAP_NODE);

  if (!node_heap)
    {
      slog (LG_INFO, "init_dlink_nodes(): block allocator failure.");
      exit (EXIT_FAILURE);
    }
}

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

  /* allocate it */
  n = static_cast<node_t *> (BlockHeapAlloc (node_heap));

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

  /* up the count */
  claro_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 */
  BlockHeapFree (node_heap, n);

  /* down the count */
  claro_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.1
Committed:	Thu Jul 19 08:24:57 2007 UTC (16 years, 10 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
Log Message:	initial import. the most important changes since Atheme are: - fixed many memory leaks - fixed many bugs - converted to C++ and use more STL containers - added a (not very enhanced yet) perl module - greatly improved XML-RPC speed - added a JSON-RPC module with code from json-cpp - added a valgrind memcheck module to operserv - added a more object oriented base64 implementation - added a specialised unit test framework - improved stability - use gettimeofday() if available - reworked adding/removing commands - MemoServ IGNORE DEL can now remove indices
#	User	Rev	Content
1	pippijn	1.1	/*
2			* dlink.C: Linked lists.
3			* Rights to this code are documented in doc/LICENSE.
4			*
5			* Copyright © 2005-2007 Atheme Project (http://www.atheme.org)
6			*/
7
8			static char const rcsid[] = "$Id";
9
10			#include "atheme.h"
11			#include "internal.h"
12
13			static BlockHeap *node_heap;
14
15			void
16			init_dlink_nodes (void)
17			{
18			node_heap = BlockHeapCreate (sizeof (node_t), HEAP_NODE);
19
20			if (!node_heap)
21			{
22			slog (LG_INFO, "init_dlink_nodes(): block allocator failure.");
23			exit (EXIT_FAILURE);
24			}
25			}
26
27			/* creates a new node */
28			node_t *
29			node_create (void)
30			{
31			node_t *n;
32
33			/* allocate it */
34			n = static_cast<node_t *> (BlockHeapAlloc (node_heap));
35
36			/* initialize */
37			n->data = n->next = n->prev = NULL;
38
39			/* up the count */
40			claro_state.node++;
41
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			BlockHeapFree (node_heap, n);
54
55			/* down the count */
56			claro_state.node--;
57			}
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			LIST_FOREACH (n, l->head) if (n->data == data)
176			return n;
177
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			*/