diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/birdlib.h | 54 | ||||
| -rw-r--r-- | lib/buffer.h | 35 | ||||
| -rw-r--r-- | lib/hash.h | 123 | ||||
| -rw-r--r-- | lib/heap.h | 156 | ||||
| -rw-r--r-- | lib/lists.c | 40 | ||||
| -rw-r--r-- | lib/lists.h | 1 | ||||
| -rw-r--r-- | lib/printf.c | 39 | ||||
| -rw-r--r-- | lib/resource.c | 32 | ||||
| -rw-r--r-- | lib/resource.h | 6 | ||||
| -rw-r--r-- | lib/socket.h | 2 | ||||
| -rw-r--r-- | lib/string.h | 4 |
11 files changed, 474 insertions, 18 deletions
diff --git a/lib/birdlib.h b/lib/birdlib.h index 7e6e8526..b7a5a6a6 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -10,6 +10,7 @@ #define _BIRD_BIRDLIB_H_ #include "timer.h" +#include "alloca.h" /* Ugly structure offset handling macros */ @@ -19,12 +20,14 @@ /* Utility macros */ -#ifdef PARSER #define _MIN(a,b) (((a)<(b))?(a):(b)) #define _MAX(a,b) (((a)>(b))?(a):(b)) -#else -#define MIN(a,b) (((a)<(b))?(a):(b)) -#define MAX(a,b) (((a)>(b))?(a):(b)) + +#ifndef PARSER +#undef MIN +#undef MAX +#define MIN(a,b) _MIN(a,b) +#define MAX(a,b) _MAX(a,b) #endif #define ABS(a) ((a)>=0 ? (a) : -(a)) @@ -40,24 +43,61 @@ #define IP_VERSION 6 #endif + /* Macros for gcc attributes */ #define NORET __attribute__((noreturn)) #define UNUSED __attribute__((unused)) + +/* Microsecond time */ + +typedef s64 btime; + +#define _S *1000000 +#define _MS *1000 +#define _US *1 +#define TO_S /1000000 +#define TO_MS /1000 +#define TO_US /1 + +#ifndef PARSER +#define S _S +#define MS _MS +#define US _US +#endif + + /* Logging and dying */ +typedef struct buffer { + byte *start; + byte *pos; + byte *end; +} buffer; + +#define STACK_BUFFER_INIT(buf,size) \ + do { \ + buf.start = alloca(size); \ + buf.pos = buf.start; \ + buf.end = buf.start + size; \ + } while(0) + +#define LOG_BUFFER_INIT(buf) \ + STACK_BUFFER_INIT(buf, LOG_BUFFER_SIZE) + +#define LOG_BUFFER_SIZE 1024 + + struct rate_limit { bird_clock_t timestamp; int count; }; #define log log_msg -void log_reset(void); -void log_commit(int class); +void log_commit(int class, buffer *buf); void log_msg(char *msg, ...); void log_rl(struct rate_limit *rl, char *msg, ...); -void logn(char *msg, ...); void die(char *msg, ...) NORET; void bug(char *msg, ...) NORET; 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..3ac9eebd --- /dev/null +++ b/lib/hash.h @@ -0,0 +1,123 @@ + + +#define HASH(type) struct { type **data; uint count, order; } +#define HASH_TYPE(v) typeof(** (v).data) +#define HASH_SIZE(v) (1 << (v).order) +#define HASH_MASK(v) ((1 << (v).order)-1) + + +#define HASH_INIT(v,pool,init_order) \ + ({ \ + (v).count = 0; \ + (v).order = (init_order); \ + (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data)); \ + }) + +#define HASH_FIND(v,id,key...) \ + ({ \ + uint _h = id##_FN((key)) & HASH_MASK(v); \ + HASH_TYPE(v) *_n = (v).data[_h]; \ + while (_n && !id##_EQ(id##_KEY(_n), (key))) \ + _n = id##_NEXT(_n); \ + _n; \ + }) + +#define HASH_INSERT(v,id,node) \ + ({ \ + uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v); \ + HASH_TYPE(v) **_nn = (v).data + _h; \ + id##_NEXT(node) = *_nn; \ + *_nn = node; \ + (v).count++; \ + }) + +#define HASH_DO_REMOVE(v,id,_nn) \ + ({ \ + HASH_TYPE(v) *_n = *_nn; \ + if (_n) \ + { \ + *_nn = id##_NEXT(_n); \ + (v).count--; \ + } \ + _n; \ + }) + +#define HASH_DELETE(v,id,key...) \ + ({ \ + uint _h = id##_FN((key)) & HASH_MASK(v); \ + HASH_TYPE(v) **_nn = (v).data + _h; \ + \ + while ((*_nn) && !id##_EQ(id##_KEY((*_nn)), (key))) \ + _nn = &(id##_NEXT((*_nn))); \ + \ + HASH_DO_REMOVE(v,id,_nn); \ + }) + +#define HASH_REMOVE(v,id,node) \ + ({ \ + uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v); \ + HASH_TYPE(v) **_nn = (v).data + _h; \ + \ + while ((*_nn) && (*_nn != (node))) \ + _nn = &(id##_NEXT((*_nn))); \ + \ + HASH_DO_REMOVE(v,id,_nn); \ + }) + + +#define HASH_REHASH(v,id,pool,step) \ + ({ \ + HASH_TYPE(v) *_n, *_n2, **_od; \ + uint _i, _s; \ + \ + _s = HASH_SIZE(v); \ + _od = (v).data; \ + (v).count = 0; \ + (v).order += (step); \ + (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data)); \ + \ + for (_i = 0; _i < _s; _i++) \ + for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2) \ + HASH_INSERT(v, id, _n); \ + \ + mb_free(_od); \ + }) + +#define HASH_DEFINE_REHASH_FN(id, type) \ + static void id##_REHASH_FN(void *v, pool *p, int step) \ + { HASH_REHASH(* (HASH(type) *) v, id, p, step); } + +#define HASH_TRY_REHASH_UP(v,id,pool) \ + ({ \ + if (((v).order < id##_REHASH_MAX) && ((v).count > HASH_SIZE(v))) \ + id##_REHASH_FN(&v, pool, 1); \ + }) + +#define HASH_TRY_REHASH_DOWN(v,id,pool) \ + ({ \ + if (((v).order > id##_REHASH_MIN) && ((v).count < HASH_SIZE(v)/2)) \ + id##_REHASH_FN(&v, pool, -1); \ + }) + +#define HASH_WALK(v,next,n) \ + do { \ + HASH_TYPE(v) *n; \ + uint _i; \ + uint _s = HASH_SIZE(v); \ + for (_i = 0; _i < _s; _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; \ + uint _s = HASH_SIZE(v); \ + for (_i = 0; _i < _s; _i++) \ + for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next) + +#define HASH_WALK_DELSAFE_END } while (0) + + diff --git a/lib/heap.h b/lib/heap.h new file mode 100644 index 00000000..c8c3d348 --- /dev/null +++ b/lib/heap.h @@ -0,0 +1,156 @@ +/* + * UCW Library -- Universal Heap Macros + * + * (c) 2001 Martin Mares <mj@ucw.cz> + * (c) 2005 Tomas Valla <tom@ucw.cz> + * + * 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 <<generic:,macro generator>> 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 { \ + uint _i = num; \ + uint _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 { \ + uint _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 { \ + uint _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 { \ + uint _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 { \ + uint _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 { \ + uint _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..d323a4b6 100644 --- a/lib/lists.c +++ b/lib/lists.c @@ -101,6 +101,46 @@ rem_node(node *n) } /** + * rem2_node - remove a node from a list, with cleanup + * @n: node to be removed + * + * Removes a node @n from the list it's linked in and resets its pointers to NULL. + * Useful if you want to distinguish between linked and unlinked nodes. + */ +LIST_INLINE void +rem2_node(node *n) +{ + node *z = n->prev; + node *x = n->next; + + z->next = x; + x->prev = z; + n->next = NULL; + n->prev = NULL; +} + +/** + * 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/lists.h b/lib/lists.h index 0b0fdbe3..9153029c 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -51,6 +51,7 @@ typedef struct list { /* In fact two overlayed nodes */ void add_tail(list *, node *); void add_head(list *, node *); void rem_node(node *); +void rem2_node(node *); void add_tail_list(list *, list *); void init_list(list *); void insert_node(node *, node *); diff --git a/lib/printf.c b/lib/printf.c index 14af1062..41e1cc0d 100644 --- a/lib/printf.c +++ b/lib/printf.c @@ -276,7 +276,7 @@ int bvsnprintf(char *buf, int size, const char *fmt, va_list args) ip_ntox(va_arg(args, ip_addr), ipbuf); else { ip_ntop(va_arg(args, ip_addr), ipbuf); - if (field_width > 0) + if (field_width == 1) field_width = STD_ADDRESS_P_LENGTH; } s = ipbuf; @@ -410,3 +410,40 @@ int bsnprintf(char * buf, int size, const char *fmt, ...) va_end(args); return i; } + +int +buffer_vprint(buffer *buf, const char *fmt, va_list args) +{ + int i = bvsnprintf((char *) buf->pos, buf->end - buf->pos, fmt, args); + buf->pos = (i >= 0) ? (buf->pos + i) : buf->end; + return i; +} + +int +buffer_print(buffer *buf, const char *fmt, ...) +{ + va_list args; + int i; + + va_start(args, fmt); + i=bvsnprintf((char *) buf->pos, buf->end - buf->pos, fmt, args); + va_end(args); + + buf->pos = (i >= 0) ? (buf->pos + i) : buf->end; + return i; +} + +void +buffer_puts(buffer *buf, const char *str) +{ + byte *bp = buf->pos; + byte *be = buf->end; + + while (bp < be && *str) + *bp++ = *str++; + + if (bp < be) + *bp = 0; + + buf->pos = bp; +} diff --git a/lib/resource.c b/lib/resource.c index 42243aa2..bf4b3ae9 100644 --- a/lib/resource.c +++ b/lib/resource.c @@ -220,7 +220,8 @@ ralloc(pool *p, struct resclass *c) bzero(r, c->size); r->class = c; - add_tail(&p->inside, &r->n); + if (p) + add_tail(&p->inside, &r->n); return r; } @@ -366,21 +367,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 +393,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 +412,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 * item_size); + *size = nsize; +} diff --git a/lib/resource.h b/lib/resource.h index 5cb5e274..1a62d389 100644 --- a/lib/resource.h +++ b/lib/resource.h @@ -52,7 +52,7 @@ extern pool root_pool; void *mb_alloc(pool *, unsigned size); void *mb_allocz(pool *, unsigned size); -void *mb_realloc(pool *p, void *m, unsigned size); +void *mb_realloc(void *m, unsigned size); void mb_free(void *); /* Memory pools with linear allocation */ @@ -78,6 +78,9 @@ void sl_free(slab *, void *); * outside resource manager and possibly sysdep code. */ +void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size); + + #ifdef HAVE_LIBDMALLOC /* * The standard dmalloc macros tend to produce lots of namespace @@ -103,3 +106,4 @@ void *xrealloc(void *, unsigned); #endif #endif + 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) diff --git a/lib/string.h b/lib/string.h index 14eaa360..2c477294 100644 --- a/lib/string.h +++ b/lib/string.h @@ -17,6 +17,10 @@ int bvsprintf(char *str, const char *fmt, va_list args); int bsnprintf(char *str, int size, const char *fmt, ...); int bvsnprintf(char *str, int size, const char *fmt, va_list args); +int buffer_vprint(buffer *buf, const char *fmt, va_list args); +int buffer_print(buffer *buf, const char *fmt, ...); +void buffer_puts(buffer *buf, const char *str); + int patmatch(byte *pat, byte *str); #endif |