Merge lp:~cbehrens/agent-smith/slist-improvements into lp:agent-smith

[Chris Behrens]

Reworked SList to be a doubly linked list to not require searching to the end to add a new element.
Added a number of functions so that struct members are not accessed directly
Doxygen'd

[lp:~cbehrens/agent-smith/slist-improvements]

74. By Chris Behrens on 2010-08-25

add #ifndef/define/endif to slist.h

=== modified file 'src/slist.c'
--- src/slist.c	2010-08-24 05:43:50 +0000
+++ src/slist.c	2010-08-25 08:06:08 +0000
@@ -14,31 +14,142 @@
  *  limitations under the License.
  */
 #include <malloc.h>
+#include <assert.h>
 #include "slist.h"
 
-SList *slist_append(SList *list, void *data) {
-    SList *elem = malloc(sizeof(SList));
-
+struct _SListElem {
+    void *sle_data;
+    SListElem *sle_prev;
+    SListElem *sle_next;
+};
+
+struct _SList {
+    slist_destroy_cb sl_destroy_cb;
+    SListElem sl_elem;
+};
+
+/**
+ * Create a new list for storing arbitrary data
+ *
+ * @param destroy_cb Callback to call when deiniting (Can be NULL)
+ * @retval A new list that is init'd as empty
+ */
+SList *slist_init(slist_destroy_cb destroy_cb)
+{
+    SList *list = malloc(sizeof(SList));
+
+    if (list == NULL)
+        return NULL;
+
+    list->sl_destroy_cb = destroy_cb;
+    list->sl_elem.sle_data = NULL;
+    list->sl_elem.sle_prev = &(list->sl_elem);
+    list->sl_elem.sle_next = &(list->sl_elem);
+
+    return list;
+}
+
+/**
+ * Destroy a previously created list
+ *
+ * @param slist The list to destroy
+ */
+void slist_deinit(SList *slist)
+{
+    if (slist != NULL)
+    {
+        SListElem *elem;
+        SListElem *next;
+
+        for(elem = slist_first(slist);
+                elem != NULL;
+                elem = next)
+        {
+            next = slist_next(slist, elem);
+            if ((elem->sle_data != NULL) && slist->sl_destroy_cb != NULL)
+                slist->sl_destroy_cb(elem->sle_data);
+            free(elem);
+        }
+
+        free(slist);
+    }
+}
+
+/**
+ * Append a new element to a previously created slist
+ *
+ * @param list The list to append to
+ * @param data Arbitrary data pointer
+ * @retval The newly created element
+ */
+SListElem *slist_append(SList *list, void *data) {
+    SListElem *elem;
+
+    assert(list != NULL);
+
+    elem = malloc(sizeof(SListElem));
     if (elem == NULL)
         return NULL;
 
-    elem->data = data;
-    elem->next = NULL;
-
-    if (!list) {
-        return elem;
-    } else {
-        SList *last;
-        last = slist_last(list);
-        last->next = elem;
-        return list;
-    }
-}
-
-SList *slist_last(SList *list) {
-	if (list) {
-		while (list->next)
-			list = list->next;
-	}
-	return list;
-}
+    elem->sle_data = data;
+
+    elem->sle_prev = list->sl_elem.sle_prev;
+    elem->sle_next = &(list->sl_elem);
+    list->sl_elem.sle_prev->sle_next = elem;
+    list->sl_elem.sle_prev = elem;
+
+    return elem;
+}
+
+/**
+ * Return the first element of a previously created list
+ *
+ * @param list The list
+ * @retval The first element or NULL if none
+ */
+SListElem *slist_first(SList *list) {
+    return slist_next(list, &(list->sl_elem));
+}
+
+/**
+ * Return the last element of a previously created list
+ *
+ * @param list The list
+ * @retval The last element or NULL if none
+ */
+SListElem *slist_last(SList *list) {
+    return slist_prev(list, &(list->sl_elem));
+}
+
+/**
+ * Return the next element in the list after the passed element
+ *
+ * @param list The list
+ * @param elem The current element
+ * @retval The element after the current element or NULL if none left
+ */
+SListElem *slist_next(SList *list, SListElem *elem) {
+    return elem->sle_next == &(list->sl_elem) ? NULL : elem->sle_next;
+}
+
+/**
+ * Return the previous element in the list after the passed element
+ *
+ * @param list The list
+ * @param elem The current element
+ * @retval The element before the current element or NULL if none
+ */
+SListElem *slist_prev(SList *list, SListElem *elem) {
+    return elem->sle_prev == &(list->sl_elem) ? NULL : elem->sle_prev;
+}
+
+/**
+ * Return the arbitrary data pointer for an element
+ *
+ * @param elem The element you want the data for
+ * @retval The arbitrary data pointer
+ */
+void *slist_data(SListElem *elem) {
+    return elem->sle_data;
+}
+

=== modified file 'src/slist.h'
--- src/slist.h	2010-07-07 09:26:52 +0000
+++ src/slist.h	2010-08-25 08:06:08 +0000
@@ -13,12 +13,79 @@
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
+#ifndef __SRC_SLIST_H__
+#define __SRC_SLIST_H__
+
 typedef struct _SList SList;
-
-struct _SList {
-    void *data;
-    SList *next;
-};
-
-SList *slist_append(SList *list, void *data);
-SList *slist_last(SList *list);
+typedef struct _SListElem SListElem;
+
+typedef void (*slist_destroy_cb)(void *data);
+
+/**
+ * Create a new list for storing arbitrary data
+ *
+ * @param destroy_cb Callback to call when deiniting (Can be NULL)
+ * @retval A new list that is init'd as empty
+ */
+SList *slist_init(slist_destroy_cb destroy_cb);
+
+/**
+ * Destroy a previously created list
+ *
+ * @param slist The list to destroy
+ */
+void slist_deinit(SList *slist);
+
+/**
+ * Append a new element to a previously created slist
+ *
+ * @param list The list to append to
+ * @param data Arbitrary data pointer
+ * @retval The newly created element
+ */
+SListElem *slist_append(SList *list, void *data);
+
+/**
+ * Return the first element of a previously created list
+ *
+ * @param list The list
+ * @retval The first element or NULL if none
+ */
+SListElem *slist_first(SList *list);
+
+/**
+ * Return the last element of a previously created list
+ *
+ * @param list The list
+ * @retval The last element or NULL if none
+ */
+SListElem *slist_last(SList *list);
+
+/**
+ * Return the next element in the list after the passed element
+ *
+ * @param list The list
+ * @param elem The current element
+ * @retval The element after the current element or NULL if none left
+ */
+SListElem *slist_next(SList *list, SListElem *elem);
+
+/**
+ * Return the previous element in the list after the passed element
+ *
+ * @param list The list
+ * @param elem The current element
+ * @retval The element before the current element or NULL if none
+ */
+SListElem *slist_prev(SList *list, SListElem *elem);
+
+/**
+ * Return the arbitrary data pointer for an element
+ *
+ * @param elem The element you want the data for
+ * @retval The arbitrary data pointer
+ */
+void *slist_data(SListElem *elem);
+
+
+#endif /* __SRC_SLIST_H__ */

=== modified file 'src/spool.c'
--- src/spool.c	2010-08-24 17:35:14 +0000
+++ src/spool.c	2010-08-25 08:06:08 +0000
@@ -35,6 +35,13 @@
 #define INCOMING_DIR "incoming"
 #define OUTGOING_DIR "outgoing"
 
+/*
+ * Global variables
+ */
+
+int inotify_fd = -1;
+SList *callbacks = NULL;
+
 int spool_ensure_dir(const char *dir);
 
 char *spool_basedir(void);
@@ -44,11 +51,19 @@
 
     char *tmp;
 
+    callbacks = slist_init(NULL);
+    if (callbacks == NULL)
+    {
+        return -1;
+    }
+
     if (spool_ensure_dir(tmp = spool_incoming_dir()) == 0)
         free(tmp);
     else {
         syslog(LOG_DAEMON | LOG_CRIT, "Failed to create incoming spool dir: %s", tmp);
         free(tmp);
+        slist_deinit(callbacks);
+        callbacks = NULL;
         return -1;
     }
 
@@ -57,6 +72,8 @@
     else {
         syslog(LOG_DAEMON | LOG_CRIT, "Failed to create outgoing spool dir: %s", tmp);
         free(tmp);
+        slist_deinit(callbacks);
+        callbacks = NULL;
         return -1;
     }
 
@@ -235,10 +252,6 @@
     return 0;
 }
 
-int inotify_fd = -1;
-
-SList *callbacks = NULL;
-
 int spool_watch(spool_callback cb) {
     char *incoming_dir;
 
@@ -268,8 +281,7 @@
 
     free(incoming_dir);
 
-    callbacks = slist_append(callbacks, cb);
-    if (callbacks == NULL)
+    if (slist_append(callbacks, cb) == NULL)
     {
         return -1;
     }
@@ -300,7 +312,7 @@
 
             if (ev->len) {
                 char *path, *incoming_dir;
-                SList *ptr;
+                SListElem *elem;
 
                 if (ev->len > len) {
                    /* No room left in buffer, so exit out of this packet */
@@ -311,8 +323,10 @@
                 path = util_join_paths(incoming_dir, ev->name);
                 free(incoming_dir);
 
-                for (ptr = callbacks; ptr; ptr=ptr->next) {
-                    spool_callback cb = (spool_callback) ptr->data;
+                for(elem = slist_first(callbacks);
+                        elem != NULL;
+                        elem = slist_next(callbacks, elem)) {
+                    spool_callback cb = (spool_callback)slist_data(elem);
                     cb(path);
                 }
 

=== modified file 'src/xen.c'
--- src/xen.c	2010-08-20 15:27:36 +0000
+++ src/xen.c	2010-08-25 08:06:08 +0000
@@ -18,6 +18,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <assert.h>
 #include <xs.h>
 #include "log.h"
 #include "slist.h"
@@ -36,9 +37,24 @@
 /*
  * Global variables
  */
-SList *handlers;
+SList *handlers = NULL;
 struct xs_handle *xh;
 
+/*
+ * Static function prototypes
+ */
+static void _xen_destroy_callback(void *data);
+
+/*
+ * Static functions
+ */
+static void _xen_destroy_callback(void *data) {
+    token_callback_tuple *cb = (token_callback_tuple *)data;
+
+    free(cb->token);
+    free(cb);
+}
+
 void xen_fire_callback(const char *path, const char *token, void *buf,
                        unsigned int buflen);
 
@@ -48,9 +64,16 @@
  * @returns 0 on success, -1 otherwise
  */
 int xen_init(void) {
-    if (!xh)
-        if (!(xh = xs_domain_open()))
+    if (!xh) {
+        handlers = slist_init(_xen_destroy_callback);
+        if (handlers == NULL)
+            return -1;
+
+        if (!(xh = xs_domain_open())) {
             AGENT_LOG("Failed to connect to Xen Store: %s", strerror(errno));
+            slist_deinit(handlers);
+        }
+    }
     return xh ? 0 : -1;
 }
 
@@ -68,6 +91,8 @@
                        const char *data) {
     token_callback_tuple *cb;
 
+    assert(xh != NULL); /* make sure xen_init() was called */
+
     if (!(cb = malloc(sizeof(token_callback_tuple)))) {
         AGENT_LOG("malloc: %s", strerror(errno));
         return -1;
@@ -88,7 +113,7 @@
 
     cb->callback = callback;
 
-    if (!(handlers = slist_append(handlers, cb))) {
+    if (slist_append(handlers, cb) == NULL) {
         AGENT_LOG0("Failed to append callback to handler list.");
         free(cb->token);
         free(cb);
@@ -171,10 +196,12 @@
 
 void xen_fire_callback(const char *path, const char *token, void *buf,
                             unsigned int buflen) {
-    SList *ptr;
+    SListElem *elem;
 
-    for (ptr = handlers; ptr; ptr=ptr->next) {
-        token_callback_tuple *t = (token_callback_tuple *) ptr->data;
+    for (elem = slist_first(handlers);
+             elem != NULL;
+             elem = slist_next(handlers, elem)) {
+        token_callback_tuple *t = (token_callback_tuple *)slist_data(elem);
         if (strcmp(token, t->token) == 0) {
             t->callback(path, buf, buflen, t->token);
             break;

=== modified file 'tests/check_slist.c'
--- tests/check_slist.c	2010-07-07 09:26:52 +0000
+++ tests/check_slist.c	2010-08-25 08:06:08 +0000
@@ -15,28 +15,119 @@
  */
 #include <stdlib.h>
 #include <check.h>
+#include <assert.h>
 #include "../src/slist.h"
 
 START_TEST(test_slist_append)
 {
-	SList *list = NULL;
 	char *testdata[] = { "foo", "bar", "baz" };
-
-	list = slist_append(list, (void *) testdata[0]);
-	fail_unless(list->data == testdata[0], "element's data attribute not correctly set");
-	fail_unless(list->next == NULL, "element's next attribute not set to NULL");
-	list = slist_append(list, (void *) testdata[1]);
-	fail_unless(list->data == testdata[0], "element's data attribute not correctly set");
-	fail_unless(list->next != NULL, "element's next attribute set to NULL");
-	fail_unless(list->next->data == testdata[1], "element's data attribute not correctly set");
-	fail_unless(list->next->next == NULL, "element's next attribute not set to NULL");
-	list = slist_append(list, (void *) testdata[2]);
-	fail_unless(list->data == testdata[0], "element's data attribute not correctly set");
-	fail_unless(list->next != NULL, "element's next attribute set to NULL");
-	fail_unless(list->next->data == testdata[1], "element's data attribute not correctly set");
-	fail_unless(list->next->next != NULL, "element's next attribute set to NULL");
-	fail_unless(list->next->next->data == testdata[2], "element's data attribute not correctly set");
-	fail_unless(list->next->next->next == NULL, "element's next attribute not set to NULL");
+	SList *list = NULL;
+	SListElem *elem;
+	SListElem *elem1;
+	SListElem *elem2;
+	SListElem *elem2_2;
+	SListElem *elem3;
+
+        fail_unless((list = slist_init(NULL)) != NULL, "initing failed");
+
+	fail_unless(slist_append(list, (void *) testdata[0]) != NULL, "appending failed");
+
+        fail_unless((elem = slist_first(list)) != NULL, "couldn't get first elem");
+
+	fail_unless(slist_last(list) == elem, "last element is not same as first element");
+
+	fail_unless(slist_data(elem) == testdata[0], "element's data attribute not correctly set");
+	fail_unless(slist_next(list, elem) == NULL, "next element is not NULL");
+	fail_unless(slist_prev(list, elem) == NULL, "prev element is not NULL");
+
+	fail_unless((elem2 = slist_append(list, (void *)testdata[1])) != NULL);
+
+        fail_unless((elem1 = slist_first(list)) != NULL, "couldn't get first elem");
+
+        fail_unless((elem1 == elem), "first element doesn't match original first element");
+
+	fail_unless(slist_data(elem) == testdata[0], "first element's data attribute not correctly set");
+
+	fail_unless(slist_next(list, elem) == elem2, "1st element's next ptr is not 2nd element");
+	fail_unless(slist_prev(list, elem) == NULL, "1st element's prev ptr is not NULL");
+	fail_unless(slist_prev(list, elem2) == elem, "2nd element's prev ptr is not 1st element");
+	fail_unless(slist_next(list, elem2) == NULL, "2nd element's next ptr is not NULL");
+	fail_unless(slist_last(list) == elem2, "last element is not same as 2nd element");
+
+	fail_unless(slist_data(elem2) == testdata[1], "2nd element's data attribute not correctly set");
+
+	fail_unless((elem3 = slist_append(list, (void *)testdata[2])) != NULL);
+
+        fail_unless((elem1 = slist_first(list)) != NULL, "couldn't get first elem");
+
+        fail_unless((elem1 == elem), "first element doesn't match original first element");
+
+        fail_unless((elem2_2 = slist_next(list, elem1)) != NULL, "couldn't get 2nd elem");
+
+        fail_unless((elem2_2 == elem2), "2nd element doesn't match original 2nd element");
+
+	fail_unless(slist_data(elem) == testdata[0], "first element's data attribute not correctly set");
+
+	fail_unless(slist_next(list, elem) == elem2, "1st element's next ptr is not 2nd element");
+	fail_unless(slist_prev(list, elem) == NULL, "1st element's prev ptr is not NULL");
+	fail_unless(slist_prev(list, elem2) == elem, "2nd element's prev ptr is not 1st element");
+	fail_unless(slist_next(list, elem2) == elem3, "2nd element's next ptr is not third element");
+	fail_unless(slist_prev(list, elem3) == elem2, "3rd element's prev ptr is not 2nd element");
+	fail_unless(slist_next(list, elem3) == NULL, "3rd element's next ptr is not NULL");
+	fail_unless(slist_last(list) == elem3, "last element is not same as 3rd element");
+
+	fail_unless(slist_data(elem3) == testdata[2], "3rd element's data attribute not correctly set");
+
+        slist_deinit(list);
+}
+END_TEST
+
+int destroy_cb_iter;
+char *destroy_cb_testdata[] = { "foo", "bar", "baz" };
+
+void _slist_destroy_cb(void *arg)
+{
+    switch(++destroy_cb_iter)
+    {
+        case 1:
+            assert(arg == destroy_cb_testdata[0]);
+            break;
+        case 2:
+            assert(arg == destroy_cb_testdata[1]);
+            break;
+        case 3:
+            assert(arg == destroy_cb_testdata[2]);
+            break;
+        case 4:
+            break;
+    }
+}
+
+START_TEST(test_slist_destroy_cb)
+{
+	SList *list = NULL;
+
+        destroy_cb_iter = 0;
+
+        fail_unless((list = slist_init(NULL)) != NULL, "initing failed");
+
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[0]) != NULL, "appending failed");
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[1]) != NULL, "appending failed");
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[2]) != NULL, "appending failed");
+
+        slist_deinit(list);
+
+        fail_unless(destroy_cb_iter == 0);
+
+        fail_unless((list = slist_init(_slist_destroy_cb)) != NULL, "initing failed");
+
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[0]) != NULL, "appending failed");
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[1]) != NULL, "appending failed");
+	fail_unless(slist_append(list, (void *) destroy_cb_testdata[2]) != NULL, "appending failed");
+
+        slist_deinit(list);
+
+        fail_unless(destroy_cb_iter == 3);
 }
 END_TEST
 
@@ -46,6 +137,7 @@
 
     TCase *tc_slist = tcase_create("slist");
     tcase_add_test(tc_slist, test_slist_append);
+    tcase_add_test(tc_slist, test_slist_destroy_cb);
     suite_add_tcase(s, tc_slist);
 
     return s;

=== modified file 'tests/check_spool.c'
--- tests/check_spool.c	2010-08-24 15:54:14 +0000
+++ tests/check_spool.c	2010-08-25 08:06:08 +0000
@@ -112,6 +112,7 @@
     FILE *fp;
 
     setenv("AGENT_MSG_SPOOL", testdir, 1);
+    fail_unless(spool_init() == 0, "Failed to init spool");
     fail_unless(spool_watch(spool_cb) == 0, "Failed to add watch.");
     spool_process_pending_events();
     fail_unless(spool_cb_called == 0, "Spool callback got called even though nothing had happened yet.");

=== modified file 'tests/mock_xenstore.c'
--- tests/mock_xenstore.c	2010-08-19 08:09:01 +0000
+++ tests/mock_xenstore.c	2010-08-25 08:06:08 +0000
@@ -24,6 +24,9 @@
 #include <sys/socket.h>
 
 struct xs_handle {
+    SList *xs_object_list;
+    SList *watches;
+    SList *pending_notifications;
     char *verification;
     char transactions;
     int clientfd;
@@ -46,10 +49,6 @@
     const char *token;
 };
 
-SList *xs_object_list = NULL;
-SList *watches = NULL;
-SList *pending_notifications = NULL;
-
 static int validate_xs_handle(struct xs_handle *h) {
     if (h && !strcmp(h->verification, "foo"))
         return 1;
@@ -75,6 +74,11 @@
         return NULL;
 
     struct xs_handle *retval = malloc(sizeof(struct xs_handle));
+
+    retval->watches = slist_init(NULL);
+    retval->xs_object_list = slist_init(NULL);
+    retval->pending_notifications = slist_init(NULL);
+
     retval->verification = strdup("foo");
     retval->transactions = 0;
 
@@ -112,21 +116,23 @@
 }
 
 bool xs_write(struct xs_handle *h, xs_transaction_t t, const char *path, const void *buf, unsigned int len) {
-    SList *ptr;
+    SListElem *ptr;
     struct xs_object *obj;
 
     if (!validate_xs_transaction(h, t))
         return 0;
 
-    for (ptr = watches; ptr; ptr=ptr->next) {
-        struct xs_path_watch *watch = (struct xs_path_watch *) ptr->data;
+    for (ptr = slist_first(h->watches);
+             ptr != NULL;
+             ptr = slist_next(h->watches, ptr)) {
+        struct xs_path_watch *watch = (struct xs_path_watch *)slist_data(ptr);
         if (strstr(path, watch->path) == path) {
             /* Either they must be identical or the triggering path be in a subdir of the watched path */
             if (strlen(path) == strlen(watch->path) || path[strlen(watch->path)] == '/') {
                 struct notification *n = (struct notification *) malloc(sizeof(struct notification));
                 n->path = path;
                 n->token = watch->token;
-                pending_notifications = slist_append(pending_notifications, n);
+                slist_append(h->pending_notifications, n);
                 /* We notify the client that there's some action */
                 if (write(h->libraryfd, "X", 1) < 1)
                     abort();
@@ -134,8 +140,10 @@
         }
     }
 
-    for (ptr = xs_object_list; ptr; ptr=ptr->next) {
-        obj = (struct xs_object *) ptr->data;
+    for (ptr = slist_first(h->xs_object_list);
+             ptr != NULL;
+             ptr = slist_next(h->xs_object_list, ptr)) {
+        obj = (struct xs_object *)slist_data(ptr);
         if (strcmp(obj->path, path) == 0) {
             obj->buflen = len;
             obj->buf = buf;
@@ -146,19 +154,21 @@
     obj->path = strdup(path);
     obj->buf = buf;
     obj->buflen = len;
-    xs_object_list = slist_append(xs_object_list, obj);
+    slist_append(h->xs_object_list, obj);
 
     return 1;
 }
 
 void *xs_read(struct xs_handle *h, xs_transaction_t t, const char *path, unsigned int *len) {
-    SList *ptr;
+    SListElem *ptr;
 
     if (!validate_xs_transaction(h, t))
         return 0;
 
-    for (ptr = xs_object_list; ptr; ptr=ptr->next) {
-        struct xs_object *obj = (struct xs_object *) ptr->data;
+    for (ptr = slist_first(h->xs_object_list);
+             ptr != NULL;
+             ptr = slist_next(h->xs_object_list, ptr)) {
+        struct xs_object *obj = (struct xs_object *)slist_data(ptr);
         if (strcmp(obj->path, path) == 0) {
             void *buf;
 
@@ -180,7 +190,7 @@
     watch = (struct xs_path_watch *) malloc(sizeof(struct xs_path_watch));
     watch->path = path;
     watch->token = token;
-    watches = slist_append(watches, watch);
+    slist_append(h->watches, watch);
 
     return 1;
 }
@@ -189,11 +199,12 @@
 
 char **xs_read_watch(struct xs_handle *h, unsigned int *num) {
     char **retval;
+    SListElem *elem;
 
     if (!validate_xs_handle(h))
         return NULL;
 
-    if (!pending_notifications) {
+    if ((elem = slist_first(h->pending_notifications)) == NULL) {
         if (nonblocking) {
             errno = EWOULDBLOCK;
             return NULL;
@@ -208,8 +219,8 @@
     }
 
     retval = (char **) malloc(sizeof(char *)*2);
-    *retval = strdup(((struct notification *) pending_notifications->data)->path);
-    *(retval + 1) = strdup(((struct notification *) pending_notifications->data)->token);
+    *retval = strdup(((struct notification *) slist_data(elem))->path);
+    *(retval + 1) = strdup(((struct notification *) slist_data(elem))->token);
     *num = 2;
 
     return retval;