PULSAR  1.0.0
Parallel Ultra Light Systolic Array Runtime
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_list.c File Reference

dependency free linked list implementation More...

#include <stdio.h>
#include <stdlib.h>
#include "icl_list.h"
Include dependency graph for icl_list.c:

Go to the source code of this file.

Functions

icl_list_ticl_list_new ()
 Create new linked list. More...
 
icl_list_ticl_list_insert (icl_list_t *head, icl_list_t *pos, void *data)
 Insert a new node after the specified node. More...
 
int icl_list_delete (icl_list_t *head, icl_list_t *pos, void(*free_function)(void *))
 Delete the specified node. More...
 
icl_list_ticl_list_search (icl_list_t *head, void *data, int(*compare)(void *, void *))
 Finds a data item in the specified linked list. More...
 
icl_list_ticl_list_isort (icl_list_t *head, void *data, int(*compare)(void *, void *))
 Insert data into a sorted list. Does not support direct comparison of pointers. More...
 
int icl_list_destroy (icl_list_t *head, void(*free_function)(void *))
 Frees the resources associated with this linked list. More...
 
int icl_list_size (icl_list_t *head)
 Get the number of items in this linked list. More...
 
icl_list_ticl_list_first (icl_list_t *head)
 Get the first item in this linked list. More...
 
icl_list_ticl_list_last (icl_list_t *head)
 Get the last item in this linked list. More...
 
icl_list_ticl_list_next (icl_list_t *head, icl_list_t *pos)
 Get the node following the specified node. More...
 
icl_list_ticl_list_prev (icl_list_t *head, icl_list_t *pos)
 Get the node preceding the specified node. More...
 
icl_list_ticl_list_concat (icl_list_t *head1, icl_list_t *head2)
 Concatenate two linked lists. More...
 
icl_list_ticl_list_prepend (icl_list_t *head, void *data)
 Insert a node at the beginning of this list. More...
 
icl_list_ticl_list_append (icl_list_t *head, void *data)
 Insert a node at the end of this list. More...
 

Detailed Description

dependency free linked list implementation

Author
Keith Seymour
Jakub Kurzak

PULSAR Runtime http://icl.eecs.utk.edu/pulsar/ Copyright (C) 2012-2013 University of Tennessee.

Definition in file icl_list.c.

Function Documentation

icl_list_t* icl_list_append ( icl_list_t head,
void *  data 
)

Insert a node at the end of this list.

Parameters
head– the linked list
data– the data to be inserted
Returns
pointer to the new node. returns NULL on error.

Definition at line 326 of file icl_list.c.

References icl_list_s::blink, and icl_list_insert().

327 {
328  return (icl_list_insert(head, head->blink, data));
329 }
icl_list_t * icl_list_insert(icl_list_t *head, icl_list_t *pos, void *data)
Insert a new node after the specified node.
Definition: icl_list.c:49
struct icl_list_s * blink
Definition: icl_list.h:22

Here is the call graph for this function:

Here is the caller graph for this function:

icl_list_t* icl_list_concat ( icl_list_t head1,
icl_list_t head2 
)

Concatenate two linked lists.

Parameters
head1– the first linked list
head2– the second linked list
Returns
pointer to the new linked list, which consists of <head1,head2>. returns NULL on error.

Definition at line 290 of file icl_list.c.

References icl_list_s::blink, and icl_list_s::flink.

291 {
292  if (!head1 || !head2 || !head1->blink || !head2->flink)
293  return NULL;
294 
295  head1->blink->flink = head2->flink;
296  head2->flink->blink = head1->blink;
297  head1->blink = head2->blink;
298 
299  free(head2);
300  return(head1);
301 }
struct icl_list_s * blink
Definition: icl_list.h:22
struct icl_list_s * flink
Definition: icl_list.h:21
int icl_list_delete ( icl_list_t head,
icl_list_t pos,
void(*)(void *)  free_function 
)

Delete the specified node.

Parameters
head– the linked list containing the node to be deleted
pos– the node to be deleted
free_function– pointer to function that frees the node data
Returns
0 on success, -1 on failure.

Definition at line 83 of file icl_list.c.

References icl_list_s::blink, icl_list_s::data, and icl_list_s::flink.

85 {
86  if (!pos || !head)
87  return -1;
88  if (pos == head)
89  return -1;
90 
91  if (free_function && pos->data)
92  (*free_function)(pos->data);
93 
94  pos->blink->flink = pos->flink;
95 
96  if (pos->flink)
97  pos->flink->blink = pos->blink;
98  else
99  head->blink = pos->blink; /* pos at end of list */
100 
101  free(pos);
102  return 0;
103 }
void * data
Definition: icl_list.h:20
struct icl_list_s * blink
Definition: icl_list.h:22
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

int icl_list_destroy ( icl_list_t head,
void(*)(void *)  free_function 
)

Frees the resources associated with this linked list.

Parameters
head– the linked list to be destroyed
free_function– pointer to function that frees the node's data
Returns
0 on success, -1 on failure.

Definition at line 173 of file icl_list.c.

References icl_list_s::data, and icl_list_s::flink.

174 {
175  icl_list_t *node, *tmpnode;
176 
177  if (!head)
178  return -1;
179 
180  for (node = head; node != NULL;) {
181  tmpnode = node->flink;
182 
183  if (free_function != NULL && node->data != NULL)
184  (*free_function)(node->data);
185 
186  free(node);
187  node = tmpnode;
188  }
189  return 0;
190 }
void * data
Definition: icl_list.h:20
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

icl_list_t* icl_list_first ( icl_list_t head)

Get the first item in this linked list.

Parameters
head– the linked list
Returns
pointer to the first item. returns NULL on error.

Definition at line 221 of file icl_list.c.

References icl_list_s::flink.

222 {
223  if (head)
224  return head->flink;
225 
226  return NULL;
227 }
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

icl_list_t* icl_list_insert ( icl_list_t head,
icl_list_t pos,
void *  data 
)

Insert a new node after the specified node.

Parameters
head– the linked list
pos– points to the position of the new node (it will be inserted after this node)
data– pointer to the data that is to be inserted
Returns
pointer to the new node. returns NULL on error.

Definition at line 49 of file icl_list.c.

References icl_list_s::blink, icl_list_s::data, and icl_list_s::flink.

50 {
51  icl_list_t *node;
52 
53  if(!head || !pos)
54  return NULL;
55 
56  node = (icl_list_t*)malloc(sizeof(icl_list_t));
57  if (!node)
58  return NULL;
59 
60  node->blink = pos;
61  node->flink = pos->flink;
62  node->data = data;
63 
64  if (pos->flink)
65  pos->flink->blink = node;
66  else
67  head->blink = node; /* node at end of list */
68 
69  pos->flink = node;
70  return node;
71 }
void * data
Definition: icl_list.h:20
struct icl_list_s * blink
Definition: icl_list.h:22
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

icl_list_t* icl_list_isort ( icl_list_t head,
void *  data,
int(*)(void *, void *)  compare 
)

Insert data into a sorted list. Does not support direct comparison of pointers.

Parameters
head– the linked list
data– the data to be inserted
compare– function that compares the data items
Returns
pointer to the new node. NULL on error.

Definition at line 145 of file icl_list.c.

References icl_list_s::data, icl_list_s::flink, and icl_list_insert().

147 {
148  if (!head || !compare)
149  return NULL;
150 
151  if (head->flink == NULL)
152  return (icl_list_insert(head, head, data));
153 
154  icl_list_t *node = head->flink;
155  if (compare(data, node->data) <= 0)
156  return (icl_list_insert(head, head, data));
157 
158  while (node->flink != NULL && compare(data, node->flink->data) > 0)
159  node = node->flink;
160  return (icl_list_insert(head, node, data));
161 }
void * data
Definition: icl_list.h:20
icl_list_t * icl_list_insert(icl_list_t *head, icl_list_t *pos, void *data)
Insert a new node after the specified node.
Definition: icl_list.c:49
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the call graph for this function:

Here is the caller graph for this function:

icl_list_t* icl_list_last ( icl_list_t head)

Get the last item in this linked list.

Parameters
head– the linked list
Returns
pointer to the last item. returns NULL on error.

Definition at line 237 of file icl_list.c.

References icl_list_s::blink.

238 {
239  if (head)
240  return head->blink;
241 
242  return NULL;
243 }
struct icl_list_s * blink
Definition: icl_list.h:22
icl_list_t* icl_list_new ( )

Create new linked list.

Returns
pointer to new linked list. returns NULL on error.

Definition at line 23 of file icl_list.c.

References icl_list_s::blink, icl_list_s::data, and icl_list_s::flink.

24 {
25  icl_list_t *node;
26 
27  node = (icl_list_t*)malloc(sizeof(icl_list_t));
28  if (!node)
29  return NULL;
30 
31  node->flink = NULL;
32  node->blink = node;
33  node->data = NULL;
34 
35  return(node);
36 }
void * data
Definition: icl_list.h:20
struct icl_list_s * blink
Definition: icl_list.h:22
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

icl_list_t* icl_list_next ( icl_list_t head,
icl_list_t pos 
)

Get the node following the specified node.

Parameters
head– the list containing the specified node
pos– the node whose successor should be returned
Returns
pointer to the next node. returns NULL on error.

Definition at line 254 of file icl_list.c.

References icl_list_s::flink.

255 {
256  if(pos)
257  return pos->flink;
258 
259  return NULL;
260 }
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function:

icl_list_t* icl_list_prepend ( icl_list_t head,
void *  data 
)

Insert a node at the beginning of this list.

Parameters
head– the linked list
data– the data to be inserted
Returns
pointer to the new node. returns NULL on error.

Definition at line 312 of file icl_list.c.

References icl_list_insert().

313 {
314  return (icl_list_insert(head, head, data));
315 }
icl_list_t * icl_list_insert(icl_list_t *head, icl_list_t *pos, void *data)
Insert a new node after the specified node.
Definition: icl_list.c:49

Here is the call graph for this function:

Here is the caller graph for this function:

icl_list_t* icl_list_prev ( icl_list_t head,
icl_list_t pos 
)

Get the node preceding the specified node.

Parameters
head– the list containing the specified node
pos– the node whose predecessor should be returned
Returns
pointer to the previous node. returns NULL on error.

Definition at line 271 of file icl_list.c.

References icl_list_s::blink.

272 {
273  if (pos && pos->blink != NULL && pos != head &&
274  pos->blink != head && pos->blink != pos)
275  return pos->blink;
276 
277  return NULL;
278 }
struct icl_list_s * blink
Definition: icl_list.h:22
icl_list_t* icl_list_search ( icl_list_t head,
void *  data,
int(*)(void *, void *)  compare 
)

Finds a data item in the specified linked list.

Parameters
head– the linked list
data– the data to be found
compare– function that compares the data items
Returns
pointer to the node, if found. otherwise returns NULL.

Definition at line 115 of file icl_list.c.

References icl_list_s::data, and icl_list_s::flink.

117 {
118  icl_list_t *node;
119 
120  if (!head)
121  return NULL;
122 
123  for (node = head->flink; node != NULL; node = node->flink) {
124  if (!node->data)
125  continue;
126  if ((compare && (*compare)(node->data, data) == 0))
127  break;
128  else if (node->data == data)
129  break; /* compare == NULL, then direct comparison of pointers */
130  }
131  return(node);
132 }
void * data
Definition: icl_list.h:20
struct icl_list_s * flink
Definition: icl_list.h:21
int icl_list_size ( icl_list_t head)

Get the number of items in this linked list.

Parameters
head– the linked list
Returns
the number of items in the list. returns -1 on error.

Definition at line 200 of file icl_list.c.

References icl_list_s::flink.

201 {
202  int size = 0;
203 
204  if (!head)
205  return -1;
206 
207  while ((head=head->flink))
208  size++;
209 
210  return size;
211 }
struct icl_list_s * flink
Definition: icl_list.h:21

Here is the caller graph for this function: