Fix parallel build for lib/
authorMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Thu, 19 Jan 2012 15:24:17 +0000 (10:24 -0500)
committerMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Thu, 19 Jan 2012 15:24:17 +0000 (10:24 -0500)
When we have a dependency from a library on another library (with
LIBADD), we need to put the lib we depend on in another directory, and
build that directory prior to the current directory. This is what is
done in the http://sourceware.org/autobook/autobook/autobook_92.html
"11.5 Convenience Libraries" example.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
configure.ac
lib/Makefile.am
lib/prio_heap.c [deleted file]
lib/prio_heap/Makefile.am [new file with mode: 0644]
lib/prio_heap/prio_heap.c [new file with mode: 0644]

index 1e980b9b9aa2ce9bfe78363598699dbf601232ac..2241681c7ac7d90188a2e6c51a71322fac6ee2b0 100644 (file)
@@ -67,6 +67,7 @@ AC_CONFIG_FILES([
        formats/ctf/metadata/Makefile
        converter/Makefile
        lib/Makefile
+       lib/prio_heap/Makefile
        include/Makefile
        tests/Makefile
 ])
index ba24d21cb002c5788754fa6eac0d36133860145f..fccf9ab55da1ca7176e968c4f075110ff7bfbc49 100644 (file)
@@ -1,8 +1,8 @@
-AM_CFLAGS = $(PACKAGE_CFLAGS) -I$(top_srcdir)/include
+SUBDIRS = prio_heap .
 
-lib_LTLIBRARIES = libprio_heap.la libbabeltrace.la
+AM_CFLAGS = $(PACKAGE_CFLAGS) -I$(top_srcdir)/include
 
-libprio_heap_la_SOURCES = prio_heap.c
+lib_LTLIBRARIES = libbabeltrace.la
 
 libbabeltrace_la_SOURCES = babeltrace.c \
                           callbacks.c \
@@ -10,4 +10,4 @@ libbabeltrace_la_SOURCES = babeltrace.c \
 
 libbabeltrace_la_LIBADD = \
        $(top_builddir)/types/libbabeltrace_types.la \
-       $(top_builddir)/lib/libprio_heap.la
+       prio_heap/libprio_heap.la
diff --git a/lib/prio_heap.c b/lib/prio_heap.c
deleted file mode 100644 (file)
index a37e64c..0000000
+++ /dev/null
@@ -1,216 +0,0 @@
-/*
- * prio_heap.c
- *
- * Static-sized priority heap containing pointers. Based on CLRS,
- * chapter 6.
- *
- * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- */
-
-#include <babeltrace/prio_heap.h>
-#include <babeltrace/babeltrace-internal.h>
-#include <errno.h>
-#include <stdlib.h>
-#include <string.h>
-#include <assert.h>
-
-#ifndef max_t
-#define max_t(type, a, b)      \
-       ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
-#endif
-
-#ifdef DEBUG_HEAP
-void check_heap(const struct ptr_heap *heap)
-{
-       size_t i;
-
-       if (!heap->len)
-               return;
-
-       for (i = 1; i < heap->len; i++)
-               assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
-}
-#endif
-
-static
-size_t parent(size_t i)
-{
-       return (i - 1) >> 1;
-}
-
-static
-size_t left(size_t i)
-{
-       return (i << 1) + 1;
-}
-
-static
-size_t right(size_t i)
-{
-       return (i << 1) + 2;
-}
-
-/*
- * Copy of heap->ptrs pointer is invalid after heap_grow.
- */
-static
-int heap_grow(struct ptr_heap *heap, size_t new_len)
-{
-       void **new_ptrs;
-
-       if (likely(heap->alloc_len >= new_len))
-               return 0;
-
-       heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
-       new_ptrs = calloc(heap->alloc_len, sizeof(void *));
-       if (unlikely(!new_ptrs))
-               return -ENOMEM;
-       if (likely(heap->ptrs))
-               memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
-       free(heap->ptrs);
-       heap->ptrs = new_ptrs;
-       return 0;
-}
-
-static
-int heap_set_len(struct ptr_heap *heap, size_t new_len)
-{
-       int ret;
-
-       ret = heap_grow(heap, new_len);
-       if (unlikely(ret))
-               return ret;
-       heap->len = new_len;
-       return 0;
-}
-
-int heap_init(struct ptr_heap *heap, size_t alloc_len,
-             int gt(void *a, void *b))
-{
-       heap->ptrs = NULL;
-       heap->len = 0;
-       heap->alloc_len = 0;
-       heap->gt = gt;
-       /*
-        * Minimum size allocated is 1 entry to ensure memory allocation
-        * never fails within heap_replace_max.
-        */
-       return heap_grow(heap, max_t(size_t, 1, alloc_len));
-}
-
-void heap_free(struct ptr_heap *heap)
-{
-       free(heap->ptrs);
-}
-
-static void heapify(struct ptr_heap *heap, size_t i)
-{
-       void **ptrs = heap->ptrs;
-       size_t l, r, largest;
-
-       for (;;) {
-               void *tmp;
-
-               l = left(i);
-               r = right(i);
-               if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
-                       largest = l;
-               else
-                       largest = i;
-               if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
-                       largest = r;
-               if (unlikely(largest == i))
-                       break;
-               tmp = ptrs[i];
-               ptrs[i] = ptrs[largest];
-               ptrs[largest] = tmp;
-               i = largest;
-       }
-       check_heap(heap);
-}
-
-void *heap_replace_max(struct ptr_heap *heap, void *p)
-{
-       void *res;
-
-       if (unlikely(!heap->len)) {
-               (void) heap_set_len(heap, 1);
-               heap->ptrs[0] = p;
-               check_heap(heap);
-               return NULL;
-       }
-
-       /* Replace the current max and heapify */
-       res = heap->ptrs[0];
-       heap->ptrs[0] = p;
-       heapify(heap, 0);
-       return res;
-}
-
-int heap_insert(struct ptr_heap *heap, void *p)
-{
-       void **ptrs;
-       size_t pos;
-       int ret;
-
-       ret = heap_set_len(heap, heap->len + 1);
-       if (unlikely(ret))
-               return ret;
-       ptrs = heap->ptrs;
-       pos = heap->len - 1;
-       while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
-               /* Move parent down until we find the right spot */
-               ptrs[pos] = ptrs[parent(pos)];
-               pos = parent(pos);
-       }
-       ptrs[pos] = p;
-       check_heap(heap);
-       return 0;
-}
-
-void *heap_remove(struct ptr_heap *heap)
-{
-       switch (heap->len) {
-       case 0:
-               return NULL;
-       case 1:
-               (void) heap_set_len(heap, 0);
-               return heap->ptrs[0];
-       }
-       /* Shrink, replace the current max by previous last entry and heapify */
-       heap_set_len(heap, heap->len - 1);
-       /* len changed. previous last entry is at heap->len */
-       return heap_replace_max(heap, heap->ptrs[heap->len]);
-}
-
-void *heap_cherrypick(struct ptr_heap *heap, void *p)
-{
-       size_t pos, len = heap->len;
-
-       for (pos = 0; pos < len; pos++)
-               if (unlikely(heap->ptrs[pos] == p))
-                       goto found;
-       return NULL;
-found:
-       if (unlikely(heap->len == 1)) {
-               (void) heap_set_len(heap, 0);
-               check_heap(heap);
-               return heap->ptrs[0];
-       }
-       /* Replace p with previous last entry and heapify. */
-       heap_set_len(heap, heap->len - 1);
-       /* len changed. previous last entry is at heap->len */
-       heap->ptrs[pos] = heap->ptrs[heap->len];
-       heapify(heap, pos);
-       return p;
-}
diff --git a/lib/prio_heap/Makefile.am b/lib/prio_heap/Makefile.am
new file mode 100644 (file)
index 0000000..9561305
--- /dev/null
@@ -0,0 +1,5 @@
+AM_CFLAGS = $(PACKAGE_CFLAGS) -I$(top_srcdir)/include
+
+lib_LTLIBRARIES = libprio_heap.la
+
+libprio_heap_la_SOURCES = prio_heap.c
diff --git a/lib/prio_heap/prio_heap.c b/lib/prio_heap/prio_heap.c
new file mode 100644 (file)
index 0000000..a37e64c
--- /dev/null
@@ -0,0 +1,216 @@
+/*
+ * prio_heap.c
+ *
+ * Static-sized priority heap containing pointers. Based on CLRS,
+ * chapter 6.
+ *
+ * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ */
+
+#include <babeltrace/prio_heap.h>
+#include <babeltrace/babeltrace-internal.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#ifndef max_t
+#define max_t(type, a, b)      \
+       ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
+#endif
+
+#ifdef DEBUG_HEAP
+void check_heap(const struct ptr_heap *heap)
+{
+       size_t i;
+
+       if (!heap->len)
+               return;
+
+       for (i = 1; i < heap->len; i++)
+               assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
+}
+#endif
+
+static
+size_t parent(size_t i)
+{
+       return (i - 1) >> 1;
+}
+
+static
+size_t left(size_t i)
+{
+       return (i << 1) + 1;
+}
+
+static
+size_t right(size_t i)
+{
+       return (i << 1) + 2;
+}
+
+/*
+ * Copy of heap->ptrs pointer is invalid after heap_grow.
+ */
+static
+int heap_grow(struct ptr_heap *heap, size_t new_len)
+{
+       void **new_ptrs;
+
+       if (likely(heap->alloc_len >= new_len))
+               return 0;
+
+       heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
+       new_ptrs = calloc(heap->alloc_len, sizeof(void *));
+       if (unlikely(!new_ptrs))
+               return -ENOMEM;
+       if (likely(heap->ptrs))
+               memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
+       free(heap->ptrs);
+       heap->ptrs = new_ptrs;
+       return 0;
+}
+
+static
+int heap_set_len(struct ptr_heap *heap, size_t new_len)
+{
+       int ret;
+
+       ret = heap_grow(heap, new_len);
+       if (unlikely(ret))
+               return ret;
+       heap->len = new_len;
+       return 0;
+}
+
+int heap_init(struct ptr_heap *heap, size_t alloc_len,
+             int gt(void *a, void *b))
+{
+       heap->ptrs = NULL;
+       heap->len = 0;
+       heap->alloc_len = 0;
+       heap->gt = gt;
+       /*
+        * Minimum size allocated is 1 entry to ensure memory allocation
+        * never fails within heap_replace_max.
+        */
+       return heap_grow(heap, max_t(size_t, 1, alloc_len));
+}
+
+void heap_free(struct ptr_heap *heap)
+{
+       free(heap->ptrs);
+}
+
+static void heapify(struct ptr_heap *heap, size_t i)
+{
+       void **ptrs = heap->ptrs;
+       size_t l, r, largest;
+
+       for (;;) {
+               void *tmp;
+
+               l = left(i);
+               r = right(i);
+               if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
+                       largest = l;
+               else
+                       largest = i;
+               if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
+                       largest = r;
+               if (unlikely(largest == i))
+                       break;
+               tmp = ptrs[i];
+               ptrs[i] = ptrs[largest];
+               ptrs[largest] = tmp;
+               i = largest;
+       }
+       check_heap(heap);
+}
+
+void *heap_replace_max(struct ptr_heap *heap, void *p)
+{
+       void *res;
+
+       if (unlikely(!heap->len)) {
+               (void) heap_set_len(heap, 1);
+               heap->ptrs[0] = p;
+               check_heap(heap);
+               return NULL;
+       }
+
+       /* Replace the current max and heapify */
+       res = heap->ptrs[0];
+       heap->ptrs[0] = p;
+       heapify(heap, 0);
+       return res;
+}
+
+int heap_insert(struct ptr_heap *heap, void *p)
+{
+       void **ptrs;
+       size_t pos;
+       int ret;
+
+       ret = heap_set_len(heap, heap->len + 1);
+       if (unlikely(ret))
+               return ret;
+       ptrs = heap->ptrs;
+       pos = heap->len - 1;
+       while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
+               /* Move parent down until we find the right spot */
+               ptrs[pos] = ptrs[parent(pos)];
+               pos = parent(pos);
+       }
+       ptrs[pos] = p;
+       check_heap(heap);
+       return 0;
+}
+
+void *heap_remove(struct ptr_heap *heap)
+{
+       switch (heap->len) {
+       case 0:
+               return NULL;
+       case 1:
+               (void) heap_set_len(heap, 0);
+               return heap->ptrs[0];
+       }
+       /* Shrink, replace the current max by previous last entry and heapify */
+       heap_set_len(heap, heap->len - 1);
+       /* len changed. previous last entry is at heap->len */
+       return heap_replace_max(heap, heap->ptrs[heap->len]);
+}
+
+void *heap_cherrypick(struct ptr_heap *heap, void *p)
+{
+       size_t pos, len = heap->len;
+
+       for (pos = 0; pos < len; pos++)
+               if (unlikely(heap->ptrs[pos] == p))
+                       goto found;
+       return NULL;
+found:
+       if (unlikely(heap->len == 1)) {
+               (void) heap_set_len(heap, 0);
+               check_heap(heap);
+               return heap->ptrs[0];
+       }
+       /* Replace p with previous last entry and heapify. */
+       heap_set_len(heap, heap->len - 1);
+       /* len changed. previous last entry is at heap->len */
+       heap->ptrs[pos] = heap->ptrs[heap->len];
+       heapify(heap, pos);
+       return p;
+}
This page took 0.04332 seconds and 4 git commands to generate.