From bf139664aa2ae9956b520ba4813bb6e03bf1a3e8 Mon Sep 17 00:00:00 2001 From: Ondrej Zajicek Date: Tue, 10 Sep 2013 12:09:36 +0200 Subject: Initial BFD commit, work in progress. --- lib/buffer.h | 35 +++++++++++++ lib/hash.h | 83 ++++++++++++++++++++++++++++++ lib/heap.h | 156 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/lists.c | 21 ++++++++ lib/resource.c | 29 ++++++++--- lib/socket.h | 2 + 6 files changed, 318 insertions(+), 8 deletions(-) create mode 100644 lib/buffer.h create mode 100644 lib/hash.h create mode 100644 lib/heap.h (limited to 'lib') diff --git a/lib/buffer.h b/lib/buffer.h new file mode 100644 index 00000000..cf073e88 --- /dev/null +++ b/lib/buffer.h @@ -0,0 +1,35 @@ + +#define BUFFER(type) struct { type *data; uint used, size; } + +#define BUFFER_SIZE(v) ((v).size * sizeof(* (v).data)) + +#define BUFFER_INIT(v,pool,isize) \ + ({ \ + (v).used = 0; \ + (v).size = (isize); \ + (v).data = mb_alloc(pool, BUFFER_SIZE(v)); \ + }) + +#define BUFFER_SET(v,nsize) \ + ({ \ + (v).used = (nsize); \ + if ((v).used > (v).size) \ + buffer_realloc((void **) &((v).data), &((v).size), (v).used, sizeof(* (v).data)); \ + }) + +#define BUFFER_INC(v,step) \ + ({ \ + uint _o = (v).used; \ + BUFFER_SET(v, (v).used + (step)); \ + (v).data + _o; \ + }) + +#define BUFFER_DEC(v,step) ({ (v).used -= (step); }) + +#define BUFFER_PUSH(v) (*BUFFER_INC(v,1)) + +#define BUFFER_POP(v) BUFFER_DEC(v,1) + +#define BUFFER_FLUSH(v) ({ (v).used = 0; }) + + diff --git a/lib/hash.h b/lib/hash.h new file mode 100644 index 00000000..7464f140 --- /dev/null +++ b/lib/hash.h @@ -0,0 +1,83 @@ + + +#define HASH(type) struct { type **data; uint used, size; } +#define HASH_TYPE(v) typeof(** (v).data) +#define HASH_SIZE(v) ((v).size * sizeof(* (v).data)) + +#define HASH_INIT(v,pool,isize) \ + ({ \ + (v).used = 0; \ + (v).size = (isize); \ + (v).data = mb_allocz(pool, HASH_SIZE(v)); \ + }) + +#define HASH_FIND(v,id,key) \ + ({ \ + HASH_TYPE(v) *_n = (v).data[id##_FN(key, (v).size)]; \ + while (_n && !id##_EQ(_n, key)) \ + _n = _n->id##_NEXT; \ + _n; \ + }) + +#define HASH_INSERT(v,id,key,node) \ + ({ \ + HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size); \ + node->id##_NEXT = *_nn; \ + *_nn = node; \ + }) + +#define HASH_DELETE(v,id,key) \ + ({ \ + HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size); \ + while ((*_nn) && !id##_EQ(*_nn, key)) \ + _nn = &((*_nn)->id##_NEXT); \ + \ + HASH_TYPE(v) *_n = *_nn; \ + if (_n) \ + *_nn = _n->id##_NEXT; \ + _n; \ + }) + +#define HASH_REMOVE(v,id,node) \ + ({ \ + HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size); \ + while ((*_nn) && (*_nn != (node))) \ + _nn = &((*_nn)->id##_NEXT); \ + \ + HASH_TYPE(v) *_n = *_nn; \ + if (_n) \ + *_nn = _n->id##_NEXT; \ + _n; \ + }) + + + +#define HASH_WALK(v,next,n) \ + do { \ + HASH_TYPE(v) *n; \ + uint _i; \ + for (_i = 0; _i < ((v).size); _i++) \ + for (n = (v).data[_i]; n; n = n->next) + +#define HASH_WALK_END } while (0) + + +#define HASH_WALK_DELSAFE(v,next,n) \ + do { \ + HASH_TYPE(v) *n, *_next; \ + uint _i; \ + for (_i = 0; _i < ((v).size); _i++) \ + for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next) + +#define HASH_WALK_DELSAFE_END } while (0) + +/* +define HASH_REHASH(s) \ + ({ \ + type *_n; \ + uint _i; \ + for (_i = 0; _i < (size_f); _i++) \ + for (_n = (hash)[_i]; _n != NULL; _n = + +*/ + diff --git a/lib/heap.h b/lib/heap.h new file mode 100644 index 00000000..ecb9a1bd --- /dev/null +++ b/lib/heap.h @@ -0,0 +1,156 @@ +/* + * UCW Library -- Universal Heap Macros + * + * (c) 2001 Martin Mares + * (c) 2005 Tomas Valla + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/** + * [[intro]] + * Introduction + * ------------ + * + * Binary heap is a simple data structure, which for example supports efficient insertions, deletions + * and access to the minimal inserted item. We define several macros for such operations. + * Note that because of simplicity of heaps, we have decided to define direct macros instead + * of a <> as for several other data structures in the Libucw. + * + * A heap is represented by a number of elements and by an array of values. Beware that we + * index this array from one, not from zero as do the standard C arrays. + * + * 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: + * + * - `num >= 0` + * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]` + * + * The first element `heap[1]` is always lower or equal to all other elements. + * + * [[macros]] + * Macros + * ------ + */ + +/* For internal usage. */ +#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ + for (;;) \ + { \ + _l = 2*_j; \ + if (_l > num) \ + break; \ + if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1]))) \ + break; \ + if (_l != num && less(heap[_l+1],heap[_l])) \ + _l++; \ + swap(heap,_j,_l,x); \ + _j = _l; \ + } + +/* For internal usage. */ +#define HEAP_BUBBLE_UP_J(heap,num,less,swap) \ + while (_j > 1) \ + { \ + _u = _j/2; \ + if (less(heap[_u], heap[_j])) \ + break; \ + swap(heap,_u,_j,x); \ + _j = _u; \ + } + +/** + * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear. + **/ +#define HEAP_INIT(heap,num,type,less,swap) \ + do { \ + uns _i = num; \ + uns _j, _l; \ + type x; \ + while (_i >= 1) \ + { \ + _j = _i; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ + _i--; \ + } \ + } while(0) + +/** + * Delete the minimum element `heap[1]` in `O(log(n))` time. + * The removed value is moved just after the resulting heap (`heap[num + 1]`). + **/ +#define HEAP_DELMIN(heap,num,type,less,swap) \ + do { \ + uns _j, _l; \ + type x; \ + swap(heap,1,num,x); \ + num--; \ + _j = 1; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before. + **/ +#define HEAP_INSERT(heap,num,type,less,swap) \ + do { \ + uns _j, _u; \ + type x; \ + _j = num; \ + HEAP_BUBBLE_UP_J(heap,num,less,swap); \ + } while(0) + +/** + * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. + * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. + * The time complexity is `O(log(n))`. + **/ +#define HEAP_INCREASE(heap,num,type,less,swap,pos) \ + do { \ + uns _j, _l; \ + type x; \ + _j = pos; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. + * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. + * The time complexity is `O(log(n))`. + **/ +#define HEAP_DECREASE(heap,num,type,less,swap,pos) \ + do { \ + uns _j, _u; \ + type x; \ + _j = pos; \ + HEAP_BUBBLE_UP_J(heap,num,less,swap); \ + } while(0) + +/** + * Delete `heap[pos]` in `O(log(n))` time. + **/ +#define HEAP_DELETE(heap,num,type,less,swap,pos) \ + do { \ + uns _j, _l, _u; \ + type x; \ + _j = pos; \ + swap(heap,_j,num,x); \ + num--; \ + if (less(heap[_j], heap[num+1])) \ + HEAP_BUBBLE_UP_J(heap,num,less,swap) \ + else \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * Default swapping macro. + **/ +#define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t) diff --git a/lib/lists.c b/lib/lists.c index 6d97ff50..58ffd230 100644 --- a/lib/lists.c +++ b/lib/lists.c @@ -100,6 +100,27 @@ rem_node(node *n) x->prev = z; } +/** + * replace_node - replace a node in a list with another one + * @old: node to be removed + * @new: node to be inserted + * + * Replaces node @old in the list it's linked in with node @new. Node + * @old may be a copy of the original node, which is not accessed + * through the list. The function could be called with @old == @new, + * which just fixes neighbors' pointers in the case that the node + * was reallocated. + */ +LIST_INLINE void +replace_node(node *old, node *new) +{ + old->next->prev = new; + old->prev->next = new; + + new->prev = old->prev; + new->next = old->next; +} + /** * init_list - create an empty list * @l: list diff --git a/lib/resource.c b/lib/resource.c index 42243aa2..775b0c53 100644 --- a/lib/resource.c +++ b/lib/resource.c @@ -366,21 +366,21 @@ mb_allocz(pool *p, unsigned size) /** * mb_realloc - reallocate a memory block - * @p: pool * @m: memory block * @size: new size of the block * * mb_realloc() changes the size of the memory block @m to a given size. * The contents will be unchanged to the minimum of the old and new sizes; - * newly allocated memory will be uninitialized. If @m is NULL, the call - * is equivalent to mb_alloc(@p, @size). + * newly allocated memory will be uninitialized. Contrary to realloc() + * behavior, @m must be non-NULL, because the resource pool is inherited + * from it. * * Like mb_alloc(), mb_realloc() also returns a pointer to the memory - * chunk , not to the resource, hence you have to free it using + * chunk, not to the resource, hence you have to free it using * mb_free(), not rfree(). */ void * -mb_realloc(pool *p, void *m, unsigned size) +mb_realloc(void *m, unsigned size) { struct mblock *ob = NULL; @@ -392,9 +392,7 @@ mb_realloc(pool *p, void *m, unsigned size) } struct mblock *b = xrealloc(ob, sizeof(struct mblock) + size); - - b->r.class = &mb_class; - add_tail(&p->inside, &b->r.n); + replace_node(&b->r.n, &b->r.n); b->size = size; return b->data; } @@ -413,3 +411,18 @@ mb_free(void *m) rfree(b); } + + +#define STEP_UP(x) ((x) + (x)/2 + 4) + +void +buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size) +{ + unsigned nsize = MIN(*size, need); + + while (nsize < need) + nsize = STEP_UP(nsize); + + *buf = mb_realloc(*buf, nsize*isize); + *size = nsize; +} diff --git a/lib/socket.h b/lib/socket.h index 6e0a769b..780d596b 100644 --- a/lib/socket.h +++ b/lib/socket.h @@ -44,6 +44,7 @@ typedef struct birdsock { /* laddr and lifindex are valid only if SKF_LADDR_RX flag is set to request it */ int fd; /* System-dependent data */ + int index; /* Index in poll buffer */ node n; void *rbuf_alloc, *tbuf_alloc; char *password; /* Password for MD5 authentication */ @@ -91,6 +92,7 @@ extern int sk_priority_control; /* Suggested priority for control traffic, shoul #define SKF_LADDR_TX 4 /* Allow to specify local address for TX packets */ #define SKF_TTL_RX 8 /* Report TTL / Hop Limit for RX packets */ +#define SKF_THREAD 0x100 /* Socked used in thread, Do not add to main loop */ /* * Socket types SA SP DA DP IF TTL SendTo (?=may, -=must not, *=must) -- cgit v1.2.3