From 1bbf06e94150d938ea45f0b8ed237fadad7efbc7 Mon Sep 17 00:00:00 2001
From: Ondřej Surý <ondrej@sury.org>
Date: Wed, 14 Nov 2012 14:03:41 +0100
Subject: Imported Upstream version 1.1.2~rc1

---
 src/common/LICENSE.txt         |  0
 src/common/acl.c               |  0
 src/common/acl.h               |  0
 src/common/base32.c            |  0
 src/common/base32.h            |  0
 src/common/base32hex.c         |  0
 src/common/base32hex.h         |  0
 src/common/base64.c            |  0
 src/common/base64.h            |  0
 src/common/crc.h               |  0
 src/common/dSFMT-params.h      |  0
 src/common/dSFMT-params521.h   |  0
 src/common/dSFMT.c             |  0
 src/common/dSFMT.h             |  0
 src/common/errcode.c           |  0
 src/common/errcode.h           |  0
 src/common/errors.c            |  0
 src/common/errors.h            |  0
 src/common/evqueue.c           |  0
 src/common/evqueue.h           |  0
 src/common/evsched.c           | 25 ++++++++++---------
 src/common/evsched.h           |  0
 src/common/fdset.c             |  0
 src/common/fdset.h             |  0
 src/common/fdset_epoll.c       |  0
 src/common/fdset_epoll.h       |  0
 src/common/fdset_kqueue.c      |  0
 src/common/fdset_kqueue.h      |  0
 src/common/fdset_poll.c        |  0
 src/common/fdset_poll.h        |  0
 src/common/general-tree.c      |  0
 src/common/general-tree.h      |  0
 src/common/heap.c              | 56 +++++++++++++++++++-----------------------
 src/common/heap.h              | 11 ++++-----
 src/common/latency.c           |  0
 src/common/latency.h           |  0
 src/common/libtap/README       |  0
 src/common/libtap/tap.c        |  0
 src/common/libtap/tap.h        |  0
 src/common/libtap/tap_unit.h   |  0
 src/common/lists.c             |  0
 src/common/lists.h             |  0
 src/common/log.c               |  0
 src/common/log.h               |  0
 src/common/mempattern.c        |  0
 src/common/mempattern.h        |  0
 src/common/modified_tree.h     |  0
 src/common/print.c             |  0
 src/common/print.h             |  0
 src/common/prng.c              |  0
 src/common/prng.h              |  0
 src/common/ref.c               |  0
 src/common/ref.h               |  0
 src/common/skip-list.c         |  0
 src/common/skip-list.h         |  0
 src/common/slab/alloc-common.h |  0
 src/common/slab/slab.c         |  0
 src/common/slab/slab.h         |  0
 src/common/sockaddr.c          |  0
 src/common/sockaddr.h          |  0
 src/common/tree.h              |  0
 61 files changed, 44 insertions(+), 48 deletions(-)
 mode change 100644 => 100755 src/common/LICENSE.txt
 mode change 100644 => 100755 src/common/acl.c
 mode change 100644 => 100755 src/common/acl.h
 mode change 100644 => 100755 src/common/base32.c
 mode change 100644 => 100755 src/common/base32.h
 mode change 100644 => 100755 src/common/base32hex.c
 mode change 100644 => 100755 src/common/base32hex.h
 mode change 100644 => 100755 src/common/base64.c
 mode change 100644 => 100755 src/common/base64.h
 mode change 100644 => 100755 src/common/crc.h
 mode change 100644 => 100755 src/common/dSFMT-params.h
 mode change 100644 => 100755 src/common/dSFMT-params521.h
 mode change 100644 => 100755 src/common/dSFMT.c
 mode change 100644 => 100755 src/common/dSFMT.h
 mode change 100644 => 100755 src/common/errcode.c
 mode change 100644 => 100755 src/common/errcode.h
 mode change 100644 => 100755 src/common/errors.c
 mode change 100644 => 100755 src/common/errors.h
 mode change 100644 => 100755 src/common/evqueue.c
 mode change 100644 => 100755 src/common/evqueue.h
 mode change 100644 => 100755 src/common/evsched.c
 mode change 100644 => 100755 src/common/evsched.h
 mode change 100644 => 100755 src/common/fdset.c
 mode change 100644 => 100755 src/common/fdset.h
 mode change 100644 => 100755 src/common/fdset_epoll.c
 mode change 100644 => 100755 src/common/fdset_epoll.h
 mode change 100644 => 100755 src/common/fdset_kqueue.c
 mode change 100644 => 100755 src/common/fdset_kqueue.h
 mode change 100644 => 100755 src/common/fdset_poll.c
 mode change 100644 => 100755 src/common/fdset_poll.h
 mode change 100644 => 100755 src/common/general-tree.c
 mode change 100644 => 100755 src/common/general-tree.h
 mode change 100644 => 100755 src/common/heap.c
 mode change 100644 => 100755 src/common/heap.h
 mode change 100644 => 100755 src/common/latency.c
 mode change 100644 => 100755 src/common/latency.h
 mode change 100644 => 100755 src/common/libtap/README
 mode change 100644 => 100755 src/common/libtap/tap.c
 mode change 100644 => 100755 src/common/libtap/tap.h
 mode change 100644 => 100755 src/common/libtap/tap_unit.h
 mode change 100644 => 100755 src/common/lists.c
 mode change 100644 => 100755 src/common/lists.h
 mode change 100644 => 100755 src/common/log.c
 mode change 100644 => 100755 src/common/log.h
 mode change 100644 => 100755 src/common/mempattern.c
 mode change 100644 => 100755 src/common/mempattern.h
 mode change 100644 => 100755 src/common/modified_tree.h
 mode change 100644 => 100755 src/common/print.c
 mode change 100644 => 100755 src/common/print.h
 mode change 100644 => 100755 src/common/prng.c
 mode change 100644 => 100755 src/common/prng.h
 mode change 100644 => 100755 src/common/ref.c
 mode change 100644 => 100755 src/common/ref.h
 mode change 100644 => 100755 src/common/skip-list.c
 mode change 100644 => 100755 src/common/skip-list.h
 mode change 100644 => 100755 src/common/slab/alloc-common.h
 mode change 100644 => 100755 src/common/slab/slab.c
 mode change 100644 => 100755 src/common/slab/slab.h
 mode change 100644 => 100755 src/common/sockaddr.c
 mode change 100644 => 100755 src/common/sockaddr.h
 mode change 100644 => 100755 src/common/tree.h

(limited to 'src/common')

diff --git a/src/common/LICENSE.txt b/src/common/LICENSE.txt
old mode 100644
new mode 100755
diff --git a/src/common/acl.c b/src/common/acl.c
old mode 100644
new mode 100755
diff --git a/src/common/acl.h b/src/common/acl.h
old mode 100644
new mode 100755
diff --git a/src/common/base32.c b/src/common/base32.c
old mode 100644
new mode 100755
diff --git a/src/common/base32.h b/src/common/base32.h
old mode 100644
new mode 100755
diff --git a/src/common/base32hex.c b/src/common/base32hex.c
old mode 100644
new mode 100755
diff --git a/src/common/base32hex.h b/src/common/base32hex.h
old mode 100644
new mode 100755
diff --git a/src/common/base64.c b/src/common/base64.c
old mode 100644
new mode 100755
diff --git a/src/common/base64.h b/src/common/base64.h
old mode 100644
new mode 100755
diff --git a/src/common/crc.h b/src/common/crc.h
old mode 100644
new mode 100755
diff --git a/src/common/dSFMT-params.h b/src/common/dSFMT-params.h
old mode 100644
new mode 100755
diff --git a/src/common/dSFMT-params521.h b/src/common/dSFMT-params521.h
old mode 100644
new mode 100755
diff --git a/src/common/dSFMT.c b/src/common/dSFMT.c
old mode 100644
new mode 100755
diff --git a/src/common/dSFMT.h b/src/common/dSFMT.h
old mode 100644
new mode 100755
diff --git a/src/common/errcode.c b/src/common/errcode.c
old mode 100644
new mode 100755
diff --git a/src/common/errcode.h b/src/common/errcode.h
old mode 100644
new mode 100755
diff --git a/src/common/errors.c b/src/common/errors.c
old mode 100644
new mode 100755
diff --git a/src/common/errors.h b/src/common/errors.h
old mode 100644
new mode 100755
diff --git a/src/common/evqueue.c b/src/common/evqueue.c
old mode 100644
new mode 100755
diff --git a/src/common/evqueue.h b/src/common/evqueue.h
old mode 100644
new mode 100755
diff --git a/src/common/evsched.c b/src/common/evsched.c
old mode 100644
new mode 100755
index 8b6f721..9bfdef0
--- a/src/common/evsched.c
+++ b/src/common/evsched.c
@@ -26,15 +26,18 @@
 #define OPENBSD_SLAB_BROKEN
 #endif
 
-/* Heap only cares about x<y. */
-static int compare_event_heap_nodes(event_t **e1, event_t **e2)
+/*! \brief Some implementations of timercmp >= are broken, this is for compat.*/
+static inline int timercmp_ge(struct timeval *a, struct timeval *b) {
+	return timercmp(a, b, >) || timercmp(a, b, ==);
+}
+
+static int compare_event_heap_nodes(event_t *e1, event_t *e2)
 {
-	if (timercmp(&(*e1)->tv, &(*e2)->tv, <)) return -1;
-	if (timercmp(&(*e1)->tv, &(*e2)->tv, >)) return 1;
+	if (timercmp(&e1->tv, &e2->tv, <)) return -1;
+	if (timercmp(&e1->tv, &e2->tv, >)) return 1;
 	return 0;
 }
 
-
 /*!
  * \brief Set event timer to T (now) + dt miliseconds.
  */
@@ -78,7 +81,7 @@ evsched_t *evsched_new()
 #ifndef OPENBSD_SLAB_BROKEN
 	slab_cache_init(&s->cache.alloc, sizeof(event_t));
 #endif
-	heap_init(&s->heap, sizeof(event_t *), compare_event_heap_nodes, 0, NULL);
+	heap_init(&s->heap, compare_event_heap_nodes, 0);
 	return s;
 }
 
@@ -179,7 +182,7 @@ event_t* evsched_next(evsched_t *s)
 			event_t *next_ev = *((event_t**)HHEAD(&s->heap));
 
 			/* Immediately return. */
-			if (timercmp(&dt, &next_ev->tv, >=)) {
+			if (timercmp_ge(&dt, &next_ev->tv)) {
 				s->current = next_ev;
 				heap_delmin(&s->heap);
 				pthread_mutex_unlock(&s->mx);
@@ -235,10 +238,10 @@ int evsched_schedule(evsched_t *s, event_t *ev, uint32_t dt)
 	/* Lock calendar. */
 	pthread_mutex_lock(&s->mx);
 	
-	heap_insert(&s->heap, &ev);
+	heap_insert(&s->heap, ev);
 
 	/* Unlock calendar. */
-	pthread_cond_signal(&s->notify);
+	pthread_cond_broadcast(&s->notify);
 	pthread_mutex_unlock(&s->mx);
 
 	return 0;
@@ -302,12 +305,12 @@ int evsched_cancel(evsched_t *s, event_t *ev)
 	/* Lock calendar. */
 	pthread_mutex_lock(&s->mx);
 
-	if ((found = heap_find(&s->heap, &ev))) {
+	if ((found = heap_find(&s->heap, ev))) {
 		heap_delete(&s->heap, found);
 	}
 
 	/* Unlock calendar. */
-	pthread_cond_signal(&s->notify);
+	pthread_cond_broadcast(&s->notify);
 	pthread_mutex_unlock(&s->mx);
 
 	/* Enable running events. */
diff --git a/src/common/evsched.h b/src/common/evsched.h
old mode 100644
new mode 100755
diff --git a/src/common/fdset.c b/src/common/fdset.c
old mode 100644
new mode 100755
diff --git a/src/common/fdset.h b/src/common/fdset.h
old mode 100644
new mode 100755
diff --git a/src/common/fdset_epoll.c b/src/common/fdset_epoll.c
old mode 100644
new mode 100755
diff --git a/src/common/fdset_epoll.h b/src/common/fdset_epoll.h
old mode 100644
new mode 100755
diff --git a/src/common/fdset_kqueue.c b/src/common/fdset_kqueue.c
old mode 100644
new mode 100755
diff --git a/src/common/fdset_kqueue.h b/src/common/fdset_kqueue.h
old mode 100644
new mode 100755
diff --git a/src/common/fdset_poll.c b/src/common/fdset_poll.c
old mode 100644
new mode 100755
diff --git a/src/common/fdset_poll.h b/src/common/fdset_poll.h
old mode 100644
new mode 100755
diff --git a/src/common/general-tree.c b/src/common/general-tree.c
old mode 100644
new mode 100755
diff --git a/src/common/general-tree.h b/src/common/general-tree.h
old mode 100644
new mode 100755
diff --git a/src/common/heap.c b/src/common/heap.c
old mode 100644
new mode 100755
index 6fefb11..27b82da
--- a/src/common/heap.c
+++ b/src/common/heap.c
@@ -22,11 +22,8 @@
  *
  * Most macros use these parameters:
  *
- * - @type - the type of elements
  * - @num - a variable (signed or unsigned integer) with the number of elements
  * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
- * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
- * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
  *
  * A valid heap must follow these rules:
  *
@@ -44,26 +41,23 @@
 #include <string.h>
 #include <stdlib.h>
 
-void _def_swap(struct heap *h, void *e1, void *e2)
+static inline void heap_swap(heap_val_t *e1, heap_val_t *e2)
 {
-	if (e1 == e2) return;
-	void *tmp = HTEMPELEMENT(h);
-	memcpy(tmp, e1, h->elm_size);
-	memcpy(e1, e2, h->elm_size);
-	memcpy(e2, tmp, h->elm_size);
+	if (e1 == e2) return; /* Stack tmp should be faster than tmpelem. */
+	heap_val_t tmp = *e1; /* Even faster than 2-XOR nowadays. */
+	*e1 = *e2;
+	*e2 = tmp;
 }
 
 
-int heap_init(struct heap *h, int elm_size, int (*cmp)(void *, void *), int init_size, void (*swap)(struct heap *, void *, void *))
+int heap_init(struct heap *h, int (*cmp)(void *, void *), int init_size)
 {
 	int isize = init_size ? init_size : INITIAL_HEAP_SIZE;
 
 	h->num = 0;
 	h->max_size = isize;
 	h->cmp = cmp;
-	h->swap = swap ? swap : _def_swap;
-	h->data = malloc((isize + 1) * elm_size);
-	h->elm_size = elm_size;
+	h->data = malloc((isize + 1) * sizeof(heap_val_t)); /* Temp element unused. */
 
 	return h->data ? 1 : 0;
 };
@@ -75,9 +69,9 @@ static inline void _heap_bubble_down(struct heap *h, int e)
 	{
 		e1 = 2*e;
 		if(e1 > h->num) break;
-		if((h->cmp(HELEMENT(h, e),HELEMENT(h,e1)) < 0) && (e1 == h->num || (h->cmp(HELEMENT(h, e),HELEMENT(h,e1+1)) < 0))) break;
-		if((e1 != h->num) && (h->cmp(HELEMENT(h, e1+1), HELEMENT(h,e1)) < 0)) e1++;
-		h->swap(h,HELEMENT(h,e),HELEMENT(h,e1));
+		if((h->cmp(*HELEMENT(h, e),*HELEMENT(h,e1)) < 0) && (e1 == h->num || (h->cmp(*HELEMENT(h, e),*HELEMENT(h,e1+1)) < 0))) break;
+		if((e1 != h->num) && (h->cmp(*HELEMENT(h, e1+1), *HELEMENT(h,e1)) < 0)) e1++;
+		heap_swap(HELEMENT(h,e),HELEMENT(h,e1));
 		e = e1;
 	}
 }
@@ -88,8 +82,8 @@ static inline void _heap_bubble_up(struct heap *h, int e)
 	while (e > 1)
 	{
 		e1 = e/2;
-		if(h->cmp(HELEMENT(h, e1),HELEMENT(h,e)) < 0) break;
-		h->swap(h,HELEMENT(h,e),HELEMENT(h,e1));
+		if(h->cmp(*HELEMENT(h, e1),*HELEMENT(h,e)) < 0) break;
+		heap_swap(HELEMENT(h,e),HELEMENT(h,e1));
 		e = e1;
 	}
 		
@@ -100,7 +94,7 @@ void heap_delmin(struct heap *h)
 	if(h->num == 0) return;
 	if(h->num > 1)
 	{
-		h->swap(h,HHEAD(h),HELEMENT(h,h->num));
+		heap_swap(HHEAD(h),HELEMENT(h,h->num));
 	}
 	--h->num;
 	_heap_bubble_down(h, 1);
@@ -111,39 +105,39 @@ int heap_insert(struct heap *h, void *e)
 	if(h->num == h->max_size)
 	{
 		h->max_size = h->max_size * HEAP_INCREASE_STEP;
-		h->data = realloc(h->data, (h->max_size + 1) * h->elm_size);
+		h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t));
 	}
 
 	h->num++;
-	memcpy(HELEMENT(h,h->num),e,h->elm_size);
+	*HELEMENT(h,h->num) = e;
 	_heap_bubble_up(h,h->num);
 
-	return h->data ? 1 :0 ;
+	return h->data ? 1 : 0;
 }
 
 int heap_find(struct heap *h, void *elm)	/* FIXME - very slow */
 {
-	int i = h->num;
-
-	while(i > 0)
+	int i = 1; /* Skip tmp element. */
+	int np = h->num + 1; /* Start from min-heap top. */
+	while(i != np)
 	{
-		if(h->cmp(HELEMENT(h, i),elm) == 0) break;
-		--i;
+		if(*HELEMENT(h, i) == elm) return i;
+		++i;
 	}
-	return i;
+	return 0;
 }
 
 void heap_delete(struct heap *h, int e)
 {
-	h->swap(h, HELEMENT(h, e), HELEMENT(h, h->num));
+	heap_swap(HELEMENT(h, e), HELEMENT(h, h->num));
 	h->num--;
-	if(h->cmp(HELEMENT(h, e), HELEMENT(h, h->num + 1)) < 0) _heap_bubble_up(h, e);
+	if(h->cmp(*HELEMENT(h, e), *HELEMENT(h, h->num + 1)) < 0) _heap_bubble_up(h, e);
 	else _heap_bubble_down(h, e);
 
 	if ((h->num > INITIAL_HEAP_SIZE) && (h->num < h->max_size / HEAP_DECREASE_THRESHOLD))
 	{
 		h->max_size = h->max_size / HEAP_INCREASE_STEP;
-		h->data = realloc(h->data, (h->max_size + 1) * h->elm_size);
+		h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t));
 	}
 }
 
diff --git a/src/common/heap.h b/src/common/heap.h
old mode 100644
new mode 100755
index d6f8a0b..6fe355c
--- a/src/common/heap.h
+++ b/src/common/heap.h
@@ -28,24 +28,23 @@
 #ifndef _HEAP_H_
 #define _HEAP_H_
 
+typedef void* heap_val_t;
+
 struct heap {
    int num;		/* Number of elements */
-   int elm_size;	/* Size of a single element */
    int max_size;	/* Size of allocated memory */
    int (*cmp)(void *, void *);
-   void (*swap)(struct heap *, void *, void *);
-   void *data;
+   heap_val_t *data;
 };		/* Array follows */
 
 #define INITIAL_HEAP_SIZE 512 /* initial heap size */
 #define HEAP_INCREASE_STEP 2  /* multiplier for each inflation, keep conservative */
 #define HEAP_DECREASE_THRESHOLD 2 /* threshold for deflation, keep conservative */
-#define HTEMPELEMENT(h) ((h)->data)			/* Pointer to tmp element (for swap) */
-#define HELEMENT(h,num) ((char*)(h)->data + (num) * (h)->elm_size)
+#define HELEMENT(h,num) ((h)->data + (num)) 
 #define HHEAD(h) HELEMENT((h),1)
 #define EMPTY_HEAP(h) ((h)->num == 0)			/* h->num == 0 */
 
-int heap_init(struct heap *, int, int (*cmp)(), int, void (*swap)());
+int heap_init(struct heap *, int (*cmp)(), int);
 void heap_delmin(struct heap *);
 int heap_insert(struct heap *, void *);
 int heap_find(struct heap *, void *);
diff --git a/src/common/latency.c b/src/common/latency.c
old mode 100644
new mode 100755
diff --git a/src/common/latency.h b/src/common/latency.h
old mode 100644
new mode 100755
diff --git a/src/common/libtap/README b/src/common/libtap/README
old mode 100644
new mode 100755
diff --git a/src/common/libtap/tap.c b/src/common/libtap/tap.c
old mode 100644
new mode 100755
diff --git a/src/common/libtap/tap.h b/src/common/libtap/tap.h
old mode 100644
new mode 100755
diff --git a/src/common/libtap/tap_unit.h b/src/common/libtap/tap_unit.h
old mode 100644
new mode 100755
diff --git a/src/common/lists.c b/src/common/lists.c
old mode 100644
new mode 100755
diff --git a/src/common/lists.h b/src/common/lists.h
old mode 100644
new mode 100755
diff --git a/src/common/log.c b/src/common/log.c
old mode 100644
new mode 100755
diff --git a/src/common/log.h b/src/common/log.h
old mode 100644
new mode 100755
diff --git a/src/common/mempattern.c b/src/common/mempattern.c
old mode 100644
new mode 100755
diff --git a/src/common/mempattern.h b/src/common/mempattern.h
old mode 100644
new mode 100755
diff --git a/src/common/modified_tree.h b/src/common/modified_tree.h
old mode 100644
new mode 100755
diff --git a/src/common/print.c b/src/common/print.c
old mode 100644
new mode 100755
diff --git a/src/common/print.h b/src/common/print.h
old mode 100644
new mode 100755
diff --git a/src/common/prng.c b/src/common/prng.c
old mode 100644
new mode 100755
diff --git a/src/common/prng.h b/src/common/prng.h
old mode 100644
new mode 100755
diff --git a/src/common/ref.c b/src/common/ref.c
old mode 100644
new mode 100755
diff --git a/src/common/ref.h b/src/common/ref.h
old mode 100644
new mode 100755
diff --git a/src/common/skip-list.c b/src/common/skip-list.c
old mode 100644
new mode 100755
diff --git a/src/common/skip-list.h b/src/common/skip-list.h
old mode 100644
new mode 100755
diff --git a/src/common/slab/alloc-common.h b/src/common/slab/alloc-common.h
old mode 100644
new mode 100755
diff --git a/src/common/slab/slab.c b/src/common/slab/slab.c
old mode 100644
new mode 100755
diff --git a/src/common/slab/slab.h b/src/common/slab/slab.h
old mode 100644
new mode 100755
diff --git a/src/common/sockaddr.c b/src/common/sockaddr.c
old mode 100644
new mode 100755
diff --git a/src/common/sockaddr.h b/src/common/sockaddr.h
old mode 100644
new mode 100755
diff --git a/src/common/tree.h b/src/common/tree.h
old mode 100644
new mode 100755
-- 
cgit v1.2.3