foreach \
grab_file \
hash \
+ heap \
htable \
idtree \
ilog \
* order (almost everyone else).
*
* This module provides conversion routines, inspired by the linux kernel.
+ * It also provides leint32_t, beint32_t etc typedefs, which are annotated for
+ * the sparse checker.
*
* Example:
* #include <stdio.h>
#error "Can't compile for both big and little endian."
#endif
+#ifdef __CHECKER__
+/* sparse needs forcing to remove bitwise attribute from ccan/short_types */
+#define ENDIAN_CAST __attribute__((force))
+#define ENDIAN_TYPE __attribute__((bitwise))
+#else
+#define ENDIAN_CAST
+#define ENDIAN_TYPE
+#endif
+
+typedef uint64_t ENDIAN_TYPE leint64_t;
+typedef uint64_t ENDIAN_TYPE beint64_t;
+typedef uint32_t ENDIAN_TYPE leint32_t;
+typedef uint32_t ENDIAN_TYPE beint32_t;
+typedef uint16_t ENDIAN_TYPE leint16_t;
+typedef uint16_t ENDIAN_TYPE beint16_t;
+
#if HAVE_LITTLE_ENDIAN
/**
* CPU_TO_LE64 - convert a constant uint64_t value to little-endian
* @native: constant to convert
*/
-#define CPU_TO_LE64(native) (native)
+#define CPU_TO_LE64(native) ((ENDIAN_CAST leint64_t)(native))
/**
* CPU_TO_LE32 - convert a constant uint32_t value to little-endian
* @native: constant to convert
*/
-#define CPU_TO_LE32(native) (native)
+#define CPU_TO_LE32(native) ((ENDIAN_CAST leint32_t)(native))
/**
* CPU_TO_LE16 - convert a constant uint16_t value to little-endian
* @native: constant to convert
*/
-#define CPU_TO_LE16(native) (native)
+#define CPU_TO_LE16(native) ((ENDIAN_CAST leint16_t)(native))
/**
* LE64_TO_CPU - convert a little-endian uint64_t constant
* @le_val: little-endian constant to convert
*/
-#define LE64_TO_CPU(le_val) (le_val)
+#define LE64_TO_CPU(le_val) ((ENDIAN_CAST uint64_t)(le_val))
/**
* LE32_TO_CPU - convert a little-endian uint32_t constant
* @le_val: little-endian constant to convert
*/
-#define LE32_TO_CPU(le_val) (le_val)
+#define LE32_TO_CPU(le_val) ((ENDIAN_CAST uint32_t)(le_val))
/**
* LE16_TO_CPU - convert a little-endian uint16_t constant
* @le_val: little-endian constant to convert
*/
-#define LE16_TO_CPU(le_val) (le_val)
+#define LE16_TO_CPU(le_val) ((ENDIAN_CAST uint16_t)(le_val))
#else /* ... HAVE_BIG_ENDIAN */
-#define CPU_TO_LE64(native) BSWAP_64(native)
-#define CPU_TO_LE32(native) BSWAP_32(native)
-#define CPU_TO_LE16(native) BSWAP_16(native)
-#define LE64_TO_CPU(le_val) BSWAP_64(le_val)
-#define LE32_TO_CPU(le_val) BSWAP_32(le_val)
-#define LE16_TO_CPU(le_val) BSWAP_16(le_val)
+#define CPU_TO_LE64(native) ((ENDIAN_CAST leint64_t)BSWAP_64(native))
+#define CPU_TO_LE32(native) ((ENDIAN_CAST leint32_t)BSWAP_32(native))
+#define CPU_TO_LE16(native) ((ENDIAN_CAST leint16_t)BSWAP_16(native))
+#define LE64_TO_CPU(le_val) BSWAP_64((ENDIAN_CAST uint64_t)le_val)
+#define LE32_TO_CPU(le_val) BSWAP_32((ENDIAN_CAST uint32_t)le_val)
+#define LE16_TO_CPU(le_val) BSWAP_16((ENDIAN_CAST uint16_t)le_val)
#endif /* HAVE_BIG_ENDIAN */
#if HAVE_BIG_ENDIAN
* CPU_TO_BE64 - convert a constant uint64_t value to big-endian
* @native: constant to convert
*/
-#define CPU_TO_BE64(native) (native)
+#define CPU_TO_BE64(native) ((ENDIAN_CAST beint64_t)(native))
/**
* CPU_TO_BE32 - convert a constant uint32_t value to big-endian
* @native: constant to convert
*/
-#define CPU_TO_BE32(native) (native)
+#define CPU_TO_BE32(native) ((ENDIAN_CAST beint32_t)(native))
/**
* CPU_TO_BE16 - convert a constant uint16_t value to big-endian
* @native: constant to convert
*/
-#define CPU_TO_BE16(native) (native)
+#define CPU_TO_BE16(native) ((ENDIAN_CAST beint16_t)(native))
/**
* BE64_TO_CPU - convert a big-endian uint64_t constant
* @le_val: big-endian constant to convert
*/
-#define BE64_TO_CPU(le_val) (le_val)
+#define BE64_TO_CPU(le_val) ((ENDIAN_CAST uint64_t)(le_val))
/**
* BE32_TO_CPU - convert a big-endian uint32_t constant
* @le_val: big-endian constant to convert
*/
-#define BE32_TO_CPU(le_val) (le_val)
+#define BE32_TO_CPU(le_val) ((ENDIAN_CAST uint32_t)(le_val))
/**
* BE16_TO_CPU - convert a big-endian uint16_t constant
* @le_val: big-endian constant to convert
*/
-#define BE16_TO_CPU(le_val) (le_val)
+#define BE16_TO_CPU(le_val) ((ENDIAN_CAST uint16_t)(le_val))
#else /* ... HAVE_LITTLE_ENDIAN */
-#define CPU_TO_BE64(native) BSWAP_64(native)
-#define CPU_TO_BE32(native) BSWAP_32(native)
-#define CPU_TO_BE16(native) BSWAP_16(native)
-#define BE64_TO_CPU(le_val) BSWAP_64(le_val)
-#define BE32_TO_CPU(le_val) BSWAP_32(le_val)
-#define BE16_TO_CPU(le_val) BSWAP_16(le_val)
+#define CPU_TO_BE64(native) ((ENDIAN_CAST beint64_t)BSWAP_64(native))
+#define CPU_TO_BE32(native) ((ENDIAN_CAST beint32_t)BSWAP_32(native))
+#define CPU_TO_BE16(native) ((ENDIAN_CAST beint16_t)BSWAP_16(native))
+#define BE64_TO_CPU(le_val) BSWAP_64((ENDIAN_CAST uint64_t)le_val)
+#define BE32_TO_CPU(le_val) BSWAP_32((ENDIAN_CAST uint32_t)le_val)
+#define BE16_TO_CPU(le_val) BSWAP_16((ENDIAN_CAST uint16_t)le_val)
#endif /* HAVE_LITTE_ENDIAN */
* cpu_to_le64 - convert a uint64_t value to little-endian
* @native: value to convert
*/
-static inline uint64_t cpu_to_le64(uint64_t native)
+static inline leint64_t cpu_to_le64(uint64_t native)
{
return CPU_TO_LE64(native);
}
* cpu_to_le32 - convert a uint32_t value to little-endian
* @native: value to convert
*/
-static inline uint32_t cpu_to_le32(uint32_t native)
+static inline leint32_t cpu_to_le32(uint32_t native)
{
return CPU_TO_LE32(native);
}
* cpu_to_le16 - convert a uint16_t value to little-endian
* @native: value to convert
*/
-static inline uint16_t cpu_to_le16(uint16_t native)
+static inline leint16_t cpu_to_le16(uint16_t native)
{
return CPU_TO_LE16(native);
}
* le64_to_cpu - convert a little-endian uint64_t value
* @le_val: little-endian value to convert
*/
-static inline uint64_t le64_to_cpu(uint64_t le_val)
+static inline uint64_t le64_to_cpu(leint64_t le_val)
{
return LE64_TO_CPU(le_val);
}
* le32_to_cpu - convert a little-endian uint32_t value
* @le_val: little-endian value to convert
*/
-static inline uint32_t le32_to_cpu(uint32_t le_val)
+static inline uint32_t le32_to_cpu(leint32_t le_val)
{
return LE32_TO_CPU(le_val);
}
* le16_to_cpu - convert a little-endian uint16_t value
* @le_val: little-endian value to convert
*/
-static inline uint16_t le16_to_cpu(uint16_t le_val)
+static inline uint16_t le16_to_cpu(leint16_t le_val)
{
return LE16_TO_CPU(le_val);
}
* cpu_to_be64 - convert a uint64_t value to big endian.
* @native: value to convert
*/
-static inline uint64_t cpu_to_be64(uint64_t native)
+static inline beint64_t cpu_to_be64(uint64_t native)
{
+ return ((ENDIAN_CAST beint64_t)BSWAP_64(native));
return CPU_TO_BE64(native);
}
* cpu_to_be32 - convert a uint32_t value to big endian.
* @native: value to convert
*/
-static inline uint32_t cpu_to_be32(uint32_t native)
+static inline beint32_t cpu_to_be32(uint32_t native)
{
return CPU_TO_BE32(native);
}
* cpu_to_be16 - convert a uint16_t value to big endian.
* @native: value to convert
*/
-static inline uint16_t cpu_to_be16(uint16_t native)
+static inline beint16_t cpu_to_be16(uint16_t native)
{
return CPU_TO_BE16(native);
}
* be64_to_cpu - convert a big-endian uint64_t value
* @be_val: big-endian value to convert
*/
-static inline uint64_t be64_to_cpu(uint64_t be_val)
+static inline uint64_t be64_to_cpu(beint64_t be_val)
{
return BE64_TO_CPU(be_val);
}
* be32_to_cpu - convert a big-endian uint32_t value
* @be_val: big-endian value to convert
*/
-static inline uint32_t be32_to_cpu(uint32_t be_val)
+static inline uint32_t be32_to_cpu(beint32_t be_val)
{
return BE32_TO_CPU(be_val);
}
* be16_to_cpu - convert a big-endian uint16_t value
* @be_val: big-endian value to convert
*/
-static inline uint16_t be16_to_cpu(uint16_t be_val)
+static inline uint16_t be16_to_cpu(beint16_t be_val)
{
return BE16_TO_CPU(be_val);
}
+/* Whichever they include first, they get these definitions. */
+#ifdef CCAN_SHORT_TYPES_H
+/**
+ * be64/be32/be16 - 64/32/16 bit big-endian representation.
+ */
+typedef beint64_t be64;
+typedef beint32_t be32;
+typedef beint16_t be16;
+
+/**
+ * le64/le32/le16 - 64/32/16 bit little-endian representation.
+ */
+typedef leint64_t le64;
+typedef leint32_t le32;
+typedef leint16_t le16;
+#endif
#endif /* CCAN_ENDIAN_H */
--- /dev/null
+../../licenses/BSD-MIT
\ No newline at end of file
--- /dev/null
+#include <string.h>
+#include "config.h"
+
+/**
+ * heap - a simple heap implementation
+ *
+ * Each heap entry is added as a void pointer. This means the implementation
+ * does _not_ assume you already have an array of entries. Instead, it keeps
+ * an internal array of pointers to those entries.
+ *
+ * Example:
+ * #include <stdio.h>
+ *
+ * #include <ccan/heap/heap.h>
+ *
+ * static bool less(const int *i, const int *j)
+ * {
+ * return *i < *j;
+ * }
+ *
+ * static bool __less(const void *i, const void *j)
+ * {
+ * return less(i, j);
+ * }
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * struct heap *h;
+ * int arr[] = {1, 0, 2};
+ * int i;
+ *
+ * h = heap_init(__less);
+ * if (h == NULL) {
+ * perror("heap alloc");
+ * exit(1);
+ * }
+ *
+ * for (i = 0; i < 3; i++) {
+ * if (heap_push(h, &arr[i])) {
+ * perror("heap push");
+ * exit(1);
+ * }
+ * }
+ * // should print 0, 1, 2
+ * for (i = 0; i < 3; i++) {
+ * int *v = heap_pop(h);
+ * printf("%d\n", *v);
+ * }
+ * heap_free(h);
+ * return 0;
+ * }
+ *
+ * License: BSD-MIT
+ * Author: Emilio G. Cota <cota@braap.org>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
--- /dev/null
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#include <ccan/heap/heap.h>
+
+/*
+ * Allocating memory in chunks greater than needed does not yield measurable
+ * speedups of the test program when linking against glibc 2.15.
+ *
+ * When the data array has to be shrunk though, limiting calls to realloc
+ * does help a little bit (~7% speedup), hence the following parameter.
+ */
+#define HEAP_MEM_HYSTERESIS 4096
+
+static inline void swap(struct heap *h, size_t i, size_t j)
+{
+ void *foo = h->data[i];
+
+ h->data[i] = h->data[j];
+ h->data[j] = foo;
+}
+
+static void __up(struct heap *h, size_t j)
+{
+ size_t i; /* parent */
+
+ while (j) {
+ i = (j - 1) / 2;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ j = i;
+ } else {
+ break;
+ }
+ }
+}
+
+int heap_push(struct heap *h, void *data)
+{
+ if (h->len == h->cap) {
+ void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
+ if (m == NULL)
+ return -1;
+ h->data = m;
+ h->cap++;
+ }
+ h->data[h->len++] = data;
+ __up(h, h->len - 1);
+ return 0;
+}
+
+static void __down(struct heap *h, size_t i)
+{
+ size_t l, r, j; /* left, right, min child */
+
+ while (1) {
+ l = 2 * i + 1;
+ if (l >= h->len)
+ break;
+ r = l + 1;
+ if (r >= h->len)
+ j = l;
+ else
+ j = h->less(h->data[l], h->data[r]) ? l : r;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ i = j;
+ } else {
+ break;
+ }
+ }
+}
+
+void *heap_pop(struct heap *h)
+{
+ void *ret = h->data[0];
+ void *m;
+
+ swap(h, 0, --h->len);
+ if (h->len) {
+ __down(h, 0);
+ if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
+ m = realloc(h->data, h->len * sizeof(void *));
+ if (m == NULL)
+ return NULL;
+ h->data = m;
+ h->cap = h->len;
+ }
+ }
+
+ return ret;
+}
+
+struct heap *heap_init(heap_less_func_t less)
+{
+ struct heap *heap = calloc(1, sizeof(*heap));
+
+ if (heap == NULL)
+ return NULL;
+ heap->less = less;
+ return heap;
+}
+
+void heap_ify(struct heap *h, heap_less_func_t less)
+{
+ int i;
+
+ if (less)
+ h->less = less;
+
+ for (i = h->len / 2 - 1; i >= 0; i--)
+ __down(h, i);
+}
+
+void heap_free(struct heap *heap)
+{
+ free(heap->data);
+ free(heap);
+}
--- /dev/null
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_HEAP_H
+#define CCAN_HEAP_H
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef bool (*heap_less_func_t)(const void *, const void *);
+
+/**
+ * struct heap - a simple, generic heap structure
+ * @data: array of pointers to the heap's entries
+ * @less: function to compare heap entries
+ * @cap: capacity of the heap array in @data
+ * @len: number of valid elements in the heap array
+ *
+ * The @less function determines the nature of the heap. If @less is
+ * something akin to 'return a.foo < b.foo', then the heap will be
+ * a min heap. Conversely, a '>' predicate will result in a max heap.
+ *
+ * Elements in the @data array are allocated as needed, hence the need for
+ * @cap and @len.
+ */
+struct heap {
+ void **data;
+ heap_less_func_t less;
+ size_t cap;
+ size_t len;
+};
+
+/**
+ * heap_init - allocate and initialise an empty heap
+ * @less: function to be used to compare heap entries
+ *
+ * Returns a pointer to an initialised heap struct on success, NULL if
+ * the heap could not be allocated.
+ *
+ * See also: HEAP_INIT()
+ */
+struct heap *heap_init(heap_less_func_t less);
+
+/**
+ * HEAP_INIT - initialiser for an empty heap
+ * @func: comparison function to be used in the heap
+ *
+ * Explicit initialiser for a heap.
+ *
+ * See also: heap_init()
+ */
+#define HEAP_INIT(func) { NULL, func, 0, 0 }
+
+/**
+ * heap_free - free a heap allocated via heap_init()
+ * @heap: the heap to be freed
+ *
+ * Note that this only frees the heap and its internal resources, not
+ * the entries pointed to by it.
+ *
+ * See also: heap_init()
+ */
+void heap_free(struct heap *heap);
+
+/**
+ * heap_ify - enforce the heap property based on a new comparison function
+ * @h: heap to be heapified
+ * @less: new comparison function
+ *
+ * Complexity: O(n)
+ */
+void heap_ify(struct heap *h, heap_less_func_t less);
+
+/**
+ * heap_push - push a new heap entry
+ * @h: heap to receive the new entry
+ * @data: pointer to the new entry
+ *
+ * Returns 0 on success, -1 on error.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_pop()
+ */
+int heap_push(struct heap *h, void *data);
+
+/**
+ * heap_pop - pops the root heap entry
+ * @h: heap to pop the head from
+ *
+ * Returns the root entry of the heap after extracting it, or NULL on error.
+ *
+ * Note: Calling heap_pop() on an empty heap is a bug--don't do it.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_push(), heap_peek()
+ */
+void *heap_pop(struct heap *h);
+
+/**
+ * heap_peek - inspect the root entry of a heap
+ * @h: heap whose root entry is to be inspected
+ *
+ * Returns the root entry in the heap, without extracting it from @h.
+ *
+ * Note: Calling heap_peek() on an empty heap is a bug--don't do it.
+ *
+ * See also: heap_pop()
+ */
+static inline void *heap_peek(const struct heap *h)
+{
+ return h->data[0];
+}
+
+#endif /* CCAN_HEAP_H */
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+
+#include <ccan/heap/heap.h>
+/* Include the C files directly. */
+#include <ccan/heap/heap.c>
+#include <ccan/tap/tap.h>
+
+struct item {
+ void *foobar;
+ int v;
+};
+
+static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
+{
+ int l, r;
+
+ l = 2 * i + 1;
+ r = l + 1;
+
+ if (l < h->len) {
+ if (less(h->data[l], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, l))
+ return false;
+ }
+ if (r < h->len) {
+ if (less(h->data[r], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, r))
+ return false;
+ }
+ return true;
+}
+
+static bool less(const struct item *a, const struct item *b)
+{
+ return a->v < b->v;
+}
+
+static bool __less(const void *a, const void *b)
+{
+ return less(a, b);
+}
+
+static bool more(const struct item *a, const struct item *b)
+{
+ return a->v > b->v;
+}
+
+static bool __more(const void *a, const void *b)
+{
+ return more(a, b);
+}
+
+static bool some_test(size_t n, bool is_less)
+{
+ struct item *items = calloc(n, sizeof(*items));
+ struct item *item, *prev;
+ struct heap *h;
+ int i;
+
+ if (items == NULL) {
+ perror("items");
+ exit(EXIT_FAILURE);
+ }
+
+ if (is_less)
+ h = heap_init(__less);
+ else
+ h = heap_init(__more);
+ if (h == NULL) {
+ perror("heap_init");
+ exit(EXIT_FAILURE);
+ }
+
+ for (i = 0; i < n; i++) {
+ item = &items[i];
+
+ item->v = rand();
+ printf("pushing %d\n", item->v);
+ heap_push(h, item);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ }
+ if (is_less) {
+ heap_ify(h, __more);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ heap_ify(h, __less);
+ if (!heap_ok(h, __less, 0))
+ return false;
+ } else {
+ heap_ify(h, NULL);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ }
+
+ for (i = 0; i < n; i++) {
+ item = heap_pop(h);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ printf("popped %d\n", item->v);
+ if (i > 0) {
+ if (is_less) {
+ if (less(item, prev))
+ return false;
+ } else {
+ if (more(item, prev))
+ return false;
+ }
+ }
+ prev = item;
+ }
+ heap_free(h);
+ free(items);
+ return true;
+}
+
+int main(void)
+{
+ plan_tests(3);
+
+ ok1(some_test(5000, true));
+ ok1(some_test(1, true));
+ ok1(some_test(33, false));
+
+ return exit_status();
+}
-../../licenses/LGPL-2.1
\ No newline at end of file
+../../licenses/CC0
\ No newline at end of file
* ilog - Integer logarithm.
*
* ilog_32() and ilog_64() compute the minimum number of bits required to store
- * an unsigned 32-bit or 64-bit value without any leading zero bits.
+ * an unsigned 32-bit or 64-bit value without any leading zero bits.
+ *
* This can also be thought of as the location of the highest set bit, with
- * counting starting from one (so that 0 returns 0, 1 returns 1, and 2**31
- * returns 32).
+ * counting starting from one (so that 0 returns 0, 1 returns 1, and 2**31
+ * returns 32).
+ *
* When the value is known to be non-zero ilog32_nz() and ilog64_nz() can
- * compile into as few as two instructions, one of which may get optimized out
- * later.
+ * compile into as few as two instructions, one of which may get optimized out
+ * later.
+ *
* STATIC_ILOG_32 and STATIC_ILOG_64 allow computation on compile-time
- * constants, so other compile-time constants can be derived from them.
+ * constants, so other compile-time constants can be derived from them.
*
* Example:
* #include <stdio.h>
* return 0;
* }
*
- * License: LGPL (v2.1 or any later version)
+ * License: CC0 (Public domain)
* Author: Timothy B. Terriberry <tterribe@xiph.org>
*/
#include <string.h>
-/*(C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 LGPL (v2 or later).
+/*(C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 CC0 (Public domain).
* See LICENSE file for details. */
#include "ilog.h"
#include <limits.h>
-/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+/* CC0 (Public domain) - see LICENSE file for details */
#if !defined(_ilog_H)
# define _ilog_H (1)
# include "config.h"
#define list_for_each_safe(h, i, nxt, member) \
list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))
+/**
+ * list_next - get the next entry in a list
+ * @h: the list_head
+ * @i: a pointer to an entry in the list.
+ * @member: the list_node member of the structure
+ *
+ * If @i was the last entry in the list, returns NULL.
+ *
+ * Example:
+ * struct child *second;
+ * second = list_next(&parent->children, first, list);
+ * if (!second)
+ * printf("No second child!\n");
+ */
+#define list_next(h, i, member) \
+ ((list_typeof(i))list_entry_or_null(list_debug(h), \
+ (i)->member.next, \
+ list_off_var_((i), member)))
+
+/**
+ * list_prev - get the previous entry in a list
+ * @h: the list_head
+ * @i: a pointer to an entry in the list.
+ * @member: the list_node member of the structure
+ *
+ * If @i was the first entry in the list, returns NULL.
+ *
+ * Example:
+ * first = list_prev(&parent->children, second, list);
+ * if (!first)
+ * printf("Can't go back to first child?!\n");
+ */
+#define list_prev(h, i, member) \
+ ((list_typeof(i))list_entry_or_null(list_debug(h), \
+ (i)->member.prev, \
+ list_off_var_((i), member)))
+
/**
* list_append_list - empty one list onto the end of another.
* @to: the list to append into
(container_off_var(var, member) + \
check_type(var->member, struct list_node))
+#if HAVE_TYPEOF
+#define list_typeof(var) typeof(var)
+#else
+#define list_typeof(var) void *
+#endif
+
+/* Returns member, or NULL if at end of list. */
+static inline void *list_entry_or_null(struct list_head *h,
+ struct list_node *n,
+ size_t off)
+{
+ if (n == &h->n)
+ return NULL;
+ return (char *)n - off;
+}
#endif /* CCAN_LIST_H */
--- /dev/null
+#include <ccan/list/list.h>
+#include <ccan/tap/tap.h>
+#include <ccan/list/list.c>
+#include "helper.h"
+
+struct parent {
+ const char *name;
+ unsigned int num_children;
+ struct list_head children;
+};
+
+struct child {
+ const char *name;
+ struct list_node list;
+};
+
+int main(int argc, char *argv[])
+{
+ struct parent parent;
+ struct child c1, c2, c3;
+
+ plan_tests(12);
+ parent.num_children = 0;
+ list_head_init(&parent.children);
+
+ c1.name = "c1";
+ list_add(&parent.children, &c1.list);
+
+ ok1(list_next(&parent.children, &c1, list) == NULL);
+ ok1(list_prev(&parent.children, &c1, list) == NULL);
+
+ c2.name = "c2";
+ list_add_tail(&parent.children, &c2.list);
+
+ ok1(list_next(&parent.children, &c1, list) == &c2);
+ ok1(list_prev(&parent.children, &c1, list) == NULL);
+ ok1(list_next(&parent.children, &c2, list) == NULL);
+ ok1(list_prev(&parent.children, &c2, list) == &c1);
+
+ c3.name = "c3";
+ list_add_tail(&parent.children, &c3.list);
+
+ ok1(list_next(&parent.children, &c1, list) == &c2);
+ ok1(list_prev(&parent.children, &c1, list) == NULL);
+ ok1(list_next(&parent.children, &c2, list) == &c3);
+ ok1(list_prev(&parent.children, &c2, list) == &c1);
+ ok1(list_next(&parent.children, &c3, list) == NULL);
+ ok1(list_prev(&parent.children, &c3, list) == &c2);
+ return exit_status();
+}
* -- Linus Torvalds
*
* The short_types header provides for convenient abbreviations for the
- * posixly-damned uint32_t types. It also provides be32/le32 for explicitly
- * annotating types of specific endian.
+ * posixly-damned uint32_t types. If ccan/endian/endian.h is included,
+ * it also provides be32/le32 for explicitly annotating types of specific
+ * endian.
*
* Include this header, if only to stop people using these identifiers
* for other things!
return 0;
}
+ if (strcmp(argv[1], "testdepends") == 0) {
+ printf("ccan/endian\n");
+ return 0;
+ }
+
return 1;
}
typedef uint8_t u8;
typedef int8_t s8;
+/* Whichever they include first, they get these definitions. */
+#ifdef CCAN_ENDIAN_H
/**
* be64/be32/be16 - 64/32/16 bit big-endian representation.
*/
-typedef uint64_t be64;
-typedef uint32_t be32;
-typedef uint16_t be16;
+typedef beint64_t be64;
+typedef beint32_t be32;
+typedef beint16_t be16;
/**
* le64/le32/le16 - 64/32/16 bit little-endian representation.
*/
-typedef uint64_t le64;
-typedef uint32_t le32;
-typedef uint16_t le16;
+typedef leint64_t le64;
+typedef leint32_t le32;
+typedef leint16_t le16;
+#endif
#endif /* CCAN_SHORT_TYPES_H */
--- /dev/null
+#include <ccan/endian/endian.h>
+#include <ccan/short_types/short_types.h>
+#include <ccan/tap/tap.h>
+#include <stdlib.h>
+#include <err.h>
+
+int main(int argc, char *argv[])
+{
+ plan_tests(6);
+
+ ok1(sizeof(be64) == 8);
+ ok1(sizeof(be32) == 4);
+ ok1(sizeof(be16) == 2);
+
+ ok1(sizeof(le64) == 8);
+ ok1(sizeof(le32) == 4);
+ ok1(sizeof(le16) == 2);
+
+ return exit_status();
+}
int main(int argc, char *argv[])
{
- plan_tests(22);
+ plan_tests(16);
ok1(sizeof(u64) == 8);
ok1(sizeof(s64) == 8);
ok1(sizeof(u8) == 1);
ok1(sizeof(s8) == 1);
- ok1(sizeof(be64) == 8);
- ok1(sizeof(be32) == 4);
- ok1(sizeof(be16) == 2);
-
- ok1(sizeof(le64) == 8);
- ok1(sizeof(le32) == 4);
- ok1(sizeof(le16) == 2);
-
/* Signedness tests. */
ok1((u64)-1 > 0);
ok1((u32)-1 > 0);
return from_tal_hdr(ignore_destroying_bit(t->parent_child)->parent);
}
-bool tal_resize_(tal_t **ctxp, size_t size, size_t count)
+bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear)
{
struct tal_hdr *old_t, *t;
struct children *child;
struct prop_hdr **lenp;
struct length len;
- size_t extra = 0;
+ size_t extra = 0, elemsize = size;
old_t = debug_tal(to_tal_hdr(*ctxp));
/* Copy here, in case we're shrinking! */
len = *(struct length *)*lenp;
extra = extra_for_length(size);
- }
+ } else /* If we don't have an old length, we can't clear! */
+ assert(!clear);
t = resizefn(old_t, sizeof(struct tal_hdr) + size + extra);
if (!t) {
if (lenp) {
struct length *new_len;
+ /* Clear between old end and new end. */
+ if (clear && count > len.count) {
+ char *old_end = (char *)(t + 1) + len.count * elemsize;
+ memset(old_end, 0, elemsize * (count - len.count));
+ }
+
new_len = (struct length *)((char *)(t + 1) + size);
len.count = count;
*new_len = len;
assert(src < *ctxp
|| (char *)src >= (char *)(*ctxp) + (size * old_count));
- if (!tal_resize_(ctxp, size, old_count + count))
+ if (!tal_resize_(ctxp, size, old_count + count, false))
goto out;
memcpy((char *)*ctxp + size * old_count, src, count * size);
if (taken(p)) {
if (unlikely(!p))
return NULL;
- if (unlikely(!tal_resize_((void **)&p, size, n + extra)))
+ if (unlikely(!tal_resize_((void **)&p, size, n + extra, false)))
return tal_free(p);
if (unlikely(!tal_steal(ctx, p)))
return tal_free(p);
* tal_resize(&p, 100);
*/
#define tal_resize(p, count) \
- tal_resize_((void **)(p), sizeof**(p), (count))
+ tal_resize_((void **)(p), sizeof**(p), (count), false)
+
+/**
+ * tal_resizez - enlarge or reduce a tal_arr[z]; zero out extra.
+ * @p: A pointer to the tal allocated array to resize.
+ * @count: the number to allocate.
+ *
+ * This returns true on success (and may move *@p), or false on failure.
+ * If @p has a length property, it is updated on success.
+ * On expand, new elements are memset to 0 bytes.
+ *
+ * Example:
+ * tal_resizez(&p, 200);
+ */
+#define tal_resizez(p, count) \
+ tal_resize_((void **)(p), sizeof**(p), (count), true)
/**
* tal_steal - change the parent of a tal-allocated pointer.
tal_t *tal_steal_(const tal_t *new_parent, const tal_t *t);
-bool tal_resize_(tal_t **ctxp, size_t size, size_t count);
+bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear);
bool tal_expand_(tal_t **ctxp, const void *src, size_t size, size_t count);
bool tal_add_destructor_(const tal_t *ctx, void (*destroy)(void *me));
strcpy(c[0], "hello");
tal_free(c[0]);
ok1(tal_first(parent) == NULL);
+
tal_free(parent);
tal_cleanup();
--- /dev/null
+#include <ccan/tal/tal.h>
+#include <ccan/tal/tal.c>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+ char *parent, *c;
+ int i;
+
+ plan_tests(1 + 3 * 100 + 98);
+
+ parent = tal(NULL, char);
+ ok1(parent);
+
+ for (i = 0; i < 100; i++) {
+ c = tal_arr(parent, char, 1);
+ ok1(tal_resizez(&c, i));
+ ok1(tal_count(c) == i);
+ ok1(tal_parent(c) == parent);
+ if (i > 1)
+ ok1(c[i-1] == '\0');
+ }
+ tal_free(parent);
+
+ tal_cleanup();
+ return exit_status();
+}
projects / ccan / commitdiff