scripts

misc scripts and tools
git clone git://git.2f30.org/scripts.git
Log | Files | Refs

commit f194ef9a467249aaa370722e28c94b7ad67dffb6
parent 179ab953ad1d666b37f936e527f593139cfabadd
Author: sin <sin@2f30.org>
Date:   Fri Aug  2 14:15:41 +0100

Remove allocators, they live in separator repos

Diffstat:
random/alloc.c | 195-------------------------------------------------------------------------------
random/rballoc.c | 340-------------------------------------------------------------------------------
random/spinlock.h | 15---------------
random/tree.h | 765-------------------------------------------------------------------------------
4 files changed, 0 insertions(+), 1315 deletions(-)
diff --git a/random/alloc.c b/random/alloc.c @@ -1,195 +0,0 @@ -#include <sys/mman.h> -#include <unistd.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <errno.h> - -enum chunk_state { - FREE = 0, - ALLOCATED, -}; - -/* A maximum of `NALLOC' allocations possible */ -enum { - NALLOC = 65536 * 128, -}; - -enum { - PAGESIZE = 0x1000, -}; - -struct chunk { - void *base; - size_t size; - enum chunk_state state; -} chunks[NALLOC]; - -static int ndebug = 0; - -/* Allocate a memory block. Round `siz' to be - * a multiple of PAGESIZE */ -static void * -alloc_block(size_t nbytes) -{ - void *addr; - int ret; - - if (nbytes % PAGESIZE) - nbytes = (nbytes + PAGESIZE) & ~(PAGESIZE - 1); - - addr = mmap(0, nbytes + PAGESIZE, - PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, - -1, 0); - if (addr == MAP_FAILED) - return NULL; - /* Guard page at the end of the allocation */ - ret = mprotect((char *)addr + nbytes, PAGESIZE, - PROT_NONE); - if (ret < 0) { - munmap(addr, nbytes + PAGESIZE); - return NULL; - } - return addr; -} - -void * -malloc(size_t nbytes) -{ - void *p; - long i; - - if (!nbytes) - return NULL; - p = alloc_block(nbytes); - if (!p) - return NULL; - for (i = 0; i < NALLOC; i++) { - if (chunks[i].state == FREE) { - chunks[i].base = p; - chunks[i].size = nbytes; - chunks[i].state = ALLOCATED; - if (ndebug > 0) - fprintf(stderr, "%s: allocated %zu bytes at index %ld\n", - __func__, nbytes, i); - return p; - } - } - return NULL; -} - -static inline void -free_chunk(struct chunk *c) -{ - munmap(c->base, c->size + PAGESIZE); - c->base = NULL; - c->size = 0; - c->state = FREE; -} - -void * -realloc(void *oldp, size_t nbytes) -{ - void *p; - size_t n; - long i; - - if (!nbytes && oldp) { - free(oldp); - return NULL; - } - p = malloc(nbytes); - if (!p) - return NULL; - for (i = 0; i < NALLOC; i++) { - if (chunks[i].base == oldp) { - n = chunks[i].size < nbytes ? chunks[i].size : nbytes; - memcpy(p, chunks[i].base, n); - if (ndebug > 0) - fprintf(stderr, "%s: reallocated %zu bytes at index %ld\n", - __func__, nbytes, i); - free_chunk(&chunks[i]); - return p; - } - } - return NULL; -} - -void * -calloc(size_t nmemb, size_t size) -{ - void *p; - - p = malloc(nmemb * size); - if (!p) - return NULL; - memset(p, 0, size * nmemb); - return p; -} - -void -free(void *p) -{ - long i; - - if (!p) - return; - for (i = 0; i < NALLOC; i++) { - if (chunks[i].base == p) { - if (ndebug > 0) - fprintf(stderr, "%s: freed chunk of %zu bytes at index %ld\n", - __func__, chunks[i].size, i); - free_chunk(&chunks[i]); - break; - } - } -} - -void -cfree(void *p) -{ - free(p); -} - -size_t -malloc_usable_size(void *p) -{ - long i; - - if (!p) - return 0; - for (i = 0; i < NALLOC; i++) - if (chunks[i].base == p && chunks[i].state == ALLOCATED) - return chunks[i].size; - return 0; -} - -size_t -malloc_size(void *p) -{ - return malloc_usable_size(p); -} - -int -posix_memalign(void **memptr, size_t align, size_t size) -{ - void *mem; - - if (((align - 1) & align)) - return EINVAL; - if (align < sizeof(void *)) - return EINVAL; - - if (PAGESIZE % align) { - fprintf(stderr, "%s: %zu alignment not supported!\n", - __func__, align); - abort(); - } - - mem = malloc(size); - if (!mem) - return ENOMEM; - - *memptr = mem; - return 0; -} diff --git a/random/rballoc.c b/random/rballoc.c @@ -1,340 +0,0 @@ -/* Compile with gcc -shared -fPIC -o rballoc.so rballoc.c */ -/* LD_PRELOAD=./rballoc.so <prog> */ -#include <sys/mman.h> -#include <unistd.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <stdint.h> -#include <errno.h> -#include "tree.h" -#include "spinlock.h" - -enum { MINALIGNMENT = 4 * sizeof(size_t) }; - -struct node { - void *buf; - size_t siz; - RB_ENTRY(node) entry; -}; - -RB_HEAD(free_tree, node) ft = RB_INITIALIZER(&ft); -RB_HEAD(alloc_tree, node) at = RB_INITIALIZER(&at); -static spinlock_t rblock; - -static int ft_cmp(struct node *a, struct node *b); -RB_PROTOTYPE(free_tree, node, entry, ft_cmp) - -static int at_cmp(struct node *a, struct node *b); -RB_PROTOTYPE(alloc_tree, node, entry, at_cmp) - -RB_GENERATE(free_tree, node, entry, ft_cmp) -/* These are ordered by `siz' */ -static int -ft_cmp(struct node *a, struct node *b) -{ - if (a->siz < b->siz) - return -1; - if (a->siz > b->siz) - return 1; - return 0; -} - -RB_GENERATE(alloc_tree, node, entry, at_cmp) -/* These are ordered by address */ -static int -at_cmp(struct node *a, struct node *b) -{ - if (a->buf < b->buf) - return -1; - if (a->buf > b->buf) - return 1; - return 0; -} - -static void -dump_alloc_tree(void) -{ - struct node *n; - - RB_FOREACH(n, alloc_tree, &at) - fprintf(stderr, "%s: buf: %p, size: %zu\n", - __func__, n->buf, n->siz); -} - -static void -dump_free_tree(void) -{ - struct node *n; - - RB_FOREACH(n, free_tree, &ft) - fprintf(stderr, "%s: buf: %p, size: %zu\n", - __func__, n->buf, n->siz); -} - -static inline void * -alloc_object(size_t siz) -{ - void *base, *p; - - base = sbrk(siz + MINALIGNMENT); - if (base == (void *)-1) - return NULL; - p = base; - p = (void *)(((uintptr_t)p + MINALIGNMENT) & ~(MINALIGNMENT - 1)); - return p; -} - -static inline void * -mmap_aligned(size_t align, size_t siz) -{ - void *p; - - /* align should be a power of two */ - if ((align - 1) & align) - return NULL; - p = mmap(0, siz + align, PROT_READ | PROT_WRITE, - MAP_PRIVATE | MAP_ANON, -1, 0); - if (p == MAP_FAILED) - return NULL; - p = (void *)(((uintptr_t)p + align) & ~(align - 1)); - return p; -} - -void * -malloc(size_t siz) -{ - struct node n, *an, *res; - void *p; - - if (!siz) - return NULL; - lock(&rblock); - /* Lookup in the free tree for a block greater - * than or equal to `siz' bytes */ - n.siz = siz; - res = RB_NFIND(free_tree, &ft, &n); - if (!res) { - /* No available free block, create a new block - * and add it to the alloc tree */ - an = alloc_object(sizeof(*an)); - if (!an) { - unlock(&rblock); - return NULL; - } - p = mmap_aligned(MINALIGNMENT, siz); - if (!p) { - unlock(&rblock); - return NULL; - } - an->buf = p; - an->siz = siz; - RB_INSERT(alloc_tree, &at, an); - unlock(&rblock); - return an->buf; - } - an = RB_REMOVE(free_tree, &ft, res); - RB_INSERT(alloc_tree, &at, an); - unlock(&rblock); - return an->buf; -} - -void * -realloc(void *oldp, size_t siz) -{ - struct node n, *res; - struct node *oldan, *newan; - struct node *fn; - - if (!oldp) - return malloc(siz); - if (!siz) { - if (oldp) - free(oldp); - return NULL; - } - lock(&rblock); - n.buf = oldp; - res = RB_FIND(alloc_tree, &at, &n); - if (res) { - /* If we were asked to shrink the allocated space - * just re-use it */ - if (res->siz >= siz) { - unlock(&rblock); - return res->buf; - } - oldan = res; - /* Lookup in the free tree for a block greater - * than or equal to `siz' bytes */ - n.siz = siz; - res = RB_NFIND(free_tree, &ft, &n); - if (!res) { - /* No available free block, create a new block - * and add it to the alloc tree */ - newan = alloc_object(sizeof(*newan)); - if (!newan) { - unlock(&rblock); - return NULL; - } - newan->buf = mmap_aligned(MINALIGNMENT, siz); - if (!newan->buf) { - free_object(newan, sizeof(*newan)); - unlock(&rblock); - return NULL; - } - newan->siz = siz; - RB_INSERT(alloc_tree, &at, newan); - } else { - /* Grab the block from the free tree instead */ - newan = RB_REMOVE(free_tree, &ft, res); - RB_INSERT(alloc_tree, &at, newan); - } - /* Copy over the contents from `oldp' to the - * new memory block */ - memcpy(newan->buf, oldan->buf, - siz < oldan->siz ? siz : oldan->siz); - /* Return `oldp' to the free tree */ - n.buf = oldan; - res = RB_FIND(alloc_tree, &at, &n); - if (res) { - fn = RB_REMOVE(alloc_tree, &at, res); - RB_INSERT(free_tree, &ft, fn); - } - unlock(&rblock); - return newan->buf; - } - unlock(&rblock); - return NULL; -} - -void * -calloc(size_t nmemb, size_t siz) -{ - void *p; - - p = malloc(nmemb * siz); - if (!p) - return NULL; - memset(p, 0, nmemb * siz); - return p; -} - -void -free(void *p) -{ - struct node n, *fn, *res; - - if (!p) - return; - lock(&rblock); - n.buf = p; - res = RB_FIND(alloc_tree, &at, &n); - if (res) { - fn = RB_REMOVE(alloc_tree, &at, res); - RB_INSERT(free_tree, &ft, fn); - } - unlock(&rblock); -} - -void -cfree(void *p) -{ - return free(p); -} - -void * -memalign(size_t align, size_t siz) -{ - struct node *an; - void *p; - - if (((align - 1) & align)) - return NULL; - if (align < sizeof(void *)) - return NULL; - if (!siz) - return 0; - /* Just allocate a new block, we don't care to look - * for a block in the free tree as it might not be properly - * aligned. The previous implementation could cope with - * that but it was sort of hackish. There are few calls to - * posix_memalign() in most cases, so the overhead should - * not really matter. */ - an = alloc_object(sizeof(*an)); - if (!an) - return NULL; - p = mmap_aligned(align, siz); - if (!p) - return NULL; - an->buf = p; - an->siz = siz; - lock(&rblock); - RB_INSERT(alloc_tree, &at, an); - unlock(&rblock); - return p; -} - -void * -aligned_alloc(size_t align, size_t siz) -{ - if (siz % align) - return NULL; - return memalign(align, siz); -} - -void * -valloc(size_t siz) -{ - return memalign(sysconf(_SC_PAGESIZE), siz); -} - -void * -pvalloc(size_t siz) -{ - long pagesize = sysconf(_SC_PAGESIZE); - siz = pagesize * ((siz + pagesize - 1) / pagesize); - return valloc(siz); -} - -int -posix_memalign(void **memptr, size_t align, size_t siz) -{ - struct node *an; - void *p; - - *memptr = NULL; - if (((align - 1) & align)) - return EINVAL; - if (align < sizeof(void *)) - return EINVAL; - if (!siz) - return 0; - *memptr = memalign(align, siz); - if (!*memptr) - return ENOMEM; - return 0; -} - -size_t -malloc_usable_size(void *p) -{ - struct node n, *res; - - if (!p) - return 0; - lock(&rblock); - n.buf = p; - res = RB_FIND(alloc_tree, &at, &n); - if (res) { - unlock(&rblock); - return res->siz; - } - unlock(&rblock); - return 0; -} - -size_t -malloc_size(void *p) -{ - return malloc_usable_size(p); -} diff --git a/random/spinlock.h b/random/spinlock.h @@ -1,15 +0,0 @@ -typedef int spinlock_t; - -static inline void -lock(spinlock_t *sl) -{ - while (__sync_lock_test_and_set(sl, 1)) - ; -} - -static inline void -unlock(spinlock_t *sl) -{ - __sync_synchronize(); - *sl = 0; -} diff --git a/random/tree.h b/random/tree.h @@ -1,765 +0,0 @@ -/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ -/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ -/* $FreeBSD$ */ - -/*- - * Copyright 2002 Niels Provos <provos@citi.umich.edu> - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef _SYS_TREE_H -#define _SYS_TREE_H - -#include <sys/cdefs.h> - -/* - * This file defines data structures for different types of trees: - * splay trees and red-black trees. - * - * A splay tree is a self-organizing data structure. Every operation - * on the tree causes a splay to happen. The splay moves the requested - * node to the root of the tree and partly rebalances it. - * - * This has the benefit that request locality causes faster lookups as - * the requested nodes move to the top of the tree. On the other hand, - * every lookup causes memory writes. - * - * The Balance Theorem bounds the total access time for m operations - * and n inserts on an initially empty tree as O((m + n)lg n). The - * amortized cost for a sequence of m accesses to a splay tree is O(lg n); - * - * A red-black tree is a binary search tree with the node color as an - * extra attribute. It fulfills a set of conditions: - * - every search path from the root to a leaf consists of the - * same number of black nodes, - * - each red node (except for the root) has a black parent, - * - each leaf node is black. - * - * Every operation on a red-black tree is bounded as O(lg n). - * The maximum height of a red-black tree is 2lg (n+1). - */ - -#define SPLAY_HEAD(name, type) \ -struct name { \ - struct type *sph_root; /* root of the tree */ \ -} - -#define SPLAY_INITIALIZER(root) \ - { NULL } - -#define SPLAY_INIT(root) do { \ - (root)->sph_root = NULL; \ -} while (/*CONSTCOND*/ 0) - -#define SPLAY_ENTRY(type) \ -struct { \ - struct type *spe_left; /* left element */ \ - struct type *spe_right; /* right element */ \ -} - -#define SPLAY_LEFT(elm, field) (elm)->field.spe_left -#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right -#define SPLAY_ROOT(head) (head)->sph_root -#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) - -/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ -} while (/*CONSTCOND*/ 0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ -} while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKLEFT(head, tmp, field) do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ -} while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKRIGHT(head, tmp, field) do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ -} while (/*CONSTCOND*/ 0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ - SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ -} while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ - -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ -void name##_SPLAY(struct name *, struct type *); \ -void name##_SPLAY_MINMAX(struct name *, int); \ -struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ -struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ - \ -/* Finds the node with the same key as elm */ \ -static __inline struct type * \ -name##_SPLAY_FIND(struct name *head, struct type *elm) \ -{ \ - if (SPLAY_EMPTY(head)) \ - return(NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ -} \ - \ -static __inline struct type * \ -name##_SPLAY_NEXT(struct name *head, struct type *elm) \ -{ \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ -} \ - \ -static __inline struct type * \ -name##_SPLAY_MIN_MAX(struct name *head, int val) \ -{ \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ -} - -/* Main splay operation. - * Moves node close to the key of elm to top - */ -#define SPLAY_GENERATE(name, type, field, cmp) \ -struct type * \ -name##_SPLAY_INSERT(struct name *head, struct type *elm) \ -{ \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if(__comp < 0) { \ - SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ -} \ - \ -struct type * \ -name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *__tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ -} \ - \ -void \ -name##_SPLAY(struct name *head, struct type *elm) \ -{ \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ -\ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ - __left = __right = &__node; \ -\ - while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0){ \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0){ \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ -} \ - \ -/* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ -void name##_SPLAY_MINMAX(struct name *head, int __comp) \ -{ \ - struct type __node, *__left, *__right, *__tmp; \ -\ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ - __left = __right = &__node; \ -\ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0){ \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ -} - -#define SPLAY_NEGINF -1 -#define SPLAY_INF 1 - -#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) -#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) -#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) -#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ - : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ - : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); \ - (x) != NULL; \ - (x) = SPLAY_NEXT(name, head, x)) - -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (/*CONSTCOND*/ 0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ -} while (/*CONSTCOND*/ 0) - -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (/*CONSTCOND*/ 0) - -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif - -#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (/*CONSTCOND*/ 0) - -#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RB_INSERT(struct name *, struct type *); \ -attr struct type *name##_RB_FIND(struct name *, struct type *); \ -attr struct type *name##_RB_NFIND(struct name *, struct type *); \ -attr struct type *name##_RB_NEXT(struct type *); \ -attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ - \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ -{ \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) != NULL && \ - RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ -} \ - \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ -{ \ - struct type *tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RB_LEFT(tmp, field)) \ - != NULL) \ - RB_COLOR(oleft, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RB_RIGHT(tmp, field)) \ - != NULL) \ - RB_COLOR(oright, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ -} \ - \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field)) != NULL) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field)) != NULL); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ -} \ - \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RB_INSERT(struct name *head, struct type *elm) \ -{ \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ -} \ - \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RB_FIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ -} \ - \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_NEXT(struct type *elm) \ -{ \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ -{ \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -attr struct type * \ -name##_RB_MINMAX(struct name *head, int val) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ -} - -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_FROM(x, name, y) \ - for ((x) = (y); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_FROM(x, name, y) \ - for ((x) = (y); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) - -#endif