[thirdparty/systemd.git] / libsysfs / dlist.c

/*
 * dlist.c
 *
 * Copyright (C) 2003 Eric J Bohm
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021110307 USA
 *
 */


/* Double linked list implementation.

 * You allocate the data and give dlist the pointer.
 * If your data is complex set the dlist->del_func to a an appropriate
 * delete function.  Otherwise dlist will just use free.

*/
#include <stdlib.h>
#include "dlist.h"

/*
 * Return pointer to node at marker.
 * else null if no nodes.
 */

inline void *dlist_mark(Dlist *list)
{
  if(list->marker!=NULL)
    return(list->marker->data);
  else
    return(NULL);
}

/* 
 * Set marker to start.
 */

inline void dlist_start(Dlist *list)
{
  list->marker=list->head;
}

/* 
 * Set marker to end.
 */

inline void dlist_end(Dlist *list)
{
  list->marker=list->head;
}

/* internal use function
 * quickie inline to consolidate the marker movement logic
 * in one place
 *
 * when direction true it moves marker after 
 * when direction false it moves marker before.
 * return pointer to data at new marker
 * if nowhere to move the marker in desired direction return null 
 */
inline void *_dlist_mark_move(Dlist *list,int direction)
{
  if(direction)
    {
      if( list->marker->next!=NULL)
	list->marker=list->marker->next;
      else
	return(NULL);
    }
  else
    {
      if( list->marker->prev!=NULL)
	list->marker=list->marker->prev;
      else
	return(NULL);
    }
  if(list->marker!=list->head)
    return(list->marker->data);
  else
    return(NULL);
}

/*
 * Create new linked list to store nodes of datasize.
 * return null if list cannot be created.
 */
Dlist *dlist_new(size_t datasize)
{
  Dlist *list=NULL;
  if((list=malloc(sizeof(Dlist))))
    {
      list->marker=NULL;
      list->count=0L;
      list->data_size=datasize;
      list->del_func=free;
      list->head=&(list->headnode);
      list->head->prev=NULL;
      list->head->next=NULL;
      list->head->data=NULL;
    }
  return(list);
}

/*
 * Create new linked list to store nodes of datasize set list
 * data node delete function to the passed in del_func
 * return null if list cannot be created.
 */
Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*))
{
  Dlist *list=NULL;
  list=dlist_new(datasize);
  if(list!=NULL)
    list->del_func=del_func;
  return(list);
}


/*
 * remove marker node from list
 * call data_delete function on data if registered.
 * otherwise call free.
 * when direction true it moves marker after 
 * when direction false it moves marker before.
 * free marker node
 * return nothing.
 */
void dlist_delete(Dlist *list,int direction)
{
  if((list->marker != list->head)&&(list->marker!=NULL)) 
    {
      DL_node *corpse;
      corpse=list->marker;
      _dlist_mark_move(list,direction);
      if(list->head->next==corpse)
	list->head->next=corpse->next;
      if(list->head->prev==corpse)
	list->head->prev=corpse->prev;
      if(corpse->prev!=NULL) //should be impossible
	corpse->prev->next=corpse->next;
      if(corpse->next!=NULL) //should be impossible
	corpse->next->prev=corpse->prev;
      list->del_func(corpse->data);
      list->count--;
      free(corpse);
    }
}

/*
 * Insert node containing data at marker.
 * If direction true it inserts after.
 * If direction false it inserts before.
 * move marker to inserted node
 * return pointer to inserted node
 */
void *dlist_insert(Dlist *list,void *data,int direction)
{
  DL_node *new_node=NULL;
  if(list==NULL || data==NULL)
    return(NULL);
  if(list->marker==NULL) //in case the marker ends up unset
    list->marker=list->head;
  if((new_node=malloc(sizeof(DL_node))))
    {
      new_node->data=data;
      new_node->prev=NULL;
      new_node->next=NULL;
      list->count++;
      if(list->head->next==NULL) //no l
	{
	  list->head->next=list->head->prev=new_node;
	  new_node->prev=list->head;
	  new_node->next=list->head;
	}
      else if(direction)
	{
	  new_node->next=list->marker->next;
	  new_node->prev=list->marker;
	  list->marker->next->prev=new_node;
	  list->marker->next=new_node;
	}
      else
	{
	  new_node->prev=list->marker->prev;
	  new_node->next=list->marker;
	  list->marker->prev->next=new_node;
	  list->marker->prev=new_node;
	}
	list->marker=new_node;
    }
  else
    {
      return(NULL);
    }
  return(list->marker->data);
}

/* 
 * Remove DL_node from list without deallocating data.
 * if marker == killme .
 *  when direction true it moves marker after 
 *  when direction false it moves marker before.
 * to previous if there is no next.
 */
void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
{
  if(killme!=NULL)
    {
      void *killer_data=killme->data;
      // take care of head and marker pointers.
      if(list->marker==killme)
	_dlist_mark_move(list,direction);
      if(killme ==list->head->next)
	list->head->next=killme->next;
      if(killme==list->head->prev)  
	list->head->prev=killme->prev;
      // remove from list
      if(killme->prev !=NULL)
	killme->prev->next=killme->next;
      if(killme->next !=NULL)
	killme->next->prev=killme->prev;
      list->count--;
      free(killme);
      return(killer_data);
    }
  else
    return (NULL);
}


/*
 * Insert node containing data after end.
 */
void dlist_push(Dlist *list,void *data)
{
  list->marker=list->head->prev;
  dlist_insert(list,data,1);
}

/*
 * Insert node containing data at start.
 */

void dlist_unshift(Dlist *list,void *data)

{
  list->marker=list->head->next;
  dlist_insert(list,data,0);
}

void dlist_unshift_sorted(Dlist *list, void *data, 
			int (*sorter)(void *new, void *old))
{
	if (list->count == 0)
		dlist_unshift(list, data);
	else {
		list->marker=list->head->next;
		dlist_insert_sorted(list, data, sorter);
	}
}

/* 
 * Remove end node from list.
 * Return pointer to data in removed node.
 * Null if no nodes.
 */

void *dlist_pop(Dlist *list)
{
  return(_dlist_remove(list,list->head->prev,0));
}

/* 
 * Remove start node from list.
 * Return pointer to data in removed node.
 * Null if no nodes.
 */

void *dlist_shift(Dlist *list)
{
  return(_dlist_remove(list,list->head->next,1));
}


/* 
 * destroy the list freeing all memory
 */


void dlist_destroy(Dlist *list)
{
  if(list !=NULL)
    {
      dlist_start(list);
      dlist_next(list);
      while (dlist_mark(list)) {
	      dlist_delete(list,1);
      }
      free(list);
    }
}

/**
 *  Return void pointer to list_data element matching comp function criteria
 *  else null
 *  Does not move the marker.
 */

void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
{
	/* test the comp function on each node */
	struct dl_node *nodepointer;
	dlist_for_each_nomark(list,nodepointer)
		if(comp(target,nodepointer->data))
			return(nodepointer->data);
	return(NULL);
}

/**
 * Apply the node_operation function to each data node in the list
 */
void dlist_transform(struct dlist *list, void (*node_operation)(void *))
{
	struct dl_node *nodepointer;
	dlist_for_each_nomark(list,nodepointer)
		node_operation(nodepointer->data);
}

/**
 * insert new into list in sorted order
 * sorter function in form int sorter(new,ith)
 *       must return 1 for when new should go before ith
 *       else 0
 * return pointer to inserted node
 * NOTE: assumes list is already sorted
 */
void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
{
	for(dlist_start(list),dlist_next(list); \
		list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
	return(dlist_insert_before(list,new));
}
Commit	Line	Data
fe3fe3b2 DS	1	/*
	2	* dlist.c
	3	*
	4	* Copyright (C) 2003 Eric J Bohm
	5	*
	6	* This library is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU Lesser General Public
	8	* License as published by the Free Software Foundation; either
	9	* version 2.1 of the License, or (at your option) any later version.
	10	*
	11	* This library is distributed in the hope that it will be useful,
	12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	* Lesser General Public License for more details.
	15	*
	16	* You should have received a copy of the GNU Lesser General Public
	17	* License along with this library; if not, write to the Free Software
	18	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021110307 USA
	19	*
	20	*/
	21
	22
	23	/* Double linked list implementation.
	24
	25	* You allocate the data and give dlist the pointer.
	26	* If your data is complex set the dlist->del_func to a an appropriate
	27	* delete function. Otherwise dlist will just use free.
	28
	29	*/
bf0314e3	30	#include <stdlib.h>
fe3fe3b2 DS	31	#include "dlist.h"
	32
	33	/*
	34	* Return pointer to node at marker.
	35	* else null if no nodes.
	36	*/
	37
	38	inline void dlist_mark(Dlist list)
	39	{
	40	if(list->marker!=NULL)
	41	return(list->marker->data);
	42	else
	43	return(NULL);
	44	}
	45
	46	/*
	47	* Set marker to start.
	48	*/
	49
	50	inline void dlist_start(Dlist *list)
	51	{
	52	list->marker=list->head;
	53	}
	54
	55	/*
	56	* Set marker to end.
	57	*/
	58
	59	inline void dlist_end(Dlist *list)
	60	{
	61	list->marker=list->head;
	62	}
	63
	64	/* internal use function
	65	* quickie inline to consolidate the marker movement logic
	66	* in one place
	67	*
	68	* when direction true it moves marker after
	69	* when direction false it moves marker before.
	70	* return pointer to data at new marker
	71	* if nowhere to move the marker in desired direction return null
	72	*/
	73	inline void _dlist_mark_move(Dlist list,int direction)
	74	{
	75	if(direction)
	76	{
	77	if( list->marker->next!=NULL)
	78	list->marker=list->marker->next;
	79	else
	80	return(NULL);
	81	}
	82	else
	83	{
	84	if( list->marker->prev!=NULL)
	85	list->marker=list->marker->prev;
	86	else
	87	return(NULL);
	88	}
	89	if(list->marker!=list->head)
	90	return(list->marker->data);
	91	else
	92	return(NULL);
	93	}
	94
95	/*
96	* Create new linked list to store nodes of datasize.
97	* return null if list cannot be created.
98	*/
99	Dlist *dlist_new(size_t datasize)
100	{
101	Dlist *list=NULL;
102	if((list=malloc(sizeof(Dlist))))
103	{
104	list->marker=NULL;
105	list->count=0L;
106	list->data_size=datasize;
107	list->del_func=free;
108	list->head=&(list->headnode);
109	list->head->prev=NULL;
110	list->head->next=NULL;
111	list->head->data=NULL;
112	}
113	return(list);
114	}
115
116	/*
117	* Create new linked list to store nodes of datasize set list
118	* data node delete function to the passed in del_func
119	* return null if list cannot be created.
120	*/
121	Dlist dlist_new_with_delete(size_t datasize,void (del_func)(void*))
122	{
123	Dlist *list=NULL;
124	list=dlist_new(datasize);
125	if(list!=NULL)
126	list->del_func=del_func;
127	return(list);
128	}
129
130
131	/*
132	* remove marker node from list
133	* call data_delete function on data if registered.
134	* otherwise call free.
135	* when direction true it moves marker after
136	* when direction false it moves marker before.
137	* free marker node
138	* return nothing.
139	*/
140	void dlist_delete(Dlist *list,int direction)
141	{
142	if((list->marker != list->head)&&(list->marker!=NULL))
143	{
144	DL_node *corpse;
145	corpse=list->marker;
146	_dlist_mark_move(list,direction);
147	if(list->head->next==corpse)
148	list->head->next=corpse->next;
149	if(list->head->prev==corpse)
150	list->head->prev=corpse->prev;
151	if(corpse->prev!=NULL) //should be impossible
152	corpse->prev->next=corpse->next;
153	if(corpse->next!=NULL) //should be impossible
154	corpse->next->prev=corpse->prev;
155	list->del_func(corpse->data);
156	list->count--;
157	free(corpse);
158	}
159	}
160
161	/*
162	* Insert node containing data at marker.
163	* If direction true it inserts after.
164	* If direction false it inserts before.
165	* move marker to inserted node
166	* return pointer to inserted node
167	*/
168	void dlist_insert(Dlist list,void *data,int direction)
169	{
170	DL_node *new_node=NULL;
171	if(list==NULL \|\| data==NULL)
172	return(NULL);
173	if(list->marker==NULL) //in case the marker ends up unset
174	list->marker=list->head;
175	if((new_node=malloc(sizeof(DL_node))))
176	{
177	new_node->data=data;
178	new_node->prev=NULL;
179	new_node->next=NULL;
180	list->count++;
181	if(list->head->next==NULL) //no l
182	{
183	list->head->next=list->head->prev=new_node;
184	new_node->prev=list->head;
185	new_node->next=list->head;
186	}
187	else if(direction)
188	{
189	new_node->next=list->marker->next;
190	new_node->prev=list->marker;
191	list->marker->next->prev=new_node;
192	list->marker->next=new_node;
193	}
194	else
195	{
196	new_node->prev=list->marker->prev;
197	new_node->next=list->marker;
198	list->marker->prev->next=new_node;
199	list->marker->prev=new_node;
200	}
201	list->marker=new_node;
202	}
203	else
204	{
205	return(NULL);
206	}
207	return(list->marker->data);
208	}
209
210	/*
211	* Remove DL_node from list without deallocating data.
212	* if marker == killme .
213	* when direction true it moves marker after
214	* when direction false it moves marker before.
215	* to previous if there is no next.
216	*/
217	void _dlist_remove(Dlist list,DL_node *killme,int direction)
218	{
219	if(killme!=NULL)
220	{
221	void *killer_data=killme->data;
222	// take care of head and marker pointers.
223	if(list->marker==killme)
224	_dlist_mark_move(list,direction);
225	if(killme ==list->head->next)
226	list->head->next=killme->next;
227	if(killme==list->head->prev)
228	list->head->prev=killme->prev;
229	// remove from list
230	if(killme->prev !=NULL)
231	killme->prev->next=killme->next;
232	if(killme->next !=NULL)
233	killme->next->prev=killme->prev;
234	list->count--;
235	free(killme);
236	return(killer_data);
237	}
238	else
239	return (NULL);
240	}
241
242
243	/*
244	* Insert node containing data after end.
245	*/
246	void dlist_push(Dlist list,void data)
247	{
248	list->marker=list->head->prev;
249	dlist_insert(list,data,1);
250	}
251
252	/*
253	* Insert node containing data at start.
254	*/
255
256	void dlist_unshift(Dlist list,void data)
257
258	{
259	list->marker=list->head->next;
260	dlist_insert(list,data,0);
261	}
262
d1fb871d AM	263	void dlist_unshift_sorted(Dlist list, void data,
	264	int (sorter)(void new, void *old))
	265	{
	266	if (list->count == 0)
	267	dlist_unshift(list, data);
	268	else {
	269	list->marker=list->head->next;
	270	dlist_insert_sorted(list, data, sorter);
	271	}
	272	}
fe3fe3b2 DS	273
	274	/*
	275	* Remove end node from list.
	276	* Return pointer to data in removed node.
	277	* Null if no nodes.
	278	*/
	279
	280	void dlist_pop(Dlist list)
	281	{
	282	return(_dlist_remove(list,list->head->prev,0));
	283	}
	284
	285	/*
	286	* Remove start node from list.
	287	* Return pointer to data in removed node.
	288	* Null if no nodes.
	289	*/
	290
	291	void dlist_shift(Dlist list)
	292	{
	293	return(_dlist_remove(list,list->head->next,1));
	294	}
	295
	296
	297	/*
	298	* destroy the list freeing all memory
	299	*/
	300
	301
	302	void dlist_destroy(Dlist *list)
	303	{
	304	if(list !=NULL)
	305	{
	306	dlist_start(list);
	307	dlist_next(list);
	308	while (dlist_mark(list)) {
	309	dlist_delete(list,1);
	310	}
	311	free(list);
	312	}
	313	}
	314
	315	/**
	316	* Return void pointer to list_data element matching comp function criteria
	317	* else null
	318	* Does not move the marker.
	319	*/
	320
	321	void dlist_find_custom(struct dlist list, void target, int (comp)(void , void ))
	322	{
	323	/* test the comp function on each node */
	324	struct dl_node *nodepointer;
	325	dlist_for_each_nomark(list,nodepointer)
	326	if(comp(target,nodepointer->data))
	327	return(nodepointer->data);
	328	return(NULL);
	329	}
	330
	331	/**
	332	* Apply the node_operation function to each data node in the list
	333	*/
	334	void dlist_transform(struct dlist list, void (node_operation)(void *))
	335	{
	336	struct dl_node *nodepointer;
337	dlist_for_each_nomark(list,nodepointer)
338	node_operation(nodepointer->data);
339	}
340
341	/**
342	* insert new into list in sorted order
343	* sorter function in form int sorter(new,ith)
344	* must return 1 for when new should go before ith
345	* else 0
346	* return pointer to inserted node
347	* NOTE: assumes list is already sorted
348	*/
349	void dlist_insert_sorted(struct dlist list, void new, int (sorter)(void , void ))
350	{
351	for(dlist_start(list),dlist_next(list); \
352	list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
353	return(dlist_insert_before(list,new));
354	}