HIPL

Merge lp:~stefan.goetz-deactivatedaccount/hipl/hip-ll-cleanup into lp:hipl

  1. hip-ll-cleanup
  2. Merge into trunk
Proposed by Stefan Götz
Status: Rejected
Rejected by: Stefan Götz
Proposed branch: lp:~stefan.goetz-deactivatedaccount/hipl/hip-ll-cleanup
Merge into: lp:hipl
Diff against target: 736 lines (+245/-210)
8 files modified
hipd/hip_socket.c (+5/-5)
hipd/maintenance.c (+2/-2)
hipd/pkt_handling.c (+2/-2)
hipd/registration.c (+9/-9)
hipd/user.c (+1/-1)
lib/core/linkedlist.c (+190/-159)
lib/core/linkedlist.h (+16/-12)
lib/core/modularization.c (+20/-20)
To merge this branch: bzr merge lp:~stefan.goetz-deactivatedaccount/hipl/hip-ll-cleanup
Reviewer Review Type Date Requested Status
Stefan Götz (community) Disapprove
Christof Mroz Approve
Review via email: mp+56058@code.launchpad.net

Description of the change

Improve const correctness and reduce code duplication in linked list implementation.

Reviewers may want to review individual commits.

To post a comment you must log in.
Revision history for this message
Christof Mroz (christof-mroz) wrote :
Download full text (3.5 KiB)

Approved because the implementation seems correct, but some possible improvements:

> +static struct hip_ll_node *hip_ll_get_node_with_prev(const struct hip_ll *const list,
> [...]
> + for (node = list->head; node; node = node->next) {
> + if (i != idx) {
> + p = node;
> + i += 1;
> + } else {
> + *prev = p;
> + break;
> + }
> + }

More concise (but see my next comment too):

*prev = NULL;
node = list->head;
for (unsigned i = 0; i < idx; ++i) {
 *prev = node;
 node = node->next;
}

> + HIP_ASSERT(node &&
> + ((idx == 0 && !*prev) || (*prev && (*prev)->next == node)));
> +
> + return node;
> +}
> +
> +/**
> + * Get the list node with the specified index.
> + *
> + * @param list points to the list to search. The result of calling this
> + * function with list == NULL is undefined.
> + * @param idx the index of the list node to retrieve. The first node element
> + * has the index 0. The result of calling this function with an idx
> + * value greater than or equal to the number of nodes in the list
> + * is undefined.
> + * @return the list node with the index idx.
> + */
> +static struct hip_ll_node *hip_ll_get_node(const struct hip_ll *const list,
> + const unsigned idx)
> +{
> + struct hip_ll_node *p = NULL;
> +
> + return hip_ll_get_node_with_prev(list, idx, &p);
> +}
> +
> +/**

I would implement the _with_prev() variant in terms of this function, not the other way around:

if (idx == 0) {
 *prev = NULL;
 return list->head;
} else {
 *prev = hip_ll_get_node(list, idx-1);
 return (*prev)->next;
}

> - * parameter @c linkedlist with payload data @c ptr. If there are less than
> - * (<code>index -1</code>) elements in the list, the element will be added as
> - * the last element of the list.
> + * parameter @c linkedlist with payload data @c ptr. If there are exactly
> + * <code>index</code> elements in the list, the element is added as the last
> + * element of the list.

Unrelated: Semantic markup: @a rather than <code>...</code> where possible.

> + if (index == 0) {
> + newnode->next = linkedlist->head;
> + linkedlist->head = newnode;
> + } else {
> + // newnode is to be inserted after prev and before next
> + struct hip_ll_node *next = NULL;
> + struct hip_ll_node *prev = NULL;
> +
> + if (index != linkedlist->element_count) {
> + next = hip_ll_get_node_with_prev(linkedlist, index, &prev);
> + } else {
> + prev = hip_ll_get_node(linkedlist, index - 1);
> + next = NULL;
> + }
> + HIP_ASSERT(prev->next == next);
> + prev->next = newnode;
> + newnode->next = next;
> }

The index != 0 branch can be simplified:
- parent = node[index-1]
- new->next = parent->child
- parent->next = new

If we're two-star programmers [1] at HIPL, the following also gets rid of the
branching:

// find storage of in...

Read more...

review: Approve
Revision history for this message
Christof Mroz (christof-mroz) wrote :

Mhh looks like I accidentally removed hipl-core from the reviewers list... you may need to add the team it again if there are problems.

Revision history for this message
Stefan Götz (stefan.goetz-deactivatedaccount) wrote :

> What's wrong with using utlist [2], btw?
> [2] http://uthash.sourceforge.net/utlist.html

Ah, awesome. I'm all for re-using existing implementations such as this.

Would anyone object to using utlist as the preferred list
implementation in HIPL?

Stefan

Revision history for this message
Stefan Götz (stefan.goetz-deactivatedaccount) wrote :

I'll put this merge proposal on ice for now and create a branch for trying out utlist as a replacement for slist to see how that works out and whether utlist proves usable.

review: Disapprove
Revision history for this message
Diego Biurrun (diego-biurrun) wrote :

On Mon, Apr 04, 2011 at 09:50:54AM +0000, Stefan Götz wrote:
> The proposal to merge lp:~stefan.goetz/hipl/hip-ll-cleanup into lp:hipl has been updated.
>
> Status: Needs review => Rejected

I'd like to suggest that you merge this. It is better than what we have
currently and the work is already done. If you decide to replace it by
something even better later on - fine. But in the meantime I would
suggest adding all improvements to HIPL, no matter how small.

Diego

Revision history for this message
Stefan Götz (stefan.goetz-deactivatedaccount) wrote :

>> The proposal to merge lp:~stefan.goetz/hipl/hip-ll-cleanup into lp:hipl has been updated.
>>
>>     Status: Needs review => Rejected
>
> I'd like to suggest that you merge this.  It is better than what we have
> currently and the work is already done.  If you decide to replace it by
> something even better later on - fine.  But in the meantime I would
> suggest adding all improvements to HIPL, no matter how small.

I will do that because I'd like to stick with hip_ll for now. However,
I will keep working on the branch a little before creating a merge
proposal again, both because Christof made outstanding suggestions and
because I changed my mind about the design of some of those
improvements.

Stefan

Revision history for this message
Diego Biurrun (diego-biurrun) wrote :

On Tue, Apr 05, 2011 at 08:59:49PM +0000, Stefan Götz wrote:
> >> The proposal to merge lp:~stefan.goetz/hipl/hip-ll-cleanup into lp:hipl has been updated.
> >>
> >>     Status: Needs review => Rejected
> >
> > I'd like to suggest that you merge this.  It is better than what we have
> > currently and the work is already done.  If you decide to replace it by
> > something even better later on - fine.  But in the meantime I would
> > suggest adding all improvements to HIPL, no matter how small.
>
> I will do that because I'd like to stick with hip_ll for now. However,
> I will keep working on the branch a little before creating a merge
> proposal again, both because Christof made outstanding suggestions and
> because I changed my mind about the design of some of those
> improvements.

OK, I can live with that of course, I'd just like to reiterate that over
time I have become quite a fan of small iterative improvements.

If I hadn't manually merged those const correctness fixes of yours they
might now be lost in an abandoned branch somewhere on the internet.

So - merge early and merge often without sacrificing quality and split
off sensible parts as early as you can. That's my recipe for success :)

Diego

Revision history for this message
Diego Biurrun (diego-biurrun) wrote :

On Sun, Apr 03, 2011 at 12:18:31PM +0000, Christof Mroz wrote:
>
> What's wrong with using utlist [2], btw?
>
> [2] http://uthash.sourceforge.net/utlist.html

That's likely not the only viable list implementation we could leverage.

Others that have been pointed out to me are glib, gnulib and sys/queue.h.
Especially the latter should be available on every system that HIPL cares
about...

Diego

Revision history for this message
Diego Biurrun (diego-biurrun) wrote :

On Wed, Apr 06, 2011 at 04:18:36PM +0200, Diego Biurrun wrote:
> On Sun, Apr 03, 2011 at 12:18:31PM +0000, Christof Mroz wrote:
> >
> > What's wrong with using utlist [2], btw?
> >
> > [2] http://uthash.sourceforge.net/utlist.html
>
> That's likely not the only viable list implementation we could leverage.
>
> Others that have been pointed out to me are glib, gnulib and sys/queue.h.
> Especially the latter should be available on every system that HIPL cares
> about...

man 3 queue

Diego

Revision history for this message
Christof Mroz (christof-mroz) wrote :

On Wed, 06 Apr 2011 16:18:36 +0200, Diego Biurrun <email address hidden> wrote:

> On Sun, Apr 03, 2011 at 12:18:31PM +0000, Christof Mroz wrote:
>>
>> What's wrong with using utlist [2], btw?
>>
>> [2] http://uthash.sourceforge.net/utlist.html
>
> That's likely not the only viable list implementation we could leverage.

Yes, that was just one that came to my mind. But...

> Others that have been pointed out to me are glib, gnulib and sys/queue.h.
> Especially the latter should be available on every system that HIPL cares
> about...

...I haven't heard about sys/queue.h yet, thanks. queue(3) looks so
similar to utlist that there's probably no reason to even consider utlist
anymore.

As I've discussed with Stefan outside the mailinglist, the design is quite
different from hip_ll though (for the better in my opinion: type-safe,
simpler, memory-efficient considering cache coherency and space usage), so
incorporating it could be a lot of work.

Revision history for this message
Stefan Götz (stefan.goetz-deactivatedaccount) wrote :

> As I've discussed with Stefan outside the mailinglist, the design is quite
> different from hip_ll though (for the better in my opinion: type-safe,
> simpler, memory-efficient considering cache coherency and space usage)

That's what makes it not useful in HIPL. sys/queue.h and utlist allow
to manage only 'objects' in a list but not 'references'. Here's why:

sys/queue.h and utlist can store objects of the following type:

struct party {
    struct party *next;
    char *host;
    char *street;
    int houseno;
    int date;
    char *costume;
}

That's fine as long as we want only one single 'parties' list in which
all known party objects are to be stored. If however, we'd like to
reference some of those objects in an additional list, say the
'coolparties' list, what do we do?
a) We copy all those party objects that are cool parties and create
the 'coolparties' list from those copies. We often don't want that
because a change to the original party object (say, its date) should
be immediately visible in both party lists.
b) We create a new
struct coolparty {
    struct coolparty *next;
    struct party *party;
} and add those objects to the 'coolparties' list, referencing party
objects from the parties list. That, of course, means that we need to
allocate and free those additional coolparty objects on the fly. Now
if we get into the same situation for a number of different object
types, that's a lot of code duplication.

The coolparties scenario is fairly common in HIPL. So what we want in
HIPL is a list implementation where list nodes reference objects
instead of turning the objects into list nodes themselves. sys/queue.h
and utlist do the latter, not the former.

SimCList seems to be ok functionality-wise and license-wise, but is
not under a lot of development. glib is fairly awesome but also fairly
heavy-weight. Not sure if it's available reliable for scratchbox or
Android or friends.

hip_ll get's the job done pretty decently - a bit of cleanup, a few
extensions... I mean I'd love to reuse something else, but here,
hip_ll doesn't look like such a bad candidate for re-use. Any
opinions?

Stefan

Unmerged revisions

5817. By Stefan Götz

Add an internal, more generic function for deleting a list node from a linked list.
Simplify the hip_ll_del() function by re-using the new internal function.

5816. By Stefan Götz

Add internal functions for retrieving list nodes.
Simplify the existing functions hip_ll_add() and hip_ll_get() by re-using the new functions.

5815. By Stefan Götz

Simplify hip_ll_uninit() to re-use existing code instead of re-implementing it.

5814. By Stefan Götz

Improved const correctness of linked list implementation. Adapted code using linked lists where necessary.

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'hipd/hip_socket.c'
2--- hipd/hip_socket.c 2011-02-25 15:18:27 +0000
3+++ hipd/hip_socket.c 2011-04-02 21:41:01 +0000
4@@ -251,8 +251,8 @@
5
6 int hip_get_highest_descriptor(void)
7 {
8- int highest_descriptor = 0;
9- struct hip_ll_node *iter = NULL;
10+ int highest_descriptor = 0;
11+ const struct hip_ll_node *iter = NULL;
12
13 if (hip_sockets) {
14 while ((iter = hip_ll_iterate(hip_sockets, iter))) {
15@@ -269,7 +269,7 @@
16
17 void hip_prepare_fd_set(fd_set *read_fdset)
18 {
19- struct hip_ll_node *iter = NULL;
20+ const struct hip_ll_node *iter = NULL;
21
22 FD_ZERO(read_fdset);
23
24@@ -296,8 +296,8 @@
25 */
26 void hip_run_socket_handles(fd_set *read_fdset, struct hip_packet_context *ctx)
27 {
28- struct hip_ll_node *iter = NULL;
29- int socketfd;
30+ const struct hip_ll_node *iter = NULL;
31+ int socketfd;
32
33 if (hip_sockets) {
34 while ((iter = hip_ll_iterate(hip_sockets, iter))) {
35
36=== modified file 'hipd/maintenance.c'
37--- hipd/maintenance.c 2011-02-14 19:20:39 +0000
38+++ hipd/maintenance.c 2011-04-02 21:41:01 +0000
39@@ -224,8 +224,8 @@
40 */
41 static int hip_run_maint_functions(void)
42 {
43- int err = 0;
44- struct hip_ll_node *iter = NULL;
45+ int err = 0;
46+ const struct hip_ll_node *iter = NULL;
47
48 if (hip_maintenance_functions) {
49 while ((iter = hip_ll_iterate(hip_maintenance_functions, iter))) {
50
51=== modified file 'hipd/pkt_handling.c'
52--- hipd/pkt_handling.c 2011-02-14 18:40:02 +0000
53+++ hipd/pkt_handling.c 2011-04-02 21:41:01 +0000
54@@ -139,8 +139,8 @@
55 const uint32_t ha_state,
56 struct hip_packet_context *ctx)
57 {
58- int err = 0;
59- struct hip_ll_node *iter = NULL;
60+ int err = 0;
61+ const struct hip_ll_node *iter = NULL;
62
63 HIP_IFEL(packet_type > HIP_MAX_PACKET_TYPE,
64 -1,
65
66=== modified file 'hipd/registration.c'
67--- hipd/registration.c 2011-03-29 19:46:16 +0000
68+++ hipd/registration.c 2011-04-02 21:41:01 +0000
69@@ -104,7 +104,7 @@
70 {
71 int idx = 0;
72 time_t now = time(NULL);
73- struct hip_ll_node *iter = NULL;
74+ const struct hip_ll_node *iter = NULL;
75 struct hip_pending_request *request = NULL;
76
77 /* See hip_del_pending_request() for a comment. */
78@@ -241,8 +241,8 @@
79 */
80 int hip_del_pending_request(struct hip_hadb_state *entry)
81 {
82- int idx = 0;
83- struct hip_ll_node *iter = NULL;
84+ int idx = 0;
85+ const struct hip_ll_node *iter = NULL;
86
87 /* Iterate through the linked list. The iterator itself can't be used
88 * for deleting nodes from the list. Therefore, we just get the index of
89@@ -276,7 +276,7 @@
90 uint8_t reg_type)
91 {
92 int idx = 0;
93- struct hip_ll_node *iter = NULL;
94+ const struct hip_ll_node *iter = NULL;
95 struct hip_pending_request *request = NULL;
96
97 /* See hip_del_pending_request() for a comment. */
98@@ -308,7 +308,7 @@
99 int hip_replace_pending_requests(struct hip_hadb_state *entry_old,
100 struct hip_hadb_state *entry_new)
101 {
102- struct hip_ll_node *iter = 0;
103+ const struct hip_ll_node *iter = 0;
104
105 while ((iter = hip_ll_iterate(&pending_requests, iter)) != NULL) {
106 if (((struct hip_pending_request *) (iter->ptr))->entry == entry_old) {
107@@ -338,8 +338,8 @@
108 static int hip_get_pending_requests(struct hip_hadb_state *entry,
109 struct hip_pending_request *requests[])
110 {
111- struct hip_ll_node *iter = 0;
112- int request_count = 0;
113+ const struct hip_ll_node *iter = 0;
114+ int request_count = 0;
115
116 if (requests == NULL) {
117 return -1;
118@@ -368,8 +368,8 @@
119 */
120 static int hip_get_pending_request_count(struct hip_hadb_state *entry)
121 {
122- struct hip_ll_node *iter = 0;
123- int request_count = 0;
124+ const struct hip_ll_node *iter = 0;
125+ int request_count = 0;
126
127 while ((iter = hip_ll_iterate(&pending_requests, iter)) != NULL) {
128 if (((struct hip_pending_request *) (iter->ptr))->entry == entry) {
129
130=== modified file 'hipd/user.c'
131--- hipd/user.c 2011-03-24 17:34:21 +0000
132+++ hipd/user.c 2011-04-02 21:41:01 +0000
133@@ -185,7 +185,7 @@
134 struct hip_common *msg,
135 struct sockaddr_in6 *src)
136 {
137- struct hip_ll_node *iter = NULL;
138+ const struct hip_ll_node *iter = NULL;
139
140 if (!hip_user_msg_handles[msg_type] ||
141 !hip_ll_get_size(hip_user_msg_handles[msg_type])) {
142
143=== modified file 'lib/core/linkedlist.c'
144--- lib/core/linkedlist.c 2011-03-29 17:55:57 +0000
145+++ lib/core/linkedlist.c 2011-04-02 21:41:01 +0000
146@@ -43,7 +43,7 @@
147 *
148 * @param linkedlist the list to init.
149 */
150-void hip_ll_init(struct hip_ll *linkedlist)
151+void hip_ll_init(struct hip_ll *const linkedlist)
152 {
153 if (linkedlist != NULL) {
154 *linkedlist = (struct hip_ll) HIP_LL_INIT;
155@@ -72,34 +72,15 @@
156 * invoking this function, and then call this function with
157 * NULL as @c free_element.
158 */
159-void hip_ll_uninit(struct hip_ll *linkedlist, free_elem_fn free_element)
160+void hip_ll_uninit(struct hip_ll *const linkedlist, free_elem_fn free_element)
161 {
162- struct hip_ll_node *pointer = NULL;
163-
164- if (linkedlist == NULL || linkedlist->head == NULL) {
165- return;
166- }
167-
168- /* Free the node currently at list head and move the next item to list
169- * head. Continue this until the item at list head is NULL. If
170- * free_element() is non-NULL we also free the memory allocated for the
171- * actual element. */
172- if (free_element != NULL) {
173- while (linkedlist->head != NULL) {
174- pointer = linkedlist->head->next;
175- free_element(linkedlist->head->ptr);
176- free(linkedlist->head);
177- linkedlist->head = pointer;
178- }
179- } else {
180- while (linkedlist->head != NULL) {
181- pointer = linkedlist->head->next;
182- free(linkedlist->head);
183- linkedlist->head = pointer;
184- }
185- }
186-
187- linkedlist->element_count = 0;
188+ if (linkedlist) {
189+ while (linkedlist->head) {
190+ hip_ll_del_first(linkedlist, free_element);
191+ }
192+ HIP_ASSERT(!linkedlist->head);
193+ HIP_ASSERT(!linkedlist->element_count);
194+ }
195 }
196
197 /**
198@@ -108,7 +89,7 @@
199 * @param linkedlist the list whose node count is to be returned.
200 * @return number of nodes in the list.
201 */
202-unsigned int hip_ll_get_size(const struct hip_ll *linkedlist)
203+unsigned int hip_ll_get_size(const struct hip_ll *const linkedlist)
204 {
205 if (linkedlist == NULL) {
206 return 0;
207@@ -118,77 +99,129 @@
208 }
209
210 /**
211+ * Get the list node with the specified index and its predecessor node.
212+ *
213+ * This function helps to avoid re-implementing the linear search for different
214+ * purposes.
215+ *
216+ * @param list points to the list to search. The result of calling this
217+ * function with list == NULL is undefined.
218+ * @param idx the index of the list node to retrieve. The first node element
219+ * has the index 0. The result of calling this function with an idx
220+ * value greater than or equal to the number of nodes in the list
221+ * is undefined.
222+ * @param prev points to a struct hip_ll_node pointer. If this function returns
223+ * successfully, the value of prev is set to point to the
224+ * predecessor node of the returned node. It is set to NULL if the
225+ * returned node is the first node in the list.
226+ * @return the list node with the index idx.
227+ */
228+static struct hip_ll_node *hip_ll_get_node_with_prev(const struct hip_ll *const list,
229+ const unsigned idx,
230+ struct hip_ll_node **const prev)
231+{
232+ unsigned i = 0;
233+ struct hip_ll_node *p = NULL;
234+ struct hip_ll_node *node;
235+
236+ HIP_ASSERT(list);
237+ HIP_ASSERT((list->element_count == 0 && !list->head) ||
238+ (list->element_count == 1 && list->head && !list->head->next) ||
239+ (list->element_count > 1 && list->head && list->head->next));
240+ HIP_ASSERT(idx < list->element_count);
241+ HIP_ASSERT(prev);
242+
243+ for (node = list->head; node; node = node->next) {
244+ if (i != idx) {
245+ p = node;
246+ i += 1;
247+ } else {
248+ *prev = p;
249+ break;
250+ }
251+ }
252+
253+ HIP_ASSERT(node &&
254+ ((idx == 0 && !*prev) || (*prev && (*prev)->next == node)));
255+
256+ return node;
257+}
258+
259+/**
260+ * Get the list node with the specified index.
261+ *
262+ * @param list points to the list to search. The result of calling this
263+ * function with list == NULL is undefined.
264+ * @param idx the index of the list node to retrieve. The first node element
265+ * has the index 0. The result of calling this function with an idx
266+ * value greater than or equal to the number of nodes in the list
267+ * is undefined.
268+ * @return the list node with the index idx.
269+ */
270+static struct hip_ll_node *hip_ll_get_node(const struct hip_ll *const list,
271+ const unsigned idx)
272+{
273+ struct hip_ll_node *p = NULL;
274+
275+ return hip_ll_get_node_with_prev(list, idx, &p);
276+}
277+
278+/**
279 * Adds a new node to a linked list. Adds a new node at @c index to the
280- * parameter @c linkedlist with payload data @c ptr. If there are less than
281- * (<code>index -1</code>) elements in the list, the element will be added as
282- * the last element of the list.
283+ * parameter @c linkedlist with payload data @c ptr. If there are exactly
284+ * <code>index</code> elements in the list, the element is added as the last
285+ * element of the list.
286 *
287 * <b>Example:</b>
288 *
289- * <code>hip_ll_add(&mylist, 2, mydata);</code> will add @c mydata as the
290- * third item of the list when there are more than two elements in @c mylist.
291- * When there are less than two items in the list @c mydata will be added as
292- * the last element of @c mylist.
293+ * <code>hip_ll_add(&mylist, 2, mydata);</code> adds @c mydata as the
294+ * third item of the list when there are two or more elements in @c mylist.
295 *
296 * @param linkedlist the list where to add the new node.
297 * @param index the list index where to store the node. Indexing starts
298 * from zero.
299 * @param ptr a pointer to the data to be stored.
300 * @return zero on success, -1 if @c linkedlist or @c ptr is NULL or
301- * if there was an error when allocating memory to the new
302- * node.
303+ * index is greater than the size of list or if there is an
304+ * error when allocating memory for the new node.
305 */
306-int hip_ll_add(struct hip_ll *linkedlist, const unsigned int index, void *ptr)
307+int hip_ll_add(struct hip_ll *const linkedlist,
308+ const unsigned int index,
309+ void *const ptr)
310 {
311- struct hip_ll_node *newnode = NULL, *pointer = NULL;
312- unsigned int current_index = 0;
313-
314- if (linkedlist == NULL || ptr == NULL) {
315- return -1;
316- }
317-
318- if ((newnode = malloc(sizeof(struct hip_ll_node))) == NULL) {
319- HIP_ERROR("Error on allocating memory for a linked list node.\n");
320- return -1;
321- }
322-
323- newnode->ptr = ptr;
324- pointer = linkedlist->head;
325-
326- /* Item to add is the first item of the list or it is to be added as the
327- * first one. */
328- if (pointer == NULL || index == 0) {
329- newnode->next = pointer;
330- linkedlist->head = newnode;
331- linkedlist->element_count++;
332- }
333- /* There exist at least one element in the list and the new element is
334- * not to be added as the first one. */
335- else {
336- struct hip_ll_node *previous = pointer;
337-
338- /* Loop until "pointer" is at the last item. */
339- while (pointer->next != NULL) {
340- previous = pointer;
341- pointer = pointer->next;
342- current_index++;
343-
344- /* We have reached the target index and the index is not
345- * the index of the last item in the list. */
346- if (current_index == index) {
347- newnode->next = pointer;
348- previous->next = newnode;
349- linkedlist->element_count++;
350- return 0;
351+ if (linkedlist && index <= linkedlist->element_count && ptr) {
352+ struct hip_ll_node *newnode;
353+ if ((newnode = malloc(sizeof(*newnode)))) {
354+ newnode->ptr = ptr;
355+
356+ if (index == 0) {
357+ newnode->next = linkedlist->head;
358+ linkedlist->head = newnode;
359+ } else {
360+ // newnode is to be inserted after prev and before next
361+ struct hip_ll_node *next = NULL;
362+ struct hip_ll_node *prev = NULL;
363+
364+ if (index != linkedlist->element_count) {
365+ next = hip_ll_get_node_with_prev(linkedlist, index, &prev);
366+ } else {
367+ prev = hip_ll_get_node(linkedlist, index - 1);
368+ next = NULL;
369+ }
370+ HIP_ASSERT(prev->next == next);
371+ prev->next = newnode;
372+ newnode->next = next;
373 }
374+
375+ linkedlist->element_count += 1;
376+
377+ return 0;
378+ } else {
379+ HIP_ERROR("Error on allocating memory for a linked list node.\n");
380 }
381- /* The node is to be added as the last item of the list. */
382- newnode->next = NULL;
383- pointer->next = newnode;
384- linkedlist->element_count++;
385 }
386
387- return 0;
388+ return -1;
389 }
390
391 /**
392@@ -201,7 +234,7 @@
393 * if there was an error when allocating memory to the new
394 * node.
395 */
396-int hip_ll_add_first(struct hip_ll *linkedlist, void *ptr)
397+int hip_ll_add_first(struct hip_ll *const linkedlist, void *const ptr)
398 {
399 return hip_ll_add(linkedlist, 0, ptr);
400 }
401@@ -216,12 +249,55 @@
402 * if there was an error when allocating memory to the new
403 * node.
404 */
405-int hip_ll_add_last(struct hip_ll *linkedlist, void *ptr)
406+int hip_ll_add_last(struct hip_ll *const linkedlist, void *const ptr)
407 {
408 return hip_ll_add(linkedlist, linkedlist->element_count, ptr);
409 }
410
411 /**
412+ * Remove a node from a list and free the node memory (not the payload data).
413+ *
414+ * Since this function expects to be given the predecessor of the node to
415+ * delete, this function has a runtime complexity of O(1).
416+ *
417+ * @param list the list from which to delete the node. The result of calling
418+ * this function with list == NULL is undefined.
419+ * @param node the node to delete. The result of calling this function with
420+ * list == NULL is undefined.
421+ * @param prev the predecessor node of the node to delete. prev must be NULL
422+ * iff node is the first node in the list. The result of calling
423+ * this function under the violation of this condition is
424+ * undefined.
425+ * @return pointer to the payload data the deleted list node was associated
426+ * with.
427+ */
428+static void *hip_ll_del_node(struct hip_ll *const list,
429+ struct hip_ll_node *const node,
430+ struct hip_ll_node *const prev)
431+{
432+ void *payload;
433+
434+ HIP_ASSERT(list);
435+ HIP_ASSERT(node);
436+ HIP_ASSERT((prev && prev->next == node) ||
437+ (!prev && list->head == node));
438+ HIP_ASSERT((list->element_count == 1 && list->head && !list->head->next) ||
439+ (list->element_count > 1 && list->head && list->head->next));
440+
441+ payload = node->ptr;
442+
443+ if (prev) {
444+ prev->next = node->next;
445+ } else {
446+ list->head = node->next;
447+ }
448+ free(node);
449+ list->element_count -= 1;
450+
451+ return payload;
452+}
453+
454+/**
455 * Deletes a node from a linked list. Deletes a node at @c index and frees the
456 * memory allocated for the node from the parameter @c linkedlist. If there are
457 * less than (<code>index -1</code>) nodes in the list no action will be taken. If
458@@ -244,58 +320,25 @@
459 * element itself is deleted. NULL is also returned when
460 * the list @c linkedlist itself is NULL.
461 */
462-void *hip_ll_del(struct hip_ll *linkedlist, const unsigned int index,
463+void *hip_ll_del(struct hip_ll *const linkedlist, const unsigned int index,
464 free_elem_fn free_element)
465 {
466- struct hip_ll_node *pointer = NULL, *previous = NULL;
467- void *ptr = NULL;
468- unsigned int current_index = 0;
469-
470- if (linkedlist == NULL || linkedlist->head == NULL) {
471- return NULL;
472- } else if (index > (linkedlist->element_count - 1)) {
473- return NULL;
474- }
475-
476- if (index == 0) {
477- ptr = linkedlist->head->ptr;
478- pointer = linkedlist->head->next;
479- if (free_element != NULL) {
480- free_element(ptr);
481- ptr = NULL;
482- }
483- free(linkedlist->head);
484- linkedlist->head = pointer;
485- linkedlist->element_count--;
486- return ptr;
487- }
488-
489- pointer = previous = linkedlist->head;
490-
491- while (pointer->next != NULL) {
492- previous = pointer;
493- pointer = pointer->next;
494- current_index++;
495-
496- /* We have reached the target index. */
497- if (current_index == index) {
498- if (pointer == NULL) {
499- previous->next = NULL;
500- } else {
501- previous->next = pointer->next;
502- }
503- ptr = pointer->ptr;
504- if (free_element != NULL) {
505- free_element(ptr);
506- ptr = NULL;
507- }
508- free(pointer);
509- linkedlist->element_count--;
510- break;
511- }
512- }
513-
514- return ptr;
515+ if (linkedlist && index < linkedlist->element_count) {
516+ struct hip_ll_node *node = NULL;
517+ struct hip_ll_node *prev = NULL;
518+ void *payload;
519+
520+ node = hip_ll_get_node_with_prev(linkedlist, index, &prev);
521+ payload = hip_ll_del_node(linkedlist, node, prev);
522+ if (free_element) {
523+ free_element(payload);
524+ return NULL;
525+ } else {
526+ return payload;
527+ }
528+ } else {
529+ return NULL;
530+ }
531 }
532
533 /**
534@@ -317,7 +360,7 @@
535 * deleted. NULL is also returned when the list
536 * @c linkedlist itself is NULL.
537 */
538-void *hip_ll_del_first(struct hip_ll *linkedlist,
539+void *hip_ll_del_first(struct hip_ll *const linkedlist,
540 free_elem_fn free_element)
541 {
542 return hip_ll_del(linkedlist, 0, free_element);
543@@ -334,27 +377,15 @@
544 * @return the next element or NULL if the list end has been reached
545 * or if @c linkedlist is NULL.
546 */
547-void *hip_ll_get(struct hip_ll *linkedlist, const unsigned int index)
548+void *hip_ll_get(const struct hip_ll *const linkedlist, const unsigned int index)
549 {
550- struct hip_ll_node *pointer = linkedlist->head;
551- unsigned int current_index = 0;
552-
553- if (linkedlist == NULL || linkedlist->head == NULL) {
554- return NULL;
555- } else if (index > (linkedlist->element_count - 1)) {
556- return NULL;
557- }
558-
559- while (pointer != NULL) {
560- if (current_index == index) {
561- break;
562- }
563-
564- pointer = pointer->next;
565- current_index++;
566- }
567-
568- return pointer->ptr;
569+ if (linkedlist && index < linkedlist->element_count) {
570+ struct hip_ll_node *const node = hip_ll_get_node(linkedlist, index);
571+ HIP_ASSERT(node);
572+ return node->ptr;
573+ } else {
574+ return NULL;
575+ }
576 }
577
578 /**
579@@ -379,8 +410,8 @@
580 * using this function.</span> Consider hip_ll_del() or
581 * hip_ll_uninit() for deleting nodes and elements.
582 */
583-struct hip_ll_node *hip_ll_iterate(const struct hip_ll *linkedlist,
584- struct hip_ll_node *current)
585+const struct hip_ll_node *hip_ll_iterate(const struct hip_ll *const linkedlist,
586+ const struct hip_ll_node *const current)
587 {
588 if (linkedlist == NULL) {
589 return NULL;
590
591=== modified file 'lib/core/linkedlist.h'
592--- lib/core/linkedlist.h 2011-03-29 16:48:08 +0000
593+++ lib/core/linkedlist.h 2011-04-02 21:41:01 +0000
594@@ -61,19 +61,23 @@
595 #define HIP_LL_INIT { 0, NULL }
596
597 /** Linked list element memory deallocator function pointer. */
598-typedef void (*free_elem_fn)(void *ptr);
599+typedef void (*free_elem_fn)(void *const ptr);
600
601-void hip_ll_init(struct hip_ll *linkedlist);
602-void hip_ll_uninit(struct hip_ll *linkedlist, free_elem_fn free_element);
603-unsigned int hip_ll_get_size(const struct hip_ll *linkedlist);
604-int hip_ll_add(struct hip_ll *linkedlist, const unsigned int index, void *ptr);
605-int hip_ll_add_first(struct hip_ll *linkedlist, void *ptr);
606-int hip_ll_add_last(struct hip_ll *linkedlist, void *ptr);
607-void *hip_ll_del(struct hip_ll *linkedlist, const unsigned int index,
608+void hip_ll_init(struct hip_ll *const linkedlist);
609+void hip_ll_uninit(struct hip_ll *const linkedlist, free_elem_fn free_element);
610+unsigned int hip_ll_get_size(const struct hip_ll *const linkedlist);
611+int hip_ll_add(struct hip_ll *const linkedlist,
612+ const unsigned int index,
613+ void *const ptr);
614+int hip_ll_add_first(struct hip_ll *const linkedlist, void *const ptr);
615+int hip_ll_add_last(struct hip_ll *const linkedlist, void *const ptr);
616+void *hip_ll_del(struct hip_ll *const linkedlist, const unsigned int index,
617 free_elem_fn free_element);
618-void *hip_ll_del_first(struct hip_ll *linkedlist, free_elem_fn free_element);
619-void *hip_ll_get(struct hip_ll *linkedlist, const unsigned int index);
620-struct hip_ll_node *hip_ll_iterate(const struct hip_ll *linkedlist,
621- struct hip_ll_node *current);
622+void *hip_ll_del_first(struct hip_ll *const linkedlist,
623+ free_elem_fn free_element);
624+void *hip_ll_get(const struct hip_ll *const linkedlist,
625+ const unsigned int index);
626+const struct hip_ll_node *hip_ll_iterate(const struct hip_ll *const linkedlist,
627+ const struct hip_ll_node *const current);
628
629 #endif /* HIP_LIB_CORE_LINKEDLIST_H */
630
631=== modified file 'lib/core/modularization.c'
632--- lib/core/modularization.c 2011-04-01 12:30:35 +0000
633+++ lib/core/modularization.c 2011-04-02 21:41:01 +0000
634@@ -165,8 +165,8 @@
635 */
636 void lmod_init_state_items(struct modular_state *state)
637 {
638- struct hip_ll_node *iter = NULL;
639- int (*init_function)(struct modular_state *state) = NULL;
640+ const struct hip_ll_node *iter = NULL;
641+ int (*init_function)(struct modular_state *state) = NULL;
642
643 while ((iter = hip_ll_iterate(&state_init_functions, iter))) {
644 init_function = iter->ptr;
645@@ -300,9 +300,9 @@
646 void *entry,
647 const uint16_t priority)
648 {
649- int idx = 0;
650- struct hip_ll *new_list = NULL;
651- struct hip_ll_node *iter = NULL;
652+ int idx = 0;
653+ struct hip_ll *new_list = NULL;
654+ const struct hip_ll_node *iter = NULL;
655
656 if (!list) {
657 if (!(new_list = malloc(sizeof(struct hip_ll)))) {
658@@ -342,8 +342,8 @@
659 */
660 int lmod_unregister_function(struct hip_ll *list, const void *function)
661 {
662- int idx = 0;
663- struct hip_ll_node *iter = NULL;
664+ int idx = 0;
665+ const struct hip_ll_node *iter = NULL;
666
667 if (!list) {
668 return -1;
669@@ -440,8 +440,8 @@
670 */
671 int lmod_packet_type_exists(const uint8_t packet_type)
672 {
673- int idx = 0;
674- struct hip_ll_node *iter = NULL;
675+ int idx = 0;
676+ const struct hip_ll_node *iter = NULL;
677
678 while ((iter = hip_ll_iterate(&packet_types, iter))) {
679 if (packet_type == ((struct packet_type *) iter->ptr)->num) {
680@@ -461,7 +461,7 @@
681 */
682 const char *lmod_get_packet_identifier(const uint8_t packet_type)
683 {
684- struct hip_ll_node *iter = NULL;
685+ const struct hip_ll_node *iter = NULL;
686 HIP_DEBUG("Name search for packet type %d \n", packet_type);
687
688 while ((iter = hip_ll_iterate(&packet_types, iter))) {
689@@ -489,9 +489,9 @@
690 int lmod_register_packet_type(const uint8_t packet_type,
691 const char *const identifier)
692 {
693- int idx = 0;
694- struct hip_ll_node *iter = NULL;
695- struct packet_type *new_entry = NULL;
696+ int idx = 0;
697+ const struct hip_ll_node *iter = NULL;
698+ struct packet_type *new_entry = NULL;
699
700 if (!identifier || (lmod_packet_type_exists(packet_type) != -1)) {
701 return -1;
702@@ -559,8 +559,8 @@
703 */
704 int lmod_parameter_type_exists(const uint16_t parameter_type)
705 {
706- int index = 0;
707- struct hip_ll_node *iter = NULL;
708+ int index = 0;
709+ const struct hip_ll_node *iter = NULL;
710
711 while ((iter = hip_ll_iterate(&parameter_types, iter))) {
712 if (parameter_type == ((struct parameter_type *) iter->ptr)->num) {
713@@ -589,10 +589,10 @@
714 int lmod_register_parameter_type(const uint16_t parameter_type,
715 const char *const identifier)
716 {
717- int index = 0;
718- struct hip_ll_node *iter = NULL;
719- struct parameter_type *new_entry = NULL;
720- int err = 0;
721+ int index = 0;
722+ const struct hip_ll_node *iter = NULL;
723+ struct parameter_type *new_entry = NULL;
724+ int err = 0;
725
726 HIP_IFEL(!identifier || (lmod_parameter_type_exists(parameter_type) != -1),
727 -1, "Missing identifier or parameter type already registered.\n");
728@@ -633,7 +633,7 @@
729 */
730 const char *lmod_get_parameter_identifier(const uint16_t parameter_type)
731 {
732- struct hip_ll_node *iter = NULL;
733+ const struct hip_ll_node *iter = NULL;
734 HIP_DEBUG("Name search for parameter type %d \n", parameter_type);
735
736 while ((iter = hip_ll_iterate(&parameter_types, iter))) {

Subscribers

People subscribed via source and target branches

to all changes: