From 27484e07cdd0be148743cb8e4acd99e96264eca9 Mon Sep 17 00:00:00 2001 From: Richard Braun Date: Sat, 3 Nov 2012 17:30:15 +0100 Subject: Merge lib into kern There are no precise enough criteria to justify the separation of these two directories. --- Makefrag.am | 28 +-- arch/x86/machine/acpimp.c | 10 +- arch/x86/machine/biosmem.c | 10 +- arch/x86/machine/boot.c | 7 +- arch/x86/machine/boot.h | 2 +- arch/x86/machine/cpu.c | 10 +- arch/x86/machine/cpu.h | 6 +- arch/x86/machine/io.h | 2 +- arch/x86/machine/lapic.c | 5 +- arch/x86/machine/lapic.h | 2 +- arch/x86/machine/multiboot.h | 4 +- arch/x86/machine/param.h | 2 +- arch/x86/machine/pic.c | 4 +- arch/x86/machine/pit.c | 2 +- arch/x86/machine/pmap.c | 8 +- arch/x86/machine/pmap.h | 4 +- arch/x86/machine/trap.c | 4 +- arch/x86/machine/trap.h | 2 +- arch/x86/machine/vga.c | 6 +- arch/x86/machine/vga.h | 2 +- kern/assert.h | 40 ++++ kern/init.h | 2 +- kern/kmem.c | 18 +- kern/kmem.h | 6 +- kern/limits.h | 23 ++ kern/list.h | 364 ++++++++++++++++++++++++++++ kern/macros.h | 73 ++++++ kern/panic.h | 2 +- kern/printk.c | 2 +- kern/printk.h | 2 +- kern/rbtree.c | 489 ++++++++++++++++++++++++++++++++++++++ kern/rbtree.h | 299 +++++++++++++++++++++++ kern/rbtree_i.h | 187 +++++++++++++++ kern/sprintf.c | 550 +++++++++++++++++++++++++++++++++++++++++++ kern/sprintf.h | 43 ++++ kern/stddef.h | 35 +++ kern/stdint.h | 30 +++ kern/string.c | 138 +++++++++++ kern/string.h | 31 +++ lib/assert.h | 40 ---- lib/limits.h | 23 -- lib/list.h | 364 ---------------------------- lib/macros.h | 73 ------ lib/rbtree.c | 489 -------------------------------------- lib/rbtree.h | 299 ----------------------- lib/rbtree_i.h | 187 --------------- lib/sprintf.c | 550 ------------------------------------------- lib/sprintf.h | 43 ---- lib/stddef.h | 35 --- lib/stdint.h | 30 --- lib/string.c | 138 ----------- lib/string.h | 31 --- vm/vm_kmem.c | 4 +- vm/vm_map.c | 12 +- vm/vm_map.h | 6 +- vm/vm_page.h | 4 +- vm/vm_phys.c | 12 +- 57 files changed, 2397 insertions(+), 2397 deletions(-) create mode 100644 kern/assert.h create mode 100644 kern/limits.h create mode 100644 kern/list.h create mode 100644 kern/macros.h create mode 100644 kern/rbtree.c create mode 100644 kern/rbtree.h create mode 100644 kern/rbtree_i.h create mode 100644 kern/sprintf.c create mode 100644 kern/sprintf.h create mode 100644 kern/stddef.h create mode 100644 kern/stdint.h create mode 100644 kern/string.c create mode 100644 kern/string.h delete mode 100644 lib/assert.h delete mode 100644 lib/limits.h delete mode 100644 lib/list.h delete mode 100644 lib/macros.h delete mode 100644 lib/rbtree.c delete mode 100644 lib/rbtree.h delete mode 100644 lib/rbtree_i.h delete mode 100644 lib/sprintf.c delete mode 100644 lib/sprintf.h delete mode 100644 lib/stddef.h delete mode 100644 lib/stdint.h delete mode 100644 lib/string.c delete mode 100644 lib/string.h diff --git a/Makefrag.am b/Makefrag.am index e2639a68..22cc0121 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -1,6 +1,7 @@ include arch/x86/Makefrag.am x15_SOURCES += \ + kern/assert.h \ kern/config.h \ kern/error.h \ kern/init.h \ @@ -8,29 +9,26 @@ x15_SOURCES += \ kern/kernel.h \ kern/kmem.c \ kern/kmem.h \ + kern/limits.h \ + kern/list.h \ + kern/macros.h \ kern/panic.c \ kern/panic.h \ kern/param.h \ kern/printk.c \ kern/printk.h \ + kern/rbtree.c \ + kern/rbtree.h \ + kern/rbtree_i.h \ kern/spinlock.h \ + kern/sprintf.c \ + kern/sprintf.h \ + kern/stddef.h \ + kern/stdint.h \ + kern/string.c \ + kern/string.h \ kern/types.h -x15_SOURCES += \ - lib/assert.h \ - lib/limits.h \ - lib/list.h \ - lib/macros.h \ - lib/rbtree.c \ - lib/rbtree.h \ - lib/rbtree_i.h \ - lib/sprintf.c \ - lib/sprintf.h \ - lib/stddef.h \ - lib/stdint.h \ - lib/string.c \ - lib/string.h - x15_SOURCES += \ vm/vm_inherit.h \ vm/vm_kmem.c \ diff --git a/arch/x86/machine/acpimp.c b/arch/x86/machine/acpimp.c index 92b28ebd..0b13cd25 100644 --- a/arch/x86/machine/acpimp.c +++ b/arch/x86/machine/acpimp.c @@ -15,16 +15,16 @@ * along with this program. If not, see . */ +#include #include #include +#include #include #include +#include +#include +#include #include -#include -#include -#include -#include -#include #include #include #include diff --git a/arch/x86/machine/biosmem.c b/arch/x86/machine/biosmem.c index 77bc8d0c..a72a8016 100644 --- a/arch/x86/machine/biosmem.c +++ b/arch/x86/machine/biosmem.c @@ -15,16 +15,16 @@ * along with this program. If not, see . */ +#include #include +#include #include #include #include +#include +#include +#include #include -#include -#include -#include -#include -#include #include #include #include diff --git a/arch/x86/machine/boot.c b/arch/x86/machine/boot.c index 691605f5..35fabb53 100644 --- a/arch/x86/machine/boot.c +++ b/arch/x86/machine/boot.c @@ -45,12 +45,13 @@ #include #include #include +#include #include #include #include -#include -#include -#include +#include +#include +#include #include #include #include diff --git a/arch/x86/machine/boot.h b/arch/x86/machine/boot.h index 41d3ca49..992e533a 100644 --- a/arch/x86/machine/boot.h +++ b/arch/x86/machine/boot.h @@ -18,7 +18,7 @@ #ifndef _X86_BOOT_H #define _X86_BOOT_H -#include +#include #include /* diff --git a/arch/x86/machine/cpu.c b/arch/x86/machine/cpu.c index 57a3e465..18dcadac 100644 --- a/arch/x86/machine/cpu.c +++ b/arch/x86/machine/cpu.c @@ -15,15 +15,15 @@ * along with this program. If not, see . */ +#include #include +#include #include #include #include -#include -#include -#include -#include -#include +#include +#include +#include #include #include #include diff --git a/arch/x86/machine/cpu.h b/arch/x86/machine/cpu.h index 1543baa1..c2dce19b 100644 --- a/arch/x86/machine/cpu.h +++ b/arch/x86/machine/cpu.h @@ -87,10 +87,10 @@ #ifndef __ASSEMBLER__ +#include #include -#include -#include -#include +#include +#include #include #define CPU_VENDOR_ID_SIZE 13 diff --git a/arch/x86/machine/io.h b/arch/x86/machine/io.h index d99d180f..6b10f0eb 100644 --- a/arch/x86/machine/io.h +++ b/arch/x86/machine/io.h @@ -18,7 +18,7 @@ #ifndef _X86_IO_H #define _X86_IO_H -#include +#include /* * Read a byte from an I/O port. diff --git a/arch/x86/machine/lapic.c b/arch/x86/machine/lapic.c index 03a2820f..c2a2b3aa 100644 --- a/arch/x86/machine/lapic.c +++ b/arch/x86/machine/lapic.c @@ -16,11 +16,12 @@ */ #include +#include #include #include #include -#include -#include +#include +#include #include #include #include diff --git a/arch/x86/machine/lapic.h b/arch/x86/machine/lapic.h index 8e74f617..24d104cd 100644 --- a/arch/x86/machine/lapic.h +++ b/arch/x86/machine/lapic.h @@ -18,7 +18,7 @@ #ifndef _X86_LAPIC_H #define _X86_LAPIC_H -#include +#include #include /* diff --git a/arch/x86/machine/multiboot.h b/arch/x86/machine/multiboot.h index 7b604a98..b0d31524 100644 --- a/arch/x86/machine/multiboot.h +++ b/arch/x86/machine/multiboot.h @@ -45,8 +45,8 @@ #ifndef __ASSEMBLER__ -#include -#include +#include +#include /* * A multiboot module. diff --git a/arch/x86/machine/param.h b/arch/x86/machine/param.h index e7241fd6..73e1ced1 100644 --- a/arch/x86/machine/param.h +++ b/arch/x86/machine/param.h @@ -18,7 +18,7 @@ #ifndef _X86_PARAM_H #define _X86_PARAM_H -#include +#include #include #define __LITTLE_ENDIAN__ diff --git a/arch/x86/machine/pic.c b/arch/x86/machine/pic.c index ddb895bd..3e5d8bbb 100644 --- a/arch/x86/machine/pic.c +++ b/arch/x86/machine/pic.c @@ -15,10 +15,10 @@ * along with this program. If not, see . */ +#include #include #include -#include -#include +#include #include #include #include diff --git a/arch/x86/machine/pit.c b/arch/x86/machine/pit.c index e5113ceb..ea7a1a58 100644 --- a/arch/x86/machine/pit.c +++ b/arch/x86/machine/pit.c @@ -15,8 +15,8 @@ * along with this program. If not, see . */ +#include #include -#include #include #include diff --git a/arch/x86/machine/pmap.c b/arch/x86/machine/pmap.c index 8365b8a8..703d842a 100644 --- a/arch/x86/machine/pmap.c +++ b/arch/x86/machine/pmap.c @@ -15,14 +15,14 @@ * along with this program. If not, see . */ +#include #include +#include #include #include +#include +#include #include -#include -#include -#include -#include #include #include #include diff --git a/arch/x86/machine/pmap.h b/arch/x86/machine/pmap.h index 7865f5fa..81cc998c 100644 --- a/arch/x86/machine/pmap.h +++ b/arch/x86/machine/pmap.h @@ -21,7 +21,7 @@ #ifndef _X86_PMAP_H #define _X86_PMAP_H -#include +#include /* * Page table entry flags. @@ -100,8 +100,8 @@ #ifndef __ASSEMBLER__ +#include #include -#include #ifdef X86_PAE typedef uint64_t pmap_pte_t; diff --git a/arch/x86/machine/trap.c b/arch/x86/machine/trap.c index 56715c81..4b450ecf 100644 --- a/arch/x86/machine/trap.c +++ b/arch/x86/machine/trap.c @@ -15,11 +15,11 @@ * along with this program. If not, see . */ +#include #include +#include #include #include -#include -#include #include #include #include diff --git a/arch/x86/machine/trap.h b/arch/x86/machine/trap.h index 161694de..f25c5893 100644 --- a/arch/x86/machine/trap.h +++ b/arch/x86/machine/trap.h @@ -57,7 +57,7 @@ #ifndef __ASSEMBLER__ -#include +#include #ifdef __LP64__ diff --git a/arch/x86/machine/vga.c b/arch/x86/machine/vga.c index 60911943..08b72332 100644 --- a/arch/x86/machine/vga.c +++ b/arch/x86/machine/vga.c @@ -16,9 +16,9 @@ */ #include -#include -#include -#include +#include +#include +#include #include #include #include diff --git a/arch/x86/machine/vga.h b/arch/x86/machine/vga.h index f6836cd9..6e7c6043 100644 --- a/arch/x86/machine/vga.h +++ b/arch/x86/machine/vga.h @@ -18,7 +18,7 @@ #ifndef _X86_VGA_H #define _X86_VGA_H -#include +#include /* * Initialize the vga module. diff --git a/kern/assert.h b/kern/assert.h new file mode 100644 index 00000000..d0fd08a5 --- /dev/null +++ b/kern/assert.h @@ -0,0 +1,40 @@ +/* + * Copyright (c) 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_ASSERT_H +#define _KERN_ASSERT_H + +#ifdef NDEBUG +#define assert(expression) ((void)(expression)) +#else /* NDEBUG */ + +#include +#include + +/* + * Panic if the given expression is false. + */ +#define assert(expression) \ +MACRO_BEGIN \ + if (unlikely(!(expression))) \ + panic("assertion (%s) failed in %s:%d, function %s()", \ + __QUOTE(expression), __FILE__, __LINE__, __func__); \ +MACRO_END + +#endif /* NDEBUG */ + +#endif /* _KERN_ASSERT_H */ diff --git a/kern/init.h b/kern/init.h index e9762724..6e437c0a 100644 --- a/kern/init.h +++ b/kern/init.h @@ -18,7 +18,7 @@ #ifndef _KERN_INIT_H #define _KERN_INIT_H -#include +#include /* * These sections should contain code and data which can be discarded once diff --git a/kern/kmem.c b/kern/kmem.c index 663cafe2..70aeebb6 100644 --- a/kern/kmem.c +++ b/kern/kmem.c @@ -48,20 +48,20 @@ * handled likewise. */ +#include #include +#include +#include #include +#include #include #include #include -#include -#include -#include -#include -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include #include #include diff --git a/kern/kmem.h b/kern/kmem.h index dee4a857..350c8977 100644 --- a/kern/kmem.h +++ b/kern/kmem.h @@ -21,10 +21,10 @@ #ifndef _KERN_KMEM_H #define _KERN_KMEM_H +#include #include -#include -#include -#include +#include +#include /* * Per-processor cache of pre-constructed objects. diff --git a/kern/limits.h b/kern/limits.h new file mode 100644 index 00000000..48f4b945 --- /dev/null +++ b/kern/limits.h @@ -0,0 +1,23 @@ +/* + * Copyright (c) 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_LIMITS_H +#define _KERN_LIMITS_H + +#define CHAR_BIT 8 + +#endif /* _KERN_LIMITS_H */ diff --git a/kern/list.h b/kern/list.h new file mode 100644 index 00000000..647e94c9 --- /dev/null +++ b/kern/list.h @@ -0,0 +1,364 @@ +/* + * Copyright (c) 2009, 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * + * Simple doubly-linked list. + */ + +#ifndef _KERN_LIST_H +#define _KERN_LIST_H + +#include +#include + +/* + * Structure used as both head and node. + * + * This implementation relies on using the same type for both heads and nodes. + * + * It is recommended to encode the use of struct list variables in their names, + * e.g. struct list free_list or struct list free_objects is a good hint for a + * list of free objects. A declaration like struct list free_node clearly + * indicates it is used as part of a node in the free list. + */ +struct list { + struct list *prev; + struct list *next; +}; + +/* + * Static list initializer. + */ +#define LIST_INITIALIZER(list) { &(list), &(list) } + +/* + * Initialize a list. + */ +static inline void +list_init(struct list *list) +{ + list->prev = list; + list->next = list; +} + +/* + * Initialize a list node. + * + * An entry is in no list when its node members point to NULL. + */ +static inline void +list_node_init(struct list *node) +{ + node->prev = NULL; + node->next = NULL; +} + +/* + * Return true if node is in no list. + */ +static inline int +list_node_unlinked(const struct list *node) +{ + return node->prev == NULL; +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define list_entry(node, type, member) structof(node, type, member) + +/* + * Return the first node of a list. + */ +static inline struct list * +list_first(const struct list *list) +{ + return list->next; +} + +/* + * Return the last node of a list. + */ +static inline struct list * +list_last(const struct list *list) +{ + return list->prev; +} + +/* + * Return the node next to the given node. + */ +static inline struct list * +list_next(const struct list *node) +{ + return node->next; +} + +/* + * Return the node previous to the given node. + */ +static inline struct list * +list_prev(const struct list *node) +{ + return node->prev; +} + +/* + * Get the first entry of a list. + */ +#define list_first_entry(list, type, member) \ + list_entry(list_first(list), type, member) + +/* + * Get the last entry of a list. + */ +#define list_last_entry(list, type, member) \ + list_entry(list_last(list), type, member) + +/* + * Return true if node is after the last or before the first node of the list. + */ +static inline int +list_end(const struct list *list, const struct list *node) +{ + return list == node; +} + +/* + * Return true if list is empty. + */ +static inline int +list_empty(const struct list *list) +{ + return list == list->next; +} + +/* + * Return true if list contains exactly one node. + */ +static inline int +list_singular(const struct list *list) +{ + return (list != list->next) && (list->next == list->prev); +} + +/* + * Split list2 by moving its nodes up to (but not including) the given + * node into list1 (which can be in a stale state). + * + * If list2 is empty, or node is list2 or list2->next, nothing is done. + */ +static inline void +list_split(struct list *list1, struct list *list2, struct list *node) +{ + if (list_empty(list2) || (list2->next == node) || list_end(list2, node)) + return; + + list1->next = list2->next; + list1->next->prev = list1; + + list1->prev = node->prev; + node->prev->next = list1; + + list2->next = node; + node->prev = list2; +} + +/* + * Append the nodes of list2 at the end of list1. + * + * After completion, list2 is stale. + */ +static inline void +list_concat(struct list *list1, const struct list *list2) +{ + struct list *last1, *first2, *last2; + + if (list_empty(list2)) + return; + + last1 = list1->prev; + first2 = list2->next; + last2 = list2->prev; + + last1->next = first2; + first2->prev = last1; + + last2->next = list1; + list1->prev = last2; +} + +/* + * Set the new head of a list. + * + * This function is an optimized version of : + * list_init(&new_list); + * list_concat(&new_list, &old_list); + * + * After completion, old_head is stale. + */ +static inline void +list_set_head(struct list *new_head, const struct list *old_head) +{ + if (list_empty(old_head)) { + list_init(new_head); + return; + } + + *new_head = *old_head; + new_head->next->prev = new_head; + new_head->prev->next = new_head; +} + +/* + * Add a node between two nodes. + */ +static inline void +list_add(struct list *prev, struct list *next, struct list *node) +{ + next->prev = node; + node->next = next; + + prev->next = node; + node->prev = prev; +} + +/* + * Insert a node at the head of a list. + */ +static inline void +list_insert(struct list *list, struct list *node) +{ + list_add(list, list->next, node); +} + +/* + * Insert a node at the tail of a list. + */ +static inline void +list_insert_tail(struct list *list, struct list *node) +{ + list_add(list->prev, list, node); +} + +/* + * Insert a node before another node. + */ +static inline void +list_insert_before(struct list *next, struct list *node) +{ + list_add(next->prev, next, node); +} + +/* + * Insert a node after another node. + */ +static inline void +list_insert_after(struct list *prev, struct list *node) +{ + list_add(prev, prev->next, node); +} + +/* + * Remove a node from a list. + * + * After completion, the node is stale. + */ +static inline void +list_remove(struct list *node) +{ + node->prev->next = node->next; + node->next->prev = node->prev; +} + +/* + * Forge a loop to process all nodes of a list. + * + * The node must not be altered during the loop. + */ +#define list_for_each(list, node) \ +for (node = list_first(list); \ + !list_end(list, node); \ + node = list_next(node)) + +/* + * Forge a loop to process all nodes of a list. + */ +#define list_for_each_safe(list, node, tmp) \ +for (node = list_first(list), tmp = list_next(node); \ + !list_end(list, node); \ + node = tmp, tmp = list_next(node)) + +/* + * Version of list_for_each() that processes nodes backward. + */ +#define list_for_each_reverse(list, node) \ +for (node = list_last(list); \ + !list_end(list, node); \ + node = list_prev(node)) + +/* + * Version of list_for_each_safe() that processes nodes backward. + */ +#define list_for_each_reverse_safe(list, node, tmp) \ +for (node = list_last(list), tmp = list_prev(node); \ + !list_end(list, node); \ + node = tmp, tmp = list_prev(node)) + +/* + * Forge a loop to process all entries of a list. + * + * The entry node must not be altered during the loop. + */ +#define list_for_each_entry(list, entry, member) \ +for (entry = list_entry(list_first(list), typeof(*entry), member); \ + !list_end(list, &entry->member); \ + entry = list_entry(list_next(&entry->member), typeof(*entry), \ + member)) + +/* + * Forge a loop to process all entries of a list. + */ +#define list_for_each_entry_safe(list, entry, tmp, member) \ +for (entry = list_entry(list_first(list), typeof(*entry), member), \ + tmp = list_entry(list_next(&entry->member), typeof(*entry), \ + member); \ + !list_end(list, &entry->member); \ + entry = tmp, tmp = list_entry(list_next(&entry->member), \ + typeof(*entry), member)) + +/* + * Version of list_for_each_entry() that processes entries backward. + */ +#define list_for_each_entry_reverse(list, entry, member) \ +for (entry = list_entry(list_last(list), typeof(*entry), member); \ + !list_end(list, &entry->member); \ + entry = list_entry(list_prev(&entry->member), typeof(*entry), \ + member)) + +/* + * Version of list_for_each_entry_safe() that processes entries backward. + */ +#define list_for_each_entry_reverse_safe(list, entry, tmp, member) \ +for (entry = list_entry(list_last(list), typeof(*entry), member), \ + tmp = list_entry(list_prev(&entry->member), typeof(*entry), \ + member); \ + !list_end(list, &entry->member); \ + entry = tmp, tmp = list_entry(list_prev(&entry->member), \ + typeof(*entry), member)) + +#endif /* _KERN_LIST_H */ diff --git a/kern/macros.h b/kern/macros.h new file mode 100644 index 00000000..012dd15b --- /dev/null +++ b/kern/macros.h @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2009, 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * + * Helper macros. + */ + +#ifndef _KERN_MACROS_H +#define _KERN_MACROS_H + +#ifndef __ASSEMBLER__ +#include +#endif /* __ASSEMBLER__ */ + +#define MACRO_BEGIN ({ +#define MACRO_END }) + +#define __QUOTE(x) #x +#define QUOTE(x) __QUOTE(x) + +#ifdef __ASSEMBLER__ +#define DECL_CONST(x, s) x +#else /* __ASSEMBLER__ */ +#define __DECL_CONST(x, s) x##s +#define DECL_CONST(x, s) __DECL_CONST(x, s) +#endif /* __ASSEMBLER__ */ + +#define STRLEN(x) (sizeof(x) - 1) +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) +#define MAX(a, b) ((a) > (b) ? (a) : (b)) + +#define P2ALIGNED(x, a) (((x) & ((a) - 1)) == 0) +#define ISP2(x) P2ALIGNED(x, x) +#define P2ALIGN(x, a) ((x) & -(a)) +#define P2ROUND(x, a) (-(-(x) & -(a))) +#define P2END(x, a) (-(~(x) & -(a))) + +#define structof(ptr, type, member) \ + ((type *)((char *)ptr - offsetof(type, member))) + +#define alignof(x) __alignof__(x) + +#define likely(expr) __builtin_expect(!!(expr), 1) +#define unlikely(expr) __builtin_expect(!!(expr), 0) + +#define barrier() asm volatile("" : : : "memory") + +#define __noreturn __attribute__((noreturn)) +#define __aligned(x) __attribute__((aligned(x))) +#define __always_inline inline __attribute__((always_inline)) +#define __section(x) __attribute__((section(x))) +#define __packed __attribute__((packed)) +#define __alias(x) __attribute__((alias(x))) + +#define __format_printf(fmt, args) \ + __attribute__((format(printf, fmt, args))) + +#endif /* _KERN_MACROS_H */ diff --git a/kern/panic.h b/kern/panic.h index a3bfbbe2..9d1d31e0 100644 --- a/kern/panic.h +++ b/kern/panic.h @@ -18,7 +18,7 @@ #ifndef _KERN_PANIC_H #define _KERN_PANIC_H -#include +#include /* * Print the given message and halt the system immediately. diff --git a/kern/printk.c b/kern/printk.c index 38d835c0..386ac979 100644 --- a/kern/printk.c +++ b/kern/printk.c @@ -17,7 +17,7 @@ #include #include -#include +#include /* * Size of the static buffer. diff --git a/kern/printk.h b/kern/printk.h index 37f25453..5e2a871b 100644 --- a/kern/printk.h +++ b/kern/printk.h @@ -29,7 +29,7 @@ #include -#include +#include int printk(const char *format, ...) __format_printf(1, 2); int vprintk(const char *format, va_list ap) __format_printf(1, 0); diff --git a/kern/rbtree.c b/kern/rbtree.c new file mode 100644 index 00000000..569d3fac --- /dev/null +++ b/kern/rbtree.c @@ -0,0 +1,489 @@ +/* + * Copyright (c) 2010, 2012 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include +#include + +/* + * Return the index of a node in the children array of its parent. + * + * The parent parameter must not be null, and must be the parent of the + * given node. + */ +static inline int +rbtree_node_index(const struct rbtree_node *node, + const struct rbtree_node *parent) +{ + assert(parent != NULL); + assert((node == NULL) || (rbtree_node_parent(node) == parent)); + + if (parent->children[RBTREE_LEFT] == node) + return RBTREE_LEFT; + + assert(parent->children[RBTREE_RIGHT] == node); + + return RBTREE_RIGHT; +} + +/* + * Return the color of a node. + */ +static inline int +rbtree_node_color(const struct rbtree_node *node) +{ + return node->parent & RBTREE_COLOR_MASK; +} + +/* + * Return true if the node is red. + */ +static inline int +rbtree_node_is_red(const struct rbtree_node *node) +{ + return rbtree_node_color(node) == RBTREE_COLOR_RED; +} + +/* + * Return true if the node is black. + */ +static inline int +rbtree_node_is_black(const struct rbtree_node *node) +{ + return rbtree_node_color(node) == RBTREE_COLOR_BLACK; +} + +/* + * Set the parent of a node, retaining its current color. + */ +static inline void +rbtree_node_set_parent(struct rbtree_node *node, struct rbtree_node *parent) +{ + assert(rbtree_node_check_alignment(node)); + assert(rbtree_node_check_alignment(parent)); + + node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK); +} + +/* + * Set the color of a node, retaining its current parent. + */ +static inline void +rbtree_node_set_color(struct rbtree_node *node, int color) +{ + assert((color & ~RBTREE_COLOR_MASK) == 0); + node->parent = (node->parent & RBTREE_PARENT_MASK) | color; +} + +/* + * Set the color of a node to red, retaining its current parent. + */ +static inline void +rbtree_node_set_red(struct rbtree_node *node) +{ + rbtree_node_set_color(node, RBTREE_COLOR_RED); +} + +/* + * Set the color of a node to black, retaining its current parent. + */ +static inline void +rbtree_node_set_black(struct rbtree_node *node) +{ + rbtree_node_set_color(node, RBTREE_COLOR_BLACK); +} + +/* + * Return the left-most deepest child node of the given node. + */ +static struct rbtree_node * +rbtree_node_find_deepest(struct rbtree_node *node) +{ + struct rbtree_node *parent; + + assert(node != NULL); + + for (;;) { + parent = node; + node = node->children[RBTREE_LEFT]; + + if (node == NULL) { + node = parent->children[RBTREE_RIGHT]; + + if (node == NULL) + return parent; + } + } +} + +/* + * Perform a tree rotation, rooted at the given node. + * + * The direction parameter defines the rotation direction and is either + * RBTREE_LEFT or RBTREE_RIGHT. + */ +static void +rbtree_rotate(struct rbtree *tree, struct rbtree_node *node, int direction) +{ + struct rbtree_node *parent, *rnode; + int left, right; + + left = direction; + right = 1 - left; + parent = rbtree_node_parent(node); + rnode = node->children[right]; + + node->children[right] = rnode->children[left]; + + if (rnode->children[left] != NULL) + rbtree_node_set_parent(rnode->children[left], node); + + rnode->children[left] = node; + rbtree_node_set_parent(rnode, parent); + + if (unlikely(parent == NULL)) + tree->root = rnode; + else + parent->children[rbtree_node_index(node, parent)] = rnode; + + rbtree_node_set_parent(node, rnode); +} + +void +rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, + int index, struct rbtree_node *node) +{ + struct rbtree_node *grand_parent, *uncle, *tmp; + int left, right; + + assert(rbtree_node_check_alignment(parent)); + assert(rbtree_node_check_alignment(node)); + + node->parent = (unsigned long)parent | RBTREE_COLOR_RED; + node->children[RBTREE_LEFT] = NULL; + node->children[RBTREE_RIGHT] = NULL; + + if (unlikely(parent == NULL)) + tree->root = node; + else + parent->children[index] = node; + + for (;;) { + if (parent == NULL) { + rbtree_node_set_black(node); + break; + } + + if (rbtree_node_is_black(parent)) + break; + + grand_parent = rbtree_node_parent(parent); + assert(grand_parent != NULL); + + left = rbtree_node_index(parent, grand_parent); + right = 1 - left; + + uncle = grand_parent->children[right]; + + /* + * Uncle is red. Flip colors and repeat at grand parent. + */ + if ((uncle != NULL) && rbtree_node_is_red(uncle)) { + rbtree_node_set_black(uncle); + rbtree_node_set_black(parent); + rbtree_node_set_red(grand_parent); + node = grand_parent; + parent = rbtree_node_parent(node); + continue; + } + + /* + * Node is the right child of its parent. Rotate left at parent. + */ + if (parent->children[right] == node) { + rbtree_rotate(tree, parent, left); + tmp = node; + node = parent; + parent = tmp; + } + + /* + * Node is the left child of its parent. Handle colors, rotate right + * at grand parent, and leave. + */ + rbtree_node_set_black(parent); + rbtree_node_set_red(grand_parent); + rbtree_rotate(tree, grand_parent, right); + break; + } + + assert(rbtree_node_is_black(tree->root)); +} + +void +rbtree_remove(struct rbtree *tree, struct rbtree_node *node) +{ + struct rbtree_node *child, *parent, *brother; + int color, left, right; + + if (node->children[RBTREE_LEFT] == NULL) + child = node->children[RBTREE_RIGHT]; + else if (node->children[RBTREE_RIGHT] == NULL) + child = node->children[RBTREE_LEFT]; + else { + struct rbtree_node *successor; + + /* + * Two-children case: replace the node with its successor. + */ + + successor = node->children[RBTREE_RIGHT]; + + while (successor->children[RBTREE_LEFT] != NULL) + successor = successor->children[RBTREE_LEFT]; + + color = rbtree_node_color(successor); + child = successor->children[RBTREE_RIGHT]; + parent = rbtree_node_parent(node); + + if (unlikely(parent == NULL)) + tree->root = successor; + else + parent->children[rbtree_node_index(node, parent)] = successor; + + parent = rbtree_node_parent(successor); + + /* + * Set parent directly to keep the original color. + */ + successor->parent = node->parent; + successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT]; + rbtree_node_set_parent(successor->children[RBTREE_LEFT], successor); + + if (node == parent) + parent = successor; + else { + successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT]; + rbtree_node_set_parent(successor->children[RBTREE_RIGHT], + successor); + parent->children[RBTREE_LEFT] = child; + + if (child != NULL) + rbtree_node_set_parent(child, parent); + } + + goto update_color; + } + + /* + * Node has at most one child. + */ + + color = rbtree_node_color(node); + parent = rbtree_node_parent(node); + + if (child != NULL) + rbtree_node_set_parent(child, parent); + + if (unlikely(parent == NULL)) + tree->root = child; + else + parent->children[rbtree_node_index(node, parent)] = child; + + /* + * The node has been removed, update the colors. The child pointer can + * be null, in which case it is considered a black leaf. + */ +update_color: + if (color == RBTREE_COLOR_RED) + return; + + for (;;) { + if ((child != NULL) && rbtree_node_is_red(child)) { + rbtree_node_set_black(child); + break; + } + + if (parent == NULL) + break; + + left = rbtree_node_index(child, parent); + right = 1 - left; + + brother = parent->children[right]; + + /* + * Brother is red. Recolor and rotate left at parent so that brother + * becomes black. + */ + if (rbtree_node_is_red(brother)) { + rbtree_node_set_black(brother); + rbtree_node_set_red(parent); + rbtree_rotate(tree, parent, left); + brother = parent->children[right]; + } + + /* + * Brother has no red child. Recolor and repeat at parent. + */ + if (((brother->children[RBTREE_LEFT] == NULL) + || rbtree_node_is_black(brother->children[RBTREE_LEFT])) + && ((brother->children[RBTREE_RIGHT] == NULL) + || rbtree_node_is_black(brother->children[RBTREE_RIGHT]))) { + rbtree_node_set_red(brother); + child = parent; + parent = rbtree_node_parent(child); + continue; + } + + /* + * Brother's right child is black. Recolor and rotate right at brother. + */ + if ((brother->children[right] == NULL) + || rbtree_node_is_black(brother->children[right])) { + rbtree_node_set_black(brother->children[left]); + rbtree_node_set_red(brother); + rbtree_rotate(tree, brother, right); + brother = parent->children[right]; + } + + /* + * Brother's left child is black. Exchange parent and brother colors + * (we already know brother is black), set brother's right child black, + * rotate left at parent and leave. + */ + rbtree_node_set_color(brother, rbtree_node_color(parent)); + rbtree_node_set_black(parent); + rbtree_node_set_black(brother->children[right]); + rbtree_rotate(tree, parent, left); + break; + } + + assert((tree->root == NULL) || rbtree_node_is_black(tree->root)); +} + +struct rbtree_node * +rbtree_nearest(struct rbtree_node *parent, int index, int direction) +{ + assert(rbtree_check_index(direction)); + + if (parent == NULL) + return NULL; + + assert(rbtree_check_index(index)); + + if (index != direction) + return parent; + + return rbtree_walk(parent, direction); +} + +struct rbtree_node * +rbtree_firstlast(const struct rbtree *tree, int direction) +{ + struct rbtree_node *prev, *cur; + + assert(rbtree_check_index(direction)); + + prev = NULL; + + for (cur = tree->root; cur != NULL; cur = cur->children[direction]) + prev = cur; + + return prev; +} + +struct rbtree_node * +rbtree_walk(struct rbtree_node *node, int direction) +{ + int left, right; + + assert(rbtree_check_index(direction)); + + left = direction; + right = 1 - left; + + if (node == NULL) + return NULL; + + if (node->children[left] != NULL) { + node = node->children[left]; + + while (node->children[right] != NULL) + node = node->children[right]; + } else { + struct rbtree_node *parent; + int index; + + for (;;) { + parent = rbtree_node_parent(node); + + if (parent == NULL) + return NULL; + + index = rbtree_node_index(node, parent); + node = parent; + + if (index == right) + break; + } + } + + return node; +} + +struct rbtree_node * +rbtree_postwalk_deepest(const struct rbtree *tree) +{ + struct rbtree_node *node; + + node = tree->root; + + if (node == NULL) + return NULL; + + return rbtree_node_find_deepest(node); +} + +struct rbtree_node * +rbtree_postwalk_unlink(struct rbtree_node *node) +{ + struct rbtree_node *parent; + int index; + + if (node == NULL) + return NULL; + + assert(node->children[RBTREE_LEFT] == NULL); + assert(node->children[RBTREE_RIGHT] == NULL); + + parent = rbtree_node_parent(node); + + if (parent == NULL) + return NULL; + + index = rbtree_node_index(node, parent); + parent->children[index] = NULL; + node = parent->children[RBTREE_RIGHT]; + + if (node == NULL) + return parent; + + return rbtree_node_find_deepest(node); +} diff --git a/kern/rbtree.h b/kern/rbtree.h new file mode 100644 index 00000000..45521c13 --- /dev/null +++ b/kern/rbtree.h @@ -0,0 +1,299 @@ +/* + * Copyright (c) 2010, 2011, 2012 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * + * Red-black tree. + */ + +#ifndef _KERN_RBTREE_H +#define _KERN_RBTREE_H + +#include +#include +#include + +/* + * Indexes of the left and right nodes in the children array of a node. + */ +#define RBTREE_LEFT 0 +#define RBTREE_RIGHT 1 + +/* + * Red-black node. + */ +struct rbtree_node; + +/* + * Red-black tree. + */ +struct rbtree; + +/* + * Static tree initializer. + */ +#define RBTREE_INITIALIZER { NULL } + +#include + +/* + * Initialize a tree. + */ +static inline void +rbtree_init(struct rbtree *tree) +{ + tree->root = NULL; +} + +/* + * Initialize a node. + * + * A node is in no tree when its parent points to itself. + */ +static inline void +rbtree_node_init(struct rbtree_node *node) +{ + assert(rbtree_node_check_alignment(node)); + + node->parent = (unsigned long)node | RBTREE_COLOR_RED; + node->children[RBTREE_LEFT] = NULL; + node->children[RBTREE_RIGHT] = NULL; +} + +/* + * Return true if node is in no tree. + */ +static inline int +rbtree_node_unlinked(const struct rbtree_node *node) +{ + return rbtree_node_parent(node) == node; +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define rbtree_entry(node, type, member) structof(node, type, member) + +/* + * Return true if tree is empty. + */ +static inline int +rbtree_empty(const struct rbtree *tree) +{ + return tree->root == NULL; +} + +/* + * Look up a node in a tree. + * + * Note that implementing the lookup algorithm as a macro gives two benefits: + * First, it avoids the overhead of a callback function. Next, the type of the + * cmp_fn parameter isn't rigid. The only guarantee offered by this + * implementation is that the key parameter is the first parameter given to + * cmp_fn. This way, users can pass only the value they need for comparison + * instead of e.g. allocating a full structure on the stack. + * + * See rbtree_insert(). + */ +#define rbtree_lookup(tree, key, cmp_fn) \ +MACRO_BEGIN \ + struct rbtree_node *cur; \ + int diff; \ + \ + cur = (tree)->root; \ + \ + while (cur != NULL) { \ + diff = cmp_fn(key, cur); \ + \ + if (diff == 0) \ + break; \ + \ + cur = cur->children[rbtree_d2i(diff)]; \ + } \ + \ + cur; \ +MACRO_END + +/* + * Look up a node or one of its nearest nodes in a tree. + * + * This macro essentially acts as rbtree_lookup() but if no entry matched + * the key, an additional step is performed to obtain the next or previous + * node, depending on the direction (left or right). + * + * The constraints that apply to the key parameter are the same as for + * rbtree_lookup(). + */ +#define rbtree_lookup_nearest(tree, key, cmp_fn, dir) \ +MACRO_BEGIN \ + struct rbtree_node *cur, *prev; \ + int diff, index; \ + \ + prev = NULL; \ + index = -1; \ + cur = (tree)->root; \ + \ + while (cur != NULL) { \ + diff = cmp_fn(key, cur); \ + \ + if (diff == 0) \ + break; \ + \ + prev = cur; \ + index = rbtree_d2i(diff); \ + cur = cur->children[index]; \ + } \ + \ + if (cur == NULL) \ + cur = rbtree_nearest(prev, index, dir); \ + \ + cur; \ +MACRO_END + +/* + * Insert a node in a tree. + * + * This macro performs a standard lookup to obtain the insertion point of + * the given node in the tree (it is assumed that the inserted node never + * compares equal to any other entry in the tree) and links the node. It + * then checks red-black rules violations, and rebalances the tree if + * necessary. + * + * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete + * entries, so it is suggested to use two different comparison inline + * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no + * guarantee about the order of the nodes given to the comparison function. + * + * See rbtree_lookup(). + */ +#define rbtree_insert(tree, node, cmp_fn) \ +MACRO_BEGIN \ + struct rbtree_node *cur, *prev; \ + int diff, index; \ + \ + prev = NULL; \ + index = -1; \ + cur = (tree)->root; \ + \ + while (cur != NULL) { \ + diff = cmp_fn(node, cur); \ + assert(diff != 0); \ + prev = cur; \ + index = rbtree_d2i(diff); \ + cur = cur->children[index]; \ + } \ + \ + rbtree_insert_rebalance(tree, prev, index, node); \ +MACRO_END + +/* + * Look up a node/slot pair in a tree. + * + * This macro essentially acts as rbtree_lookup() but in addition to a node, + * it also returns a slot, which identifies an insertion point in the tree. + * If the returned node is null, the slot can be used by rbtree_insert_slot() + * to insert without the overhead of an additional lookup. The slot is a + * simple unsigned long integer. + * + * The constraints that apply to the key parameter are the same as for + * rbtree_lookup(). + */ +#define rbtree_lookup_slot(tree, key, cmp_fn, slot) \ +MACRO_BEGIN \ + struct rbtree_node *cur, *prev; \ + int diff, index; \ + \ + prev = NULL; \ + index = 0; \ + cur = (tree)->root; \ + \ + while (cur != NULL) { \ + diff = cmp_fn(key, cur); \ + \ + if (diff == 0) \ + break; \ + \ + prev = cur; \ + index = rbtree_d2i(diff); \ + cur = cur->children[index]; \ + } \ + \ + (slot) = rbtree_slot(prev, index); \ + cur; \ +MACRO_END + +/* + * Insert a node at an insertion point in a tree. + * + * This macro essentially acts as rbtree_insert() except that it doesn't + * obtain the insertion point with a standard lookup. The insertion point + * is obtained by calling rbtree_lookup_slot(). In addition, the new node + * must not compare equal to an existing node in the tree (i.e. the slot + * must denote a null node). + */ +#define rbtree_insert_slot(tree, slot, node) \ +MACRO_BEGIN \ + struct rbtree_node *parent; \ + int index; \ + \ + parent = rbtree_slot_parent(slot); \ + index = rbtree_slot_index(slot); \ + rbtree_insert_rebalance(tree, parent, index, node); \ +MACRO_END + +/* + * Remove a node from a tree. + * + * After completion, the node is stale. + */ +void rbtree_remove(struct rbtree *tree, struct rbtree_node *node); + +/* + * Return the first node of a tree. + */ +#define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT) + +/* + * Return the last node of a tree. + */ +#define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT) + +/* + * Return the node previous to the given node. + */ +#define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT) + +/* + * Return the node next to the given node. + */ +#define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT) + +/* + * Forge a loop to process all nodes of a tree, removing them when visited. + * + * This macro can only be used to destroy a tree, so that the resources used + * by the entries can be released by the user. It basically removes all nodes + * without doing any color checking. + * + * After completion, all nodes and the tree root member are stale. + */ +#define rbtree_for_each_remove(tree, node, tmp) \ +for (node = rbtree_postwalk_deepest(tree), \ + tmp = rbtree_postwalk_unlink(node); \ + node != NULL; \ + node = tmp, tmp = rbtree_postwalk_unlink(node)) \ + +#endif /* _KERN_RBTREE_H */ diff --git a/kern/rbtree_i.h b/kern/rbtree_i.h new file mode 100644 index 00000000..7f9650e7 --- /dev/null +++ b/kern/rbtree_i.h @@ -0,0 +1,187 @@ +/* + * Copyright (c) 2010, 2011, 2012 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_RBTREE_I_H +#define _KERN_RBTREE_I_H + +#include +#include +#include + +/* + * Red-black node structure. + * + * To reduce the number of branches and the instruction cache footprint, + * the left and right child pointers are stored in an array, and the symmetry + * of most tree operations is exploited by using left/right variables when + * referring to children. + * + * In addition, this implementation assumes that all nodes are 4-byte aligned, + * so that the least significant bit of the parent member can be used to store + * the color of the node. This is true for all modern 32 and 64 bits + * architectures, as long as the nodes aren't embedded in structures with + * special alignment constraints such as member packing. + */ +struct rbtree_node { + unsigned long parent; + struct rbtree_node *children[2]; +}; + +/* + * Red-black tree structure. + */ +struct rbtree { + struct rbtree_node *root; +}; + +/* + * Masks applied on the parent member of a node to obtain either the + * color or the parent address. + */ +#define RBTREE_COLOR_MASK 0x1UL +#define RBTREE_PARENT_MASK (~0x3UL) + +/* + * Node colors. + */ +#define RBTREE_COLOR_RED 0 +#define RBTREE_COLOR_BLACK 1 + +/* + * Masks applied on slots to obtain either the child index or the parent + * address. + */ +#define RBTREE_SLOT_INDEX_MASK 0x1UL +#define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK) + +/* + * Return true if the given index is a valid child index. + */ +static inline int +rbtree_check_index(int index) +{ + return index == (index & 1); +} + +/* + * Convert the result of a comparison into an index in the children array + * (0 or 1). + * + * This function is mostly used when looking up a node. + */ +static inline int +rbtree_d2i(int diff) +{ + return !(diff <= 0); +} + +/* + * Return true if the given pointer is suitably aligned. + */ +static inline int +rbtree_node_check_alignment(const struct rbtree_node *node) +{ + return ((unsigned long)node & (~RBTREE_PARENT_MASK)) == 0; +} + +/* + * Return the parent of a node. + */ +static inline struct rbtree_node * +rbtree_node_parent(const struct rbtree_node *node) +{ + return (struct rbtree_node *)(node->parent & RBTREE_PARENT_MASK); +} + +/* + * Translate an insertion point into a slot. + */ +static inline unsigned long +rbtree_slot(struct rbtree_node *parent, int index) +{ + assert(rbtree_node_check_alignment(parent)); + assert(rbtree_check_index(index)); + return (unsigned long)parent | index; +} + +/* + * Extract the parent address from a slot. + */ +static inline struct rbtree_node * +rbtree_slot_parent(unsigned long slot) +{ + return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK); +} + +/* + * Extract the index from a slot. + */ +static inline int +rbtree_slot_index(unsigned long slot) +{ + return slot & RBTREE_SLOT_INDEX_MASK; +} + +/* + * Insert a node in a tree, rebalancing it if necessary. + * + * The index parameter is the index in the children array of the parent where + * the new node is to be inserted. It is ignored if the parent is null. + * + * This function is intended to be used by the rbtree_insert() macro only. + */ +void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, + int index, struct rbtree_node *node); + +/* + * Return the previous or next node relative to a location in a tree. + * + * The parent and index parameters define the location, which can be empty. + * The direction parameter is either RBTREE_LEFT (to obtain the previous + * node) or RBTREE_RIGHT (to obtain the next one). + */ +struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index, + int direction); + +/* + * Return the first or last node of a tree. + * + * The direction parameter is either RBTREE_LEFT (to obtain the first node) + * or RBTREE_RIGHT (to obtain the last one). + */ +struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction); + +/* + * Return the node next to, or previous to the given node. + * + * The direction parameter is either RBTREE_LEFT (to obtain the previous node) + * or RBTREE_RIGHT (to obtain the next one). + */ +struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction); + +/* + * Return the left-most deepest node of a tree, which is the starting point of + * the postorder traversal performed by rbtree_for_each_remove(). + */ +struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree); + +/* + * Unlink a node from its tree and return the next (right) node in postorder. + */ +struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node); + +#endif /* _KERN_RBTREE_I_H */ diff --git a/kern/sprintf.c b/kern/sprintf.c new file mode 100644 index 00000000..13f2671e --- /dev/null +++ b/kern/sprintf.c @@ -0,0 +1,550 @@ +/* + * Copyright (c) 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include + +#include +#include +#include +#include + +/* + * Formatting flags. + * + * FORMAT_LOWER must be 0x20 as it is OR'd with digits, eg. + * '0': 0x30 | 0x20 => 0x30 ('0') + * 'A': 0x41 | 0x20 => 0x61 ('a') + */ +#define SPRINTF_FORMAT_ALT_FORM 0x01 +#define SPRINTF_FORMAT_ZERO_PAD 0x02 +#define SPRINTF_FORMAT_LEFT_JUSTIFY 0x04 +#define SPRINTF_FORMAT_BLANK 0x08 +#define SPRINTF_FORMAT_SIGN 0x10 +#define SPRINTF_FORMAT_LOWER 0x20 +#define SPRINTF_FORMAT_CONV_SIGNED 0x40 + +enum { + SPRINTF_MODIFIER_NONE, + SPRINTF_MODIFIER_CHAR, + SPRINTF_MODIFIER_SHORT, + SPRINTF_MODIFIER_LONG, + SPRINTF_MODIFIER_LONGLONG, + SPRINTF_MODIFIER_PTR, /* Used only for %p */ + SPRINTF_MODIFIER_SIZE, + SPRINTF_MODIFIER_PTRDIFF +}; + +enum { + SPRINTF_SPECIFIER_INVALID, + SPRINTF_SPECIFIER_INT, + SPRINTF_SPECIFIER_CHAR, + SPRINTF_SPECIFIER_STR, + SPRINTF_SPECIFIER_NRCHARS, + SPRINTF_SPECIFIER_PERCENT +}; + +/* + * Size for the temporary number buffer. The minimum base is 8 so 3 bits + * are consumed per digit. Add one to round up. The conversion algorithm + * doesn't use the null byte. + */ +#define SPRINTF_MAX_NUM_SIZE (((sizeof(uint64_t) * CHAR_BIT) / 3) + 1) + +/* + * Special size for vsnprintf(), used by sprintf()/vsprintf() when the + * buffer size is unknown. + */ +#define SPRINTF_NOLIMIT ((size_t)-1) + +static const char sprintf_digits[] = "0123456789ABCDEF"; + +static inline char * +sprintf_putchar(char *str, char *end, char c) +{ + if (str < end) + *str = c; + + str++; + + return str; +} + +static inline int +sprintf_isdigit(char c) +{ + return (c >= '0') && (c <= '9'); +} + +int +sprintf(char *str, const char *format, ...) +{ + va_list ap; + int length; + + va_start(ap, format); + length = vsprintf(str, format, ap); + va_end(ap); + + return length; +} + +int +vsprintf(char *str, const char *format, va_list ap) +{ + return vsnprintf(str, SPRINTF_NOLIMIT, format, ap); +} + +int +snprintf(char *str, size_t size, const char *format, ...) +{ + va_list ap; + int length; + + va_start(ap, format); + length = vsnprintf(str, size, format, ap); + va_end(ap); + + return length; +} + +int +vsnprintf(char *str, size_t size, const char *format, va_list ap) +{ + unsigned long long n; + int i, len, found, flags, width, precision, modifier, specifier, shift; + unsigned char r, base, mask; + char c, *s, *start, *end, sign, tmp[SPRINTF_MAX_NUM_SIZE]; + + start = str; + + if (size == 0) + end = NULL; + else if (size == SPRINTF_NOLIMIT) + end = (char *)-1; + else + end = start + size - 1; + + while ((c = *format) != '\0') { + if (c != '%') { + str = sprintf_putchar(str, end, c); + format++; + continue; + } + + /* Flags */ + + found = 1; + flags = 0; + + do { + format++; + c = *format; + + switch (c) { + case '#': + flags |= SPRINTF_FORMAT_ALT_FORM; + break; + case '0': + flags |= SPRINTF_FORMAT_ZERO_PAD; + break; + case '-': + flags |= SPRINTF_FORMAT_LEFT_JUSTIFY; + break; + case ' ': + flags |= SPRINTF_FORMAT_BLANK; + break; + case '+': + flags |= SPRINTF_FORMAT_SIGN; + break; + default: + found = 0; + break; + } + } while (found); + + /* Width */ + + if (sprintf_isdigit(c)) { + width = 0; + + while (sprintf_isdigit(c)) { + width = width * 10 + (c - '0'); + format++; + c = *format; + } + } else if (c == '*') { + width = va_arg(ap, int); + + if (width < 0) { + flags |= SPRINTF_FORMAT_LEFT_JUSTIFY; + width = -width; + } + + format++; + c = *format; + } else { + width = 0; + } + + /* Precision */ + + if (c == '.') { + format++; + c = *format; + + if (sprintf_isdigit(c)) { + precision = 0; + + while (sprintf_isdigit(c)) { + precision = precision * 10 + (c - '0'); + format++; + c = *format; + } + } else if (c == '*') { + precision = va_arg(ap, int); + + if (precision < 0) + precision = 0; + + format++; + c = *format; + } else { + precision = 0; + } + } else { + /* precision is >= 0 only if explicit */ + precision = -1; + } + + /* Length modifier */ + + switch (c) { + case 'h': + case 'l': + format++; + + if (c == *format) { + modifier = (c == 'h') + ? SPRINTF_MODIFIER_CHAR + : SPRINTF_MODIFIER_LONGLONG; + goto skip_modifier; + } else { + modifier = (c == 'h') + ? SPRINTF_MODIFIER_SHORT + : SPRINTF_MODIFIER_LONG; + c = *format; + } + + break; + case 'z': + modifier = SPRINTF_MODIFIER_SIZE; + goto skip_modifier; + case 't': + modifier = SPRINTF_MODIFIER_PTRDIFF; +skip_modifier: + format++; + c = *format; + break; + default: + modifier = SPRINTF_MODIFIER_NONE; + break; + } + + /* Specifier */ + + switch (c) { + case 'd': + case 'i': + flags |= SPRINTF_FORMAT_CONV_SIGNED; + case 'u': + base = 10; + goto integer; + case 'o': + base = 8; + goto integer; + case 'p': + flags |= SPRINTF_FORMAT_ALT_FORM; + modifier = SPRINTF_MODIFIER_PTR; + case 'x': + flags |= SPRINTF_FORMAT_LOWER; + case 'X': + base = 16; +integer: + specifier = SPRINTF_SPECIFIER_INT; + break; + case 'c': + specifier = SPRINTF_SPECIFIER_CHAR; + break; + case 's': + specifier = SPRINTF_SPECIFIER_STR; + break; + case 'n': + specifier = SPRINTF_SPECIFIER_NRCHARS; + break; + case '%': + specifier = SPRINTF_SPECIFIER_PERCENT; + break; + default: + specifier = SPRINTF_SPECIFIER_INVALID; + break; + } + + /* Output */ + + switch (specifier) { + case SPRINTF_SPECIFIER_INT: + switch (modifier) { + case SPRINTF_MODIFIER_CHAR: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = (signed char)va_arg(ap, int); + else + n = (unsigned char)va_arg(ap, int); + break; + case SPRINTF_MODIFIER_SHORT: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = (short)va_arg(ap, int); + else + n = (unsigned short)va_arg(ap, int); + break; + case SPRINTF_MODIFIER_LONG: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = va_arg(ap, long); + else + n = va_arg(ap, unsigned long); + break; + case SPRINTF_MODIFIER_LONGLONG: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = va_arg(ap, long long); + else + n = va_arg(ap, unsigned long long); + break; + case SPRINTF_MODIFIER_PTR: + n = (unsigned long)va_arg(ap, void *); + break; + case SPRINTF_MODIFIER_SIZE: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = va_arg(ap, ssize_t); + else + n = va_arg(ap, size_t); + break; + case SPRINTF_MODIFIER_PTRDIFF: + n = va_arg(ap, ptrdiff_t); + break; + default: + if (flags & SPRINTF_FORMAT_CONV_SIGNED) + n = va_arg(ap, int); + else + n = va_arg(ap, unsigned int); + break; + } + + if ((flags & SPRINTF_FORMAT_LEFT_JUSTIFY) || (precision >= 0)) + flags &= ~SPRINTF_FORMAT_ZERO_PAD; + + sign = 0; + + if (flags & SPRINTF_FORMAT_ALT_FORM) { + /* '0' for octal */ + width--; + + /* '0x' or '0X' for hexadecimal */ + if (base == 16) + width--; + } else if (flags & SPRINTF_FORMAT_CONV_SIGNED) { + if ((long long)n < 0) { + sign = '-'; + width--; + n = -(long long)n; + } else if (flags & SPRINTF_FORMAT_SIGN) { + /* SPRINTF_FORMAT_SIGN must precede SPRINTF_FORMAT_BLANK. */ + sign = '+'; + width--; + } else if (flags & SPRINTF_FORMAT_BLANK) { + sign = ' '; + width--; + } + } + + /* Conversion, in reverse order */ + + i = 0; + + if (n == 0) { + if (precision != 0) + tmp[i++] = '0'; + } else if (base == 10) { + /* + * Try to avoid 64 bits operations if the processor doesn't + * support them. Note that even when using modulus and + * division operators close to each other, the compiler will + * forge two calls to __udivdi3() and __umoddi3() instead of + * one to __udivmoddi3(), whereas processor instructions are + * generally correctly used once, giving both the remainder + * and the quotient, through plain or reciprocal division. + */ +#ifndef __LP64__ + if (modifier == SPRINTF_MODIFIER_LONGLONG) { +#endif /* __LP64__ */ + do { + r = n % 10; + n /= 10; + tmp[i++] = sprintf_digits[r]; + } while (n != 0); +#ifndef __LP64__ + } else { + unsigned long m; + + m = (unsigned long)n; + + do { + r = m % 10; + m /= 10; + tmp[i++] = sprintf_digits[r]; + } while (m != 0); + } +#endif /* __LP64__ */ + } else { + mask = base - 1; + shift = (base == 8) ? 3 : 4; + + do { + r = (unsigned char)n & mask; + n >>= shift; + tmp[i++] = sprintf_digits[r] + | (flags & SPRINTF_FORMAT_LOWER); + } while (n != 0); + } + + if (i > precision) + precision = i; + + width -= precision; + + if (!(flags & (SPRINTF_FORMAT_LEFT_JUSTIFY + | SPRINTF_FORMAT_ZERO_PAD))) + while (width-- > 0) + str = sprintf_putchar(str, end, ' '); + + if (flags & SPRINTF_FORMAT_ALT_FORM) { + str = sprintf_putchar(str, end, '0'); + + if (base == 16) + str = sprintf_putchar(str, end, + 'X' | (flags & SPRINTF_FORMAT_LOWER)); + } else if (sign) { + str = sprintf_putchar(str, end, sign); + } + + if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) { + c = (flags & SPRINTF_FORMAT_ZERO_PAD) ? '0' : ' '; + + while (width-- > 0) + str = sprintf_putchar(str, end, c); + } + + while (i < precision--) + str = sprintf_putchar(str, end, '0'); + + while (i-- > 0) + str = sprintf_putchar(str, end, tmp[i]); + + while (width-- > 0) + str = sprintf_putchar(str, end, ' '); + + break; + case SPRINTF_SPECIFIER_CHAR: + c = (unsigned char)va_arg(ap, int); + + if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) + while (--width > 0) + str = sprintf_putchar(str, end, ' '); + + str = sprintf_putchar(str, end, c); + + while (--width > 0) + str = sprintf_putchar(str, end, ' '); + + break; + case SPRINTF_SPECIFIER_STR: + s = va_arg(ap, char *); + + if (s == NULL) + s = "(null)"; + + len = 0; + + for (len = 0; s[len] != '\0'; len++) + if (len == precision) + break; + + if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) + while (len < width--) + str = sprintf_putchar(str, end, ' '); + + for (i = 0; i < len; i++) { + str = sprintf_putchar(str, end, *s); + s++; + } + + while (len < width--) + str = sprintf_putchar(str, end, ' '); + + break; + case SPRINTF_SPECIFIER_NRCHARS: + if (modifier == SPRINTF_MODIFIER_CHAR) { + signed char *ptr = va_arg(ap, signed char *); + *ptr = str - start; + } else if (modifier == SPRINTF_MODIFIER_SHORT) { + short *ptr = va_arg(ap, short *); + *ptr = str - start; + } else if (modifier == SPRINTF_MODIFIER_LONG) { + long *ptr = va_arg(ap, long *); + *ptr = str - start; + } else if (modifier == SPRINTF_MODIFIER_LONGLONG) { + long long *ptr = va_arg(ap, long long *); + *ptr = str - start; + } else if (modifier == SPRINTF_MODIFIER_SIZE) { + ssize_t *ptr = va_arg(ap, ssize_t *); + *ptr = str - start; + } else if (modifier == SPRINTF_MODIFIER_PTRDIFF) { + ptrdiff_t *ptr = va_arg(ap, ptrdiff_t *); + *ptr = str - start; + } else { + int *ptr = va_arg(ap, int *); + *ptr = str - start; + } + + break; + case SPRINTF_SPECIFIER_PERCENT: + case SPRINTF_SPECIFIER_INVALID: + str = sprintf_putchar(str, end, '%'); + break; + default: + break; + } + + if (specifier != SPRINTF_SPECIFIER_INVALID) + format++; + } + + if (str < end) + *str = '\0'; + else if (end != NULL) + *end = '\0'; + + return str - start; +} diff --git a/kern/sprintf.h b/kern/sprintf.h new file mode 100644 index 00000000..0c097953 --- /dev/null +++ b/kern/sprintf.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2010 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * + * Formatted string functions. + * + * The functions provided by this module implement a subset of the C99 + * sprintf() like functions, mostly centered around character, string, and + * integer conversions. + * + * The supported specifiers are: d i o u x X c s p n % + * The supported length modifiers are: hh h l ll z t + */ + +#ifndef _KERN_SPRINTF_H +#define _KERN_SPRINTF_H + +#include + +#include + +int sprintf(char *str, const char *format, ...) __format_printf(2, 3); +int vsprintf(char *str, const char *format, va_list ap) __format_printf(2, 0); + +int snprintf(char *str, size_t size, const char *format, ...) + __format_printf(3, 4); +int vsnprintf(char *str, size_t size, const char *format, va_list ap) + __format_printf(3, 0); + +#endif /* _KERN_SPRINTF_H */ diff --git a/kern/stddef.h b/kern/stddef.h new file mode 100644 index 00000000..b07c9924 --- /dev/null +++ b/kern/stddef.h @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2010, 2011 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_STDDEF_H +#define _KERN_STDDEF_H + +#define NULL ((void *)0) + +#define offsetof(type, member) __builtin_offsetof(type, member) + +#ifdef __LP64__ +typedef unsigned long size_t; +typedef long ssize_t; +typedef long ptrdiff_t; +#else /* __LP64__ */ +typedef unsigned int size_t; +typedef int ssize_t; +typedef int ptrdiff_t; +#endif /* __LP64__ */ + +#endif /* _KERN_STDDEF_H */ diff --git a/kern/stdint.h b/kern/stdint.h new file mode 100644 index 00000000..d6794c4e --- /dev/null +++ b/kern/stdint.h @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2010, 2011 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_STDINT_H +#define _KERN_STDINT_H + +typedef signed char int8_t; +typedef unsigned char uint8_t; +typedef signed short int16_t; +typedef unsigned short uint16_t; +typedef signed int int32_t; +typedef unsigned int uint32_t; +typedef signed long long int64_t; +typedef unsigned long long uint64_t; + +#endif /* _KERN_STDINT_H */ diff --git a/kern/string.c b/kern/string.c new file mode 100644 index 00000000..82bcd2f1 --- /dev/null +++ b/kern/string.c @@ -0,0 +1,138 @@ +/* + * Copyright (c) 2012 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * + * Trivial, portable implementations. + */ + +#include +#include + +void * +memcpy(void *dest, const void *src, size_t n) +{ + const char *src_ptr; + char *dest_ptr; + size_t i; + + dest_ptr = dest; + src_ptr = src; + + for (i = 0; i < n; i++) + *dest_ptr++ = *src_ptr++; + + return dest; +} + +void * +memmove(void *dest, const void *src, size_t n) +{ + const char *src_ptr; + char *dest_ptr; + size_t i; + + if (src == dest) + return dest; + else if (src < dest) { + dest_ptr = (char *)dest + n - 1; + src_ptr = (const char *)src + n - 1; + + for (i = 0; i < n; i++) + *dest_ptr-- = *src_ptr--; + } else if (src > dest) { + dest_ptr = dest; + src_ptr = src; + + for (i = 0; i < n; i++) + *dest_ptr++ = *src_ptr++; + } + + return dest; +} + +void * +memset(void *s, int c, size_t n) +{ + char *buffer; + size_t i; + + buffer = s; + + for (i = 0; i < n; i++) + buffer[i] = c; + + return s; +} + +int +memcmp(const void *s1, const void *s2, size_t n) +{ + const char *a1, *a2; + size_t i; + + a1 = s1; + a2 = s2; + + for (i = 0; i < n; i++) + if (a1[i] != a2[i]) + return a2[i] - a1[i]; + + return 0; +} + +size_t +strlen(const char *s) +{ + size_t i; + + i = 0; + + while (*s++ != '\0') + i++; + + return i; +} + +char * +strcpy(char *dest, const char *src) +{ + char *tmp; + + tmp = dest; + + while ((*dest = *src) != '\0') { + dest++; + src++; + } + + return tmp; +} + +int +strcmp(const char *s1, const char *s2) +{ + char c1, c2; + + while ((c1 = *s1) == (c2 = *s2)) { + if (c1 == '\0') + return 0; + + s1++; + s2++; + } + + return (c1 < c2) ? -1 : 1; +} diff --git a/kern/string.h b/kern/string.h new file mode 100644 index 00000000..8dd4d9d0 --- /dev/null +++ b/kern/string.h @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2012 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _KERN_STRING_H +#define _KERN_STRING_H + +#include + +void * memcpy(void *dest, const void *src, size_t n); +void * memmove(void *dest, const void *src, size_t n); +void * memset(void *s, int c, size_t n); +int memcmp(const void *s1, const void *s2, size_t n); +size_t strlen(const char *s); +char * strcpy(char *dest, const char *src); +int strcmp(const char *s1, const char *s2); + +#endif /* _KERN_STRING_H */ diff --git a/lib/assert.h b/lib/assert.h deleted file mode 100644 index 79e23680..00000000 --- a/lib/assert.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * Copyright (c) 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_ASSERT_H -#define _LIB_ASSERT_H - -#ifdef NDEBUG -#define assert(expression) ((void)(expression)) -#else /* NDEBUG */ - -#include -#include - -/* - * Panic if the given expression is false. - */ -#define assert(expression) \ -MACRO_BEGIN \ - if (unlikely(!(expression))) \ - panic("assertion (%s) failed in %s:%d, function %s()", \ - __QUOTE(expression), __FILE__, __LINE__, __func__); \ -MACRO_END - -#endif /* NDEBUG */ - -#endif /* _LIB_ASSERT_H */ diff --git a/lib/limits.h b/lib/limits.h deleted file mode 100644 index 8f0bd4df..00000000 --- a/lib/limits.h +++ /dev/null @@ -1,23 +0,0 @@ -/* - * Copyright (c) 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_LIMITS_H -#define _LIB_LIMITS_H - -#define CHAR_BIT 8 - -#endif /* _LIB_LIMITS_H */ diff --git a/lib/list.h b/lib/list.h deleted file mode 100644 index b530d6c4..00000000 --- a/lib/list.h +++ /dev/null @@ -1,364 +0,0 @@ -/* - * Copyright (c) 2009, 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * - * Simple doubly-linked list. - */ - -#ifndef _LIB_LIST_H -#define _LIB_LIST_H - -#include -#include - -/* - * Structure used as both head and node. - * - * This implementation relies on using the same type for both heads and nodes. - * - * It is recommended to encode the use of struct list variables in their names, - * e.g. struct list free_list or struct list free_objects is a good hint for a - * list of free objects. A declaration like struct list free_node clearly - * indicates it is used as part of a node in the free list. - */ -struct list { - struct list *prev; - struct list *next; -}; - -/* - * Static list initializer. - */ -#define LIST_INITIALIZER(list) { &(list), &(list) } - -/* - * Initialize a list. - */ -static inline void -list_init(struct list *list) -{ - list->prev = list; - list->next = list; -} - -/* - * Initialize a list node. - * - * An entry is in no list when its node members point to NULL. - */ -static inline void -list_node_init(struct list *node) -{ - node->prev = NULL; - node->next = NULL; -} - -/* - * Return true if node is in no list. - */ -static inline int -list_node_unlinked(const struct list *node) -{ - return node->prev == NULL; -} - -/* - * Macro that evaluates to the address of the structure containing the - * given node based on the given type and member. - */ -#define list_entry(node, type, member) structof(node, type, member) - -/* - * Return the first node of a list. - */ -static inline struct list * -list_first(const struct list *list) -{ - return list->next; -} - -/* - * Return the last node of a list. - */ -static inline struct list * -list_last(const struct list *list) -{ - return list->prev; -} - -/* - * Return the node next to the given node. - */ -static inline struct list * -list_next(const struct list *node) -{ - return node->next; -} - -/* - * Return the node previous to the given node. - */ -static inline struct list * -list_prev(const struct list *node) -{ - return node->prev; -} - -/* - * Get the first entry of a list. - */ -#define list_first_entry(list, type, member) \ - list_entry(list_first(list), type, member) - -/* - * Get the last entry of a list. - */ -#define list_last_entry(list, type, member) \ - list_entry(list_last(list), type, member) - -/* - * Return true if node is after the last or before the first node of the list. - */ -static inline int -list_end(const struct list *list, const struct list *node) -{ - return list == node; -} - -/* - * Return true if list is empty. - */ -static inline int -list_empty(const struct list *list) -{ - return list == list->next; -} - -/* - * Return true if list contains exactly one node. - */ -static inline int -list_singular(const struct list *list) -{ - return (list != list->next) && (list->next == list->prev); -} - -/* - * Split list2 by moving its nodes up to (but not including) the given - * node into list1 (which can be in a stale state). - * - * If list2 is empty, or node is list2 or list2->next, nothing is done. - */ -static inline void -list_split(struct list *list1, struct list *list2, struct list *node) -{ - if (list_empty(list2) || (list2->next == node) || list_end(list2, node)) - return; - - list1->next = list2->next; - list1->next->prev = list1; - - list1->prev = node->prev; - node->prev->next = list1; - - list2->next = node; - node->prev = list2; -} - -/* - * Append the nodes of list2 at the end of list1. - * - * After completion, list2 is stale. - */ -static inline void -list_concat(struct list *list1, const struct list *list2) -{ - struct list *last1, *first2, *last2; - - if (list_empty(list2)) - return; - - last1 = list1->prev; - first2 = list2->next; - last2 = list2->prev; - - last1->next = first2; - first2->prev = last1; - - last2->next = list1; - list1->prev = last2; -} - -/* - * Set the new head of a list. - * - * This function is an optimized version of : - * list_init(&new_list); - * list_concat(&new_list, &old_list); - * - * After completion, old_head is stale. - */ -static inline void -list_set_head(struct list *new_head, const struct list *old_head) -{ - if (list_empty(old_head)) { - list_init(new_head); - return; - } - - *new_head = *old_head; - new_head->next->prev = new_head; - new_head->prev->next = new_head; -} - -/* - * Add a node between two nodes. - */ -static inline void -list_add(struct list *prev, struct list *next, struct list *node) -{ - next->prev = node; - node->next = next; - - prev->next = node; - node->prev = prev; -} - -/* - * Insert a node at the head of a list. - */ -static inline void -list_insert(struct list *list, struct list *node) -{ - list_add(list, list->next, node); -} - -/* - * Insert a node at the tail of a list. - */ -static inline void -list_insert_tail(struct list *list, struct list *node) -{ - list_add(list->prev, list, node); -} - -/* - * Insert a node before another node. - */ -static inline void -list_insert_before(struct list *next, struct list *node) -{ - list_add(next->prev, next, node); -} - -/* - * Insert a node after another node. - */ -static inline void -list_insert_after(struct list *prev, struct list *node) -{ - list_add(prev, prev->next, node); -} - -/* - * Remove a node from a list. - * - * After completion, the node is stale. - */ -static inline void -list_remove(struct list *node) -{ - node->prev->next = node->next; - node->next->prev = node->prev; -} - -/* - * Forge a loop to process all nodes of a list. - * - * The node must not be altered during the loop. - */ -#define list_for_each(list, node) \ -for (node = list_first(list); \ - !list_end(list, node); \ - node = list_next(node)) - -/* - * Forge a loop to process all nodes of a list. - */ -#define list_for_each_safe(list, node, tmp) \ -for (node = list_first(list), tmp = list_next(node); \ - !list_end(list, node); \ - node = tmp, tmp = list_next(node)) - -/* - * Version of list_for_each() that processes nodes backward. - */ -#define list_for_each_reverse(list, node) \ -for (node = list_last(list); \ - !list_end(list, node); \ - node = list_prev(node)) - -/* - * Version of list_for_each_safe() that processes nodes backward. - */ -#define list_for_each_reverse_safe(list, node, tmp) \ -for (node = list_last(list), tmp = list_prev(node); \ - !list_end(list, node); \ - node = tmp, tmp = list_prev(node)) - -/* - * Forge a loop to process all entries of a list. - * - * The entry node must not be altered during the loop. - */ -#define list_for_each_entry(list, entry, member) \ -for (entry = list_entry(list_first(list), typeof(*entry), member); \ - !list_end(list, &entry->member); \ - entry = list_entry(list_next(&entry->member), typeof(*entry), \ - member)) - -/* - * Forge a loop to process all entries of a list. - */ -#define list_for_each_entry_safe(list, entry, tmp, member) \ -for (entry = list_entry(list_first(list), typeof(*entry), member), \ - tmp = list_entry(list_next(&entry->member), typeof(*entry), \ - member); \ - !list_end(list, &entry->member); \ - entry = tmp, tmp = list_entry(list_next(&entry->member), \ - typeof(*entry), member)) - -/* - * Version of list_for_each_entry() that processes entries backward. - */ -#define list_for_each_entry_reverse(list, entry, member) \ -for (entry = list_entry(list_last(list), typeof(*entry), member); \ - !list_end(list, &entry->member); \ - entry = list_entry(list_prev(&entry->member), typeof(*entry), \ - member)) - -/* - * Version of list_for_each_entry_safe() that processes entries backward. - */ -#define list_for_each_entry_reverse_safe(list, entry, tmp, member) \ -for (entry = list_entry(list_last(list), typeof(*entry), member), \ - tmp = list_entry(list_prev(&entry->member), typeof(*entry), \ - member); \ - !list_end(list, &entry->member); \ - entry = tmp, tmp = list_entry(list_prev(&entry->member), \ - typeof(*entry), member)) - -#endif /* _LIB_LIST_H */ diff --git a/lib/macros.h b/lib/macros.h deleted file mode 100644 index 99837147..00000000 --- a/lib/macros.h +++ /dev/null @@ -1,73 +0,0 @@ -/* - * Copyright (c) 2009, 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * - * Helper macros. - */ - -#ifndef _LIB_MACROS_H -#define _LIB_MACROS_H - -#ifndef __ASSEMBLER__ -#include -#endif /* __ASSEMBLER__ */ - -#define MACRO_BEGIN ({ -#define MACRO_END }) - -#define __QUOTE(x) #x -#define QUOTE(x) __QUOTE(x) - -#ifdef __ASSEMBLER__ -#define DECL_CONST(x, s) x -#else /* __ASSEMBLER__ */ -#define __DECL_CONST(x, s) x##s -#define DECL_CONST(x, s) __DECL_CONST(x, s) -#endif /* __ASSEMBLER__ */ - -#define STRLEN(x) (sizeof(x) - 1) -#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) - -#define MIN(a, b) ((a) < (b) ? (a) : (b)) -#define MAX(a, b) ((a) > (b) ? (a) : (b)) - -#define P2ALIGNED(x, a) (((x) & ((a) - 1)) == 0) -#define ISP2(x) P2ALIGNED(x, x) -#define P2ALIGN(x, a) ((x) & -(a)) -#define P2ROUND(x, a) (-(-(x) & -(a))) -#define P2END(x, a) (-(~(x) & -(a))) - -#define structof(ptr, type, member) \ - ((type *)((char *)ptr - offsetof(type, member))) - -#define alignof(x) __alignof__(x) - -#define likely(expr) __builtin_expect(!!(expr), 1) -#define unlikely(expr) __builtin_expect(!!(expr), 0) - -#define barrier() asm volatile("" : : : "memory") - -#define __noreturn __attribute__((noreturn)) -#define __aligned(x) __attribute__((aligned(x))) -#define __always_inline inline __attribute__((always_inline)) -#define __section(x) __attribute__((section(x))) -#define __packed __attribute__((packed)) -#define __alias(x) __attribute__((alias(x))) - -#define __format_printf(fmt, args) \ - __attribute__((format(printf, fmt, args))) - -#endif /* _LIB_MACROS_H */ diff --git a/lib/rbtree.c b/lib/rbtree.c deleted file mode 100644 index 16718968..00000000 --- a/lib/rbtree.c +++ /dev/null @@ -1,489 +0,0 @@ -/* - * Copyright (c) 2010, 2012 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#include -#include -#include -#include -#include - -/* - * Return the index of a node in the children array of its parent. - * - * The parent parameter must not be null, and must be the parent of the - * given node. - */ -static inline int -rbtree_node_index(const struct rbtree_node *node, - const struct rbtree_node *parent) -{ - assert(parent != NULL); - assert((node == NULL) || (rbtree_node_parent(node) == parent)); - - if (parent->children[RBTREE_LEFT] == node) - return RBTREE_LEFT; - - assert(parent->children[RBTREE_RIGHT] == node); - - return RBTREE_RIGHT; -} - -/* - * Return the color of a node. - */ -static inline int -rbtree_node_color(const struct rbtree_node *node) -{ - return node->parent & RBTREE_COLOR_MASK; -} - -/* - * Return true if the node is red. - */ -static inline int -rbtree_node_is_red(const struct rbtree_node *node) -{ - return rbtree_node_color(node) == RBTREE_COLOR_RED; -} - -/* - * Return true if the node is black. - */ -static inline int -rbtree_node_is_black(const struct rbtree_node *node) -{ - return rbtree_node_color(node) == RBTREE_COLOR_BLACK; -} - -/* - * Set the parent of a node, retaining its current color. - */ -static inline void -rbtree_node_set_parent(struct rbtree_node *node, struct rbtree_node *parent) -{ - assert(rbtree_node_check_alignment(node)); - assert(rbtree_node_check_alignment(parent)); - - node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK); -} - -/* - * Set the color of a node, retaining its current parent. - */ -static inline void -rbtree_node_set_color(struct rbtree_node *node, int color) -{ - assert((color & ~RBTREE_COLOR_MASK) == 0); - node->parent = (node->parent & RBTREE_PARENT_MASK) | color; -} - -/* - * Set the color of a node to red, retaining its current parent. - */ -static inline void -rbtree_node_set_red(struct rbtree_node *node) -{ - rbtree_node_set_color(node, RBTREE_COLOR_RED); -} - -/* - * Set the color of a node to black, retaining its current parent. - */ -static inline void -rbtree_node_set_black(struct rbtree_node *node) -{ - rbtree_node_set_color(node, RBTREE_COLOR_BLACK); -} - -/* - * Return the left-most deepest child node of the given node. - */ -static struct rbtree_node * -rbtree_node_find_deepest(struct rbtree_node *node) -{ - struct rbtree_node *parent; - - assert(node != NULL); - - for (;;) { - parent = node; - node = node->children[RBTREE_LEFT]; - - if (node == NULL) { - node = parent->children[RBTREE_RIGHT]; - - if (node == NULL) - return parent; - } - } -} - -/* - * Perform a tree rotation, rooted at the given node. - * - * The direction parameter defines the rotation direction and is either - * RBTREE_LEFT or RBTREE_RIGHT. - */ -static void -rbtree_rotate(struct rbtree *tree, struct rbtree_node *node, int direction) -{ - struct rbtree_node *parent, *rnode; - int left, right; - - left = direction; - right = 1 - left; - parent = rbtree_node_parent(node); - rnode = node->children[right]; - - node->children[right] = rnode->children[left]; - - if (rnode->children[left] != NULL) - rbtree_node_set_parent(rnode->children[left], node); - - rnode->children[left] = node; - rbtree_node_set_parent(rnode, parent); - - if (unlikely(parent == NULL)) - tree->root = rnode; - else - parent->children[rbtree_node_index(node, parent)] = rnode; - - rbtree_node_set_parent(node, rnode); -} - -void -rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, - int index, struct rbtree_node *node) -{ - struct rbtree_node *grand_parent, *uncle, *tmp; - int left, right; - - assert(rbtree_node_check_alignment(parent)); - assert(rbtree_node_check_alignment(node)); - - node->parent = (unsigned long)parent | RBTREE_COLOR_RED; - node->children[RBTREE_LEFT] = NULL; - node->children[RBTREE_RIGHT] = NULL; - - if (unlikely(parent == NULL)) - tree->root = node; - else - parent->children[index] = node; - - for (;;) { - if (parent == NULL) { - rbtree_node_set_black(node); - break; - } - - if (rbtree_node_is_black(parent)) - break; - - grand_parent = rbtree_node_parent(parent); - assert(grand_parent != NULL); - - left = rbtree_node_index(parent, grand_parent); - right = 1 - left; - - uncle = grand_parent->children[right]; - - /* - * Uncle is red. Flip colors and repeat at grand parent. - */ - if ((uncle != NULL) && rbtree_node_is_red(uncle)) { - rbtree_node_set_black(uncle); - rbtree_node_set_black(parent); - rbtree_node_set_red(grand_parent); - node = grand_parent; - parent = rbtree_node_parent(node); - continue; - } - - /* - * Node is the right child of its parent. Rotate left at parent. - */ - if (parent->children[right] == node) { - rbtree_rotate(tree, parent, left); - tmp = node; - node = parent; - parent = tmp; - } - - /* - * Node is the left child of its parent. Handle colors, rotate right - * at grand parent, and leave. - */ - rbtree_node_set_black(parent); - rbtree_node_set_red(grand_parent); - rbtree_rotate(tree, grand_parent, right); - break; - } - - assert(rbtree_node_is_black(tree->root)); -} - -void -rbtree_remove(struct rbtree *tree, struct rbtree_node *node) -{ - struct rbtree_node *child, *parent, *brother; - int color, left, right; - - if (node->children[RBTREE_LEFT] == NULL) - child = node->children[RBTREE_RIGHT]; - else if (node->children[RBTREE_RIGHT] == NULL) - child = node->children[RBTREE_LEFT]; - else { - struct rbtree_node *successor; - - /* - * Two-children case: replace the node with its successor. - */ - - successor = node->children[RBTREE_RIGHT]; - - while (successor->children[RBTREE_LEFT] != NULL) - successor = successor->children[RBTREE_LEFT]; - - color = rbtree_node_color(successor); - child = successor->children[RBTREE_RIGHT]; - parent = rbtree_node_parent(node); - - if (unlikely(parent == NULL)) - tree->root = successor; - else - parent->children[rbtree_node_index(node, parent)] = successor; - - parent = rbtree_node_parent(successor); - - /* - * Set parent directly to keep the original color. - */ - successor->parent = node->parent; - successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT]; - rbtree_node_set_parent(successor->children[RBTREE_LEFT], successor); - - if (node == parent) - parent = successor; - else { - successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT]; - rbtree_node_set_parent(successor->children[RBTREE_RIGHT], - successor); - parent->children[RBTREE_LEFT] = child; - - if (child != NULL) - rbtree_node_set_parent(child, parent); - } - - goto update_color; - } - - /* - * Node has at most one child. - */ - - color = rbtree_node_color(node); - parent = rbtree_node_parent(node); - - if (child != NULL) - rbtree_node_set_parent(child, parent); - - if (unlikely(parent == NULL)) - tree->root = child; - else - parent->children[rbtree_node_index(node, parent)] = child; - - /* - * The node has been removed, update the colors. The child pointer can - * be null, in which case it is considered a black leaf. - */ -update_color: - if (color == RBTREE_COLOR_RED) - return; - - for (;;) { - if ((child != NULL) && rbtree_node_is_red(child)) { - rbtree_node_set_black(child); - break; - } - - if (parent == NULL) - break; - - left = rbtree_node_index(child, parent); - right = 1 - left; - - brother = parent->children[right]; - - /* - * Brother is red. Recolor and rotate left at parent so that brother - * becomes black. - */ - if (rbtree_node_is_red(brother)) { - rbtree_node_set_black(brother); - rbtree_node_set_red(parent); - rbtree_rotate(tree, parent, left); - brother = parent->children[right]; - } - - /* - * Brother has no red child. Recolor and repeat at parent. - */ - if (((brother->children[RBTREE_LEFT] == NULL) - || rbtree_node_is_black(brother->children[RBTREE_LEFT])) - && ((brother->children[RBTREE_RIGHT] == NULL) - || rbtree_node_is_black(brother->children[RBTREE_RIGHT]))) { - rbtree_node_set_red(brother); - child = parent; - parent = rbtree_node_parent(child); - continue; - } - - /* - * Brother's right child is black. Recolor and rotate right at brother. - */ - if ((brother->children[right] == NULL) - || rbtree_node_is_black(brother->children[right])) { - rbtree_node_set_black(brother->children[left]); - rbtree_node_set_red(brother); - rbtree_rotate(tree, brother, right); - brother = parent->children[right]; - } - - /* - * Brother's left child is black. Exchange parent and brother colors - * (we already know brother is black), set brother's right child black, - * rotate left at parent and leave. - */ - rbtree_node_set_color(brother, rbtree_node_color(parent)); - rbtree_node_set_black(parent); - rbtree_node_set_black(brother->children[right]); - rbtree_rotate(tree, parent, left); - break; - } - - assert((tree->root == NULL) || rbtree_node_is_black(tree->root)); -} - -struct rbtree_node * -rbtree_nearest(struct rbtree_node *parent, int index, int direction) -{ - assert(rbtree_check_index(direction)); - - if (parent == NULL) - return NULL; - - assert(rbtree_check_index(index)); - - if (index != direction) - return parent; - - return rbtree_walk(parent, direction); -} - -struct rbtree_node * -rbtree_firstlast(const struct rbtree *tree, int direction) -{ - struct rbtree_node *prev, *cur; - - assert(rbtree_check_index(direction)); - - prev = NULL; - - for (cur = tree->root; cur != NULL; cur = cur->children[direction]) - prev = cur; - - return prev; -} - -struct rbtree_node * -rbtree_walk(struct rbtree_node *node, int direction) -{ - int left, right; - - assert(rbtree_check_index(direction)); - - left = direction; - right = 1 - left; - - if (node == NULL) - return NULL; - - if (node->children[left] != NULL) { - node = node->children[left]; - - while (node->children[right] != NULL) - node = node->children[right]; - } else { - struct rbtree_node *parent; - int index; - - for (;;) { - parent = rbtree_node_parent(node); - - if (parent == NULL) - return NULL; - - index = rbtree_node_index(node, parent); - node = parent; - - if (index == right) - break; - } - } - - return node; -} - -struct rbtree_node * -rbtree_postwalk_deepest(const struct rbtree *tree) -{ - struct rbtree_node *node; - - node = tree->root; - - if (node == NULL) - return NULL; - - return rbtree_node_find_deepest(node); -} - -struct rbtree_node * -rbtree_postwalk_unlink(struct rbtree_node *node) -{ - struct rbtree_node *parent; - int index; - - if (node == NULL) - return NULL; - - assert(node->children[RBTREE_LEFT] == NULL); - assert(node->children[RBTREE_RIGHT] == NULL); - - parent = rbtree_node_parent(node); - - if (parent == NULL) - return NULL; - - index = rbtree_node_index(node, parent); - parent->children[index] = NULL; - node = parent->children[RBTREE_RIGHT]; - - if (node == NULL) - return parent; - - return rbtree_node_find_deepest(node); -} diff --git a/lib/rbtree.h b/lib/rbtree.h deleted file mode 100644 index e607fcea..00000000 --- a/lib/rbtree.h +++ /dev/null @@ -1,299 +0,0 @@ -/* - * Copyright (c) 2010, 2011, 2012 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * - * Red-black tree. - */ - -#ifndef _LIB_RBTREE_H -#define _LIB_RBTREE_H - -#include -#include -#include - -/* - * Indexes of the left and right nodes in the children array of a node. - */ -#define RBTREE_LEFT 0 -#define RBTREE_RIGHT 1 - -/* - * Red-black node. - */ -struct rbtree_node; - -/* - * Red-black tree. - */ -struct rbtree; - -/* - * Static tree initializer. - */ -#define RBTREE_INITIALIZER { NULL } - -#include "rbtree_i.h" - -/* - * Initialize a tree. - */ -static inline void -rbtree_init(struct rbtree *tree) -{ - tree->root = NULL; -} - -/* - * Initialize a node. - * - * A node is in no tree when its parent points to itself. - */ -static inline void -rbtree_node_init(struct rbtree_node *node) -{ - assert(rbtree_node_check_alignment(node)); - - node->parent = (unsigned long)node | RBTREE_COLOR_RED; - node->children[RBTREE_LEFT] = NULL; - node->children[RBTREE_RIGHT] = NULL; -} - -/* - * Return true if node is in no tree. - */ -static inline int -rbtree_node_unlinked(const struct rbtree_node *node) -{ - return rbtree_node_parent(node) == node; -} - -/* - * Macro that evaluates to the address of the structure containing the - * given node based on the given type and member. - */ -#define rbtree_entry(node, type, member) structof(node, type, member) - -/* - * Return true if tree is empty. - */ -static inline int -rbtree_empty(const struct rbtree *tree) -{ - return tree->root == NULL; -} - -/* - * Look up a node in a tree. - * - * Note that implementing the lookup algorithm as a macro gives two benefits: - * First, it avoids the overhead of a callback function. Next, the type of the - * cmp_fn parameter isn't rigid. The only guarantee offered by this - * implementation is that the key parameter is the first parameter given to - * cmp_fn. This way, users can pass only the value they need for comparison - * instead of e.g. allocating a full structure on the stack. - * - * See rbtree_insert(). - */ -#define rbtree_lookup(tree, key, cmp_fn) \ -MACRO_BEGIN \ - struct rbtree_node *cur; \ - int diff; \ - \ - cur = (tree)->root; \ - \ - while (cur != NULL) { \ - diff = cmp_fn(key, cur); \ - \ - if (diff == 0) \ - break; \ - \ - cur = cur->children[rbtree_d2i(diff)]; \ - } \ - \ - cur; \ -MACRO_END - -/* - * Look up a node or one of its nearest nodes in a tree. - * - * This macro essentially acts as rbtree_lookup() but if no entry matched - * the key, an additional step is performed to obtain the next or previous - * node, depending on the direction (left or right). - * - * The constraints that apply to the key parameter are the same as for - * rbtree_lookup(). - */ -#define rbtree_lookup_nearest(tree, key, cmp_fn, dir) \ -MACRO_BEGIN \ - struct rbtree_node *cur, *prev; \ - int diff, index; \ - \ - prev = NULL; \ - index = -1; \ - cur = (tree)->root; \ - \ - while (cur != NULL) { \ - diff = cmp_fn(key, cur); \ - \ - if (diff == 0) \ - break; \ - \ - prev = cur; \ - index = rbtree_d2i(diff); \ - cur = cur->children[index]; \ - } \ - \ - if (cur == NULL) \ - cur = rbtree_nearest(prev, index, dir); \ - \ - cur; \ -MACRO_END - -/* - * Insert a node in a tree. - * - * This macro performs a standard lookup to obtain the insertion point of - * the given node in the tree (it is assumed that the inserted node never - * compares equal to any other entry in the tree) and links the node. It - * then checks red-black rules violations, and rebalances the tree if - * necessary. - * - * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete - * entries, so it is suggested to use two different comparison inline - * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no - * guarantee about the order of the nodes given to the comparison function. - * - * See rbtree_lookup(). - */ -#define rbtree_insert(tree, node, cmp_fn) \ -MACRO_BEGIN \ - struct rbtree_node *cur, *prev; \ - int diff, index; \ - \ - prev = NULL; \ - index = -1; \ - cur = (tree)->root; \ - \ - while (cur != NULL) { \ - diff = cmp_fn(node, cur); \ - assert(diff != 0); \ - prev = cur; \ - index = rbtree_d2i(diff); \ - cur = cur->children[index]; \ - } \ - \ - rbtree_insert_rebalance(tree, prev, index, node); \ -MACRO_END - -/* - * Look up a node/slot pair in a tree. - * - * This macro essentially acts as rbtree_lookup() but in addition to a node, - * it also returns a slot, which identifies an insertion point in the tree. - * If the returned node is null, the slot can be used by rbtree_insert_slot() - * to insert without the overhead of an additional lookup. The slot is a - * simple unsigned long integer. - * - * The constraints that apply to the key parameter are the same as for - * rbtree_lookup(). - */ -#define rbtree_lookup_slot(tree, key, cmp_fn, slot) \ -MACRO_BEGIN \ - struct rbtree_node *cur, *prev; \ - int diff, index; \ - \ - prev = NULL; \ - index = 0; \ - cur = (tree)->root; \ - \ - while (cur != NULL) { \ - diff = cmp_fn(key, cur); \ - \ - if (diff == 0) \ - break; \ - \ - prev = cur; \ - index = rbtree_d2i(diff); \ - cur = cur->children[index]; \ - } \ - \ - (slot) = rbtree_slot(prev, index); \ - cur; \ -MACRO_END - -/* - * Insert a node at an insertion point in a tree. - * - * This macro essentially acts as rbtree_insert() except that it doesn't - * obtain the insertion point with a standard lookup. The insertion point - * is obtained by calling rbtree_lookup_slot(). In addition, the new node - * must not compare equal to an existing node in the tree (i.e. the slot - * must denote a null node). - */ -#define rbtree_insert_slot(tree, slot, node) \ -MACRO_BEGIN \ - struct rbtree_node *parent; \ - int index; \ - \ - parent = rbtree_slot_parent(slot); \ - index = rbtree_slot_index(slot); \ - rbtree_insert_rebalance(tree, parent, index, node); \ -MACRO_END - -/* - * Remove a node from a tree. - * - * After completion, the node is stale. - */ -void rbtree_remove(struct rbtree *tree, struct rbtree_node *node); - -/* - * Return the first node of a tree. - */ -#define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT) - -/* - * Return the last node of a tree. - */ -#define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT) - -/* - * Return the node previous to the given node. - */ -#define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT) - -/* - * Return the node next to the given node. - */ -#define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT) - -/* - * Forge a loop to process all nodes of a tree, removing them when visited. - * - * This macro can only be used to destroy a tree, so that the resources used - * by the entries can be released by the user. It basically removes all nodes - * without doing any color checking. - * - * After completion, all nodes and the tree root member are stale. - */ -#define rbtree_for_each_remove(tree, node, tmp) \ -for (node = rbtree_postwalk_deepest(tree), \ - tmp = rbtree_postwalk_unlink(node); \ - node != NULL; \ - node = tmp, tmp = rbtree_postwalk_unlink(node)) \ - -#endif /* _LIB_RBTREE_H */ diff --git a/lib/rbtree_i.h b/lib/rbtree_i.h deleted file mode 100644 index 1f85c1a9..00000000 --- a/lib/rbtree_i.h +++ /dev/null @@ -1,187 +0,0 @@ -/* - * Copyright (c) 2010, 2011, 2012 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_RBTREE_I_H -#define _LIB_RBTREE_I_H - -#include -#include -#include - -/* - * Red-black node structure. - * - * To reduce the number of branches and the instruction cache footprint, - * the left and right child pointers are stored in an array, and the symmetry - * of most tree operations is exploited by using left/right variables when - * referring to children. - * - * In addition, this implementation assumes that all nodes are 4-byte aligned, - * so that the least significant bit of the parent member can be used to store - * the color of the node. This is true for all modern 32 and 64 bits - * architectures, as long as the nodes aren't embedded in structures with - * special alignment constraints such as member packing. - */ -struct rbtree_node { - unsigned long parent; - struct rbtree_node *children[2]; -}; - -/* - * Red-black tree structure. - */ -struct rbtree { - struct rbtree_node *root; -}; - -/* - * Masks applied on the parent member of a node to obtain either the - * color or the parent address. - */ -#define RBTREE_COLOR_MASK 0x1UL -#define RBTREE_PARENT_MASK (~0x3UL) - -/* - * Node colors. - */ -#define RBTREE_COLOR_RED 0 -#define RBTREE_COLOR_BLACK 1 - -/* - * Masks applied on slots to obtain either the child index or the parent - * address. - */ -#define RBTREE_SLOT_INDEX_MASK 0x1UL -#define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK) - -/* - * Return true if the given index is a valid child index. - */ -static inline int -rbtree_check_index(int index) -{ - return index == (index & 1); -} - -/* - * Convert the result of a comparison into an index in the children array - * (0 or 1). - * - * This function is mostly used when looking up a node. - */ -static inline int -rbtree_d2i(int diff) -{ - return !(diff <= 0); -} - -/* - * Return true if the given pointer is suitably aligned. - */ -static inline int -rbtree_node_check_alignment(const struct rbtree_node *node) -{ - return ((unsigned long)node & (~RBTREE_PARENT_MASK)) == 0; -} - -/* - * Return the parent of a node. - */ -static inline struct rbtree_node * -rbtree_node_parent(const struct rbtree_node *node) -{ - return (struct rbtree_node *)(node->parent & RBTREE_PARENT_MASK); -} - -/* - * Translate an insertion point into a slot. - */ -static inline unsigned long -rbtree_slot(struct rbtree_node *parent, int index) -{ - assert(rbtree_node_check_alignment(parent)); - assert(rbtree_check_index(index)); - return (unsigned long)parent | index; -} - -/* - * Extract the parent address from a slot. - */ -static inline struct rbtree_node * -rbtree_slot_parent(unsigned long slot) -{ - return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK); -} - -/* - * Extract the index from a slot. - */ -static inline int -rbtree_slot_index(unsigned long slot) -{ - return slot & RBTREE_SLOT_INDEX_MASK; -} - -/* - * Insert a node in a tree, rebalancing it if necessary. - * - * The index parameter is the index in the children array of the parent where - * the new node is to be inserted. It is ignored if the parent is null. - * - * This function is intended to be used by the rbtree_insert() macro only. - */ -void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, - int index, struct rbtree_node *node); - -/* - * Return the previous or next node relative to a location in a tree. - * - * The parent and index parameters define the location, which can be empty. - * The direction parameter is either RBTREE_LEFT (to obtain the previous - * node) or RBTREE_RIGHT (to obtain the next one). - */ -struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index, - int direction); - -/* - * Return the first or last node of a tree. - * - * The direction parameter is either RBTREE_LEFT (to obtain the first node) - * or RBTREE_RIGHT (to obtain the last one). - */ -struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction); - -/* - * Return the node next to, or previous to the given node. - * - * The direction parameter is either RBTREE_LEFT (to obtain the previous node) - * or RBTREE_RIGHT (to obtain the next one). - */ -struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction); - -/* - * Return the left-most deepest node of a tree, which is the starting point of - * the postorder traversal performed by rbtree_for_each_remove(). - */ -struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree); - -/* - * Unlink a node from its tree and return the next (right) node in postorder. - */ -struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node); - -#endif /* _LIB_RBTREE_I_H */ diff --git a/lib/sprintf.c b/lib/sprintf.c deleted file mode 100644 index 7cf1e136..00000000 --- a/lib/sprintf.c +++ /dev/null @@ -1,550 +0,0 @@ -/* - * Copyright (c) 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#include - -#include -#include -#include -#include - -/* - * Formatting flags. - * - * FORMAT_LOWER must be 0x20 as it is OR'd with digits, eg. - * '0': 0x30 | 0x20 => 0x30 ('0') - * 'A': 0x41 | 0x20 => 0x61 ('a') - */ -#define SPRINTF_FORMAT_ALT_FORM 0x01 -#define SPRINTF_FORMAT_ZERO_PAD 0x02 -#define SPRINTF_FORMAT_LEFT_JUSTIFY 0x04 -#define SPRINTF_FORMAT_BLANK 0x08 -#define SPRINTF_FORMAT_SIGN 0x10 -#define SPRINTF_FORMAT_LOWER 0x20 -#define SPRINTF_FORMAT_CONV_SIGNED 0x40 - -enum { - SPRINTF_MODIFIER_NONE, - SPRINTF_MODIFIER_CHAR, - SPRINTF_MODIFIER_SHORT, - SPRINTF_MODIFIER_LONG, - SPRINTF_MODIFIER_LONGLONG, - SPRINTF_MODIFIER_PTR, /* Used only for %p */ - SPRINTF_MODIFIER_SIZE, - SPRINTF_MODIFIER_PTRDIFF -}; - -enum { - SPRINTF_SPECIFIER_INVALID, - SPRINTF_SPECIFIER_INT, - SPRINTF_SPECIFIER_CHAR, - SPRINTF_SPECIFIER_STR, - SPRINTF_SPECIFIER_NRCHARS, - SPRINTF_SPECIFIER_PERCENT -}; - -/* - * Size for the temporary number buffer. The minimum base is 8 so 3 bits - * are consumed per digit. Add one to round up. The conversion algorithm - * doesn't use the null byte. - */ -#define SPRINTF_MAX_NUM_SIZE (((sizeof(uint64_t) * CHAR_BIT) / 3) + 1) - -/* - * Special size for vsnprintf(), used by sprintf()/vsprintf() when the - * buffer size is unknown. - */ -#define SPRINTF_NOLIMIT ((size_t)-1) - -static const char sprintf_digits[] = "0123456789ABCDEF"; - -static inline char * -sprintf_putchar(char *str, char *end, char c) -{ - if (str < end) - *str = c; - - str++; - - return str; -} - -static inline int -sprintf_isdigit(char c) -{ - return (c >= '0') && (c <= '9'); -} - -int -sprintf(char *str, const char *format, ...) -{ - va_list ap; - int length; - - va_start(ap, format); - length = vsprintf(str, format, ap); - va_end(ap); - - return length; -} - -int -vsprintf(char *str, const char *format, va_list ap) -{ - return vsnprintf(str, SPRINTF_NOLIMIT, format, ap); -} - -int -snprintf(char *str, size_t size, const char *format, ...) -{ - va_list ap; - int length; - - va_start(ap, format); - length = vsnprintf(str, size, format, ap); - va_end(ap); - - return length; -} - -int -vsnprintf(char *str, size_t size, const char *format, va_list ap) -{ - unsigned long long n; - int i, len, found, flags, width, precision, modifier, specifier, shift; - unsigned char r, base, mask; - char c, *s, *start, *end, sign, tmp[SPRINTF_MAX_NUM_SIZE]; - - start = str; - - if (size == 0) - end = NULL; - else if (size == SPRINTF_NOLIMIT) - end = (char *)-1; - else - end = start + size - 1; - - while ((c = *format) != '\0') { - if (c != '%') { - str = sprintf_putchar(str, end, c); - format++; - continue; - } - - /* Flags */ - - found = 1; - flags = 0; - - do { - format++; - c = *format; - - switch (c) { - case '#': - flags |= SPRINTF_FORMAT_ALT_FORM; - break; - case '0': - flags |= SPRINTF_FORMAT_ZERO_PAD; - break; - case '-': - flags |= SPRINTF_FORMAT_LEFT_JUSTIFY; - break; - case ' ': - flags |= SPRINTF_FORMAT_BLANK; - break; - case '+': - flags |= SPRINTF_FORMAT_SIGN; - break; - default: - found = 0; - break; - } - } while (found); - - /* Width */ - - if (sprintf_isdigit(c)) { - width = 0; - - while (sprintf_isdigit(c)) { - width = width * 10 + (c - '0'); - format++; - c = *format; - } - } else if (c == '*') { - width = va_arg(ap, int); - - if (width < 0) { - flags |= SPRINTF_FORMAT_LEFT_JUSTIFY; - width = -width; - } - - format++; - c = *format; - } else { - width = 0; - } - - /* Precision */ - - if (c == '.') { - format++; - c = *format; - - if (sprintf_isdigit(c)) { - precision = 0; - - while (sprintf_isdigit(c)) { - precision = precision * 10 + (c - '0'); - format++; - c = *format; - } - } else if (c == '*') { - precision = va_arg(ap, int); - - if (precision < 0) - precision = 0; - - format++; - c = *format; - } else { - precision = 0; - } - } else { - /* precision is >= 0 only if explicit */ - precision = -1; - } - - /* Length modifier */ - - switch (c) { - case 'h': - case 'l': - format++; - - if (c == *format) { - modifier = (c == 'h') - ? SPRINTF_MODIFIER_CHAR - : SPRINTF_MODIFIER_LONGLONG; - goto skip_modifier; - } else { - modifier = (c == 'h') - ? SPRINTF_MODIFIER_SHORT - : SPRINTF_MODIFIER_LONG; - c = *format; - } - - break; - case 'z': - modifier = SPRINTF_MODIFIER_SIZE; - goto skip_modifier; - case 't': - modifier = SPRINTF_MODIFIER_PTRDIFF; -skip_modifier: - format++; - c = *format; - break; - default: - modifier = SPRINTF_MODIFIER_NONE; - break; - } - - /* Specifier */ - - switch (c) { - case 'd': - case 'i': - flags |= SPRINTF_FORMAT_CONV_SIGNED; - case 'u': - base = 10; - goto integer; - case 'o': - base = 8; - goto integer; - case 'p': - flags |= SPRINTF_FORMAT_ALT_FORM; - modifier = SPRINTF_MODIFIER_PTR; - case 'x': - flags |= SPRINTF_FORMAT_LOWER; - case 'X': - base = 16; -integer: - specifier = SPRINTF_SPECIFIER_INT; - break; - case 'c': - specifier = SPRINTF_SPECIFIER_CHAR; - break; - case 's': - specifier = SPRINTF_SPECIFIER_STR; - break; - case 'n': - specifier = SPRINTF_SPECIFIER_NRCHARS; - break; - case '%': - specifier = SPRINTF_SPECIFIER_PERCENT; - break; - default: - specifier = SPRINTF_SPECIFIER_INVALID; - break; - } - - /* Output */ - - switch (specifier) { - case SPRINTF_SPECIFIER_INT: - switch (modifier) { - case SPRINTF_MODIFIER_CHAR: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = (signed char)va_arg(ap, int); - else - n = (unsigned char)va_arg(ap, int); - break; - case SPRINTF_MODIFIER_SHORT: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = (short)va_arg(ap, int); - else - n = (unsigned short)va_arg(ap, int); - break; - case SPRINTF_MODIFIER_LONG: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = va_arg(ap, long); - else - n = va_arg(ap, unsigned long); - break; - case SPRINTF_MODIFIER_LONGLONG: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = va_arg(ap, long long); - else - n = va_arg(ap, unsigned long long); - break; - case SPRINTF_MODIFIER_PTR: - n = (unsigned long)va_arg(ap, void *); - break; - case SPRINTF_MODIFIER_SIZE: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = va_arg(ap, ssize_t); - else - n = va_arg(ap, size_t); - break; - case SPRINTF_MODIFIER_PTRDIFF: - n = va_arg(ap, ptrdiff_t); - break; - default: - if (flags & SPRINTF_FORMAT_CONV_SIGNED) - n = va_arg(ap, int); - else - n = va_arg(ap, unsigned int); - break; - } - - if ((flags & SPRINTF_FORMAT_LEFT_JUSTIFY) || (precision >= 0)) - flags &= ~SPRINTF_FORMAT_ZERO_PAD; - - sign = 0; - - if (flags & SPRINTF_FORMAT_ALT_FORM) { - /* '0' for octal */ - width--; - - /* '0x' or '0X' for hexadecimal */ - if (base == 16) - width--; - } else if (flags & SPRINTF_FORMAT_CONV_SIGNED) { - if ((long long)n < 0) { - sign = '-'; - width--; - n = -(long long)n; - } else if (flags & SPRINTF_FORMAT_SIGN) { - /* SPRINTF_FORMAT_SIGN must precede SPRINTF_FORMAT_BLANK. */ - sign = '+'; - width--; - } else if (flags & SPRINTF_FORMAT_BLANK) { - sign = ' '; - width--; - } - } - - /* Conversion, in reverse order */ - - i = 0; - - if (n == 0) { - if (precision != 0) - tmp[i++] = '0'; - } else if (base == 10) { - /* - * Try to avoid 64 bits operations if the processor doesn't - * support them. Note that even when using modulus and - * division operators close to each other, the compiler will - * forge two calls to __udivdi3() and __umoddi3() instead of - * one to __udivmoddi3(), whereas processor instructions are - * generally correctly used once, giving both the remainder - * and the quotient, through plain or reciprocal division. - */ -#ifndef __LP64__ - if (modifier == SPRINTF_MODIFIER_LONGLONG) { -#endif /* __LP64__ */ - do { - r = n % 10; - n /= 10; - tmp[i++] = sprintf_digits[r]; - } while (n != 0); -#ifndef __LP64__ - } else { - unsigned long m; - - m = (unsigned long)n; - - do { - r = m % 10; - m /= 10; - tmp[i++] = sprintf_digits[r]; - } while (m != 0); - } -#endif /* __LP64__ */ - } else { - mask = base - 1; - shift = (base == 8) ? 3 : 4; - - do { - r = (unsigned char)n & mask; - n >>= shift; - tmp[i++] = sprintf_digits[r] - | (flags & SPRINTF_FORMAT_LOWER); - } while (n != 0); - } - - if (i > precision) - precision = i; - - width -= precision; - - if (!(flags & (SPRINTF_FORMAT_LEFT_JUSTIFY - | SPRINTF_FORMAT_ZERO_PAD))) - while (width-- > 0) - str = sprintf_putchar(str, end, ' '); - - if (flags & SPRINTF_FORMAT_ALT_FORM) { - str = sprintf_putchar(str, end, '0'); - - if (base == 16) - str = sprintf_putchar(str, end, - 'X' | (flags & SPRINTF_FORMAT_LOWER)); - } else if (sign) { - str = sprintf_putchar(str, end, sign); - } - - if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) { - c = (flags & SPRINTF_FORMAT_ZERO_PAD) ? '0' : ' '; - - while (width-- > 0) - str = sprintf_putchar(str, end, c); - } - - while (i < precision--) - str = sprintf_putchar(str, end, '0'); - - while (i-- > 0) - str = sprintf_putchar(str, end, tmp[i]); - - while (width-- > 0) - str = sprintf_putchar(str, end, ' '); - - break; - case SPRINTF_SPECIFIER_CHAR: - c = (unsigned char)va_arg(ap, int); - - if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) - while (--width > 0) - str = sprintf_putchar(str, end, ' '); - - str = sprintf_putchar(str, end, c); - - while (--width > 0) - str = sprintf_putchar(str, end, ' '); - - break; - case SPRINTF_SPECIFIER_STR: - s = va_arg(ap, char *); - - if (s == NULL) - s = "(null)"; - - len = 0; - - for (len = 0; s[len] != '\0'; len++) - if (len == precision) - break; - - if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) - while (len < width--) - str = sprintf_putchar(str, end, ' '); - - for (i = 0; i < len; i++) { - str = sprintf_putchar(str, end, *s); - s++; - } - - while (len < width--) - str = sprintf_putchar(str, end, ' '); - - break; - case SPRINTF_SPECIFIER_NRCHARS: - if (modifier == SPRINTF_MODIFIER_CHAR) { - signed char *ptr = va_arg(ap, signed char *); - *ptr = str - start; - } else if (modifier == SPRINTF_MODIFIER_SHORT) { - short *ptr = va_arg(ap, short *); - *ptr = str - start; - } else if (modifier == SPRINTF_MODIFIER_LONG) { - long *ptr = va_arg(ap, long *); - *ptr = str - start; - } else if (modifier == SPRINTF_MODIFIER_LONGLONG) { - long long *ptr = va_arg(ap, long long *); - *ptr = str - start; - } else if (modifier == SPRINTF_MODIFIER_SIZE) { - ssize_t *ptr = va_arg(ap, ssize_t *); - *ptr = str - start; - } else if (modifier == SPRINTF_MODIFIER_PTRDIFF) { - ptrdiff_t *ptr = va_arg(ap, ptrdiff_t *); - *ptr = str - start; - } else { - int *ptr = va_arg(ap, int *); - *ptr = str - start; - } - - break; - case SPRINTF_SPECIFIER_PERCENT: - case SPRINTF_SPECIFIER_INVALID: - str = sprintf_putchar(str, end, '%'); - break; - default: - break; - } - - if (specifier != SPRINTF_SPECIFIER_INVALID) - format++; - } - - if (str < end) - *str = '\0'; - else if (end != NULL) - *end = '\0'; - - return str - start; -} diff --git a/lib/sprintf.h b/lib/sprintf.h deleted file mode 100644 index af9e841b..00000000 --- a/lib/sprintf.h +++ /dev/null @@ -1,43 +0,0 @@ -/* - * Copyright (c) 2010 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * - * Formatted string functions. - * - * The functions provided by this module implement a subset of the C99 - * sprintf() like functions, mostly centered around character, string, and - * integer conversions. - * - * The supported specifiers are: d i o u x X c s p n % - * The supported length modifiers are: hh h l ll z t - */ - -#ifndef _LIB_SPRINTF_H -#define _LIB_SPRINTF_H - -#include - -#include - -int sprintf(char *str, const char *format, ...) __format_printf(2, 3); -int vsprintf(char *str, const char *format, va_list ap) __format_printf(2, 0); - -int snprintf(char *str, size_t size, const char *format, ...) - __format_printf(3, 4); -int vsnprintf(char *str, size_t size, const char *format, va_list ap) - __format_printf(3, 0); - -#endif /* _LIB_SPRINTF_H */ diff --git a/lib/stddef.h b/lib/stddef.h deleted file mode 100644 index 2cbb7a9e..00000000 --- a/lib/stddef.h +++ /dev/null @@ -1,35 +0,0 @@ -/* - * Copyright (c) 2010, 2011 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_STDDEF_H -#define _LIB_STDDEF_H - -#define NULL ((void *)0) - -#define offsetof(type, member) __builtin_offsetof(type, member) - -#ifdef __LP64__ -typedef unsigned long size_t; -typedef long ssize_t; -typedef long ptrdiff_t; -#else /* __LP64__ */ -typedef unsigned int size_t; -typedef int ssize_t; -typedef int ptrdiff_t; -#endif /* __LP64__ */ - -#endif /* _LIB_STDDEF_H */ diff --git a/lib/stdint.h b/lib/stdint.h deleted file mode 100644 index 17cb9a2b..00000000 --- a/lib/stdint.h +++ /dev/null @@ -1,30 +0,0 @@ -/* - * Copyright (c) 2010, 2011 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_STDINT_H -#define _LIB_STDINT_H - -typedef signed char int8_t; -typedef unsigned char uint8_t; -typedef signed short int16_t; -typedef unsigned short uint16_t; -typedef signed int int32_t; -typedef unsigned int uint32_t; -typedef signed long long int64_t; -typedef unsigned long long uint64_t; - -#endif /* _LIB_STDINT_H */ diff --git a/lib/string.c b/lib/string.c deleted file mode 100644 index f0ed626c..00000000 --- a/lib/string.c +++ /dev/null @@ -1,138 +0,0 @@ -/* - * Copyright (c) 2012 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * - * Trivial, portable implementations. - */ - -#include -#include - -void * -memcpy(void *dest, const void *src, size_t n) -{ - const char *src_ptr; - char *dest_ptr; - size_t i; - - dest_ptr = dest; - src_ptr = src; - - for (i = 0; i < n; i++) - *dest_ptr++ = *src_ptr++; - - return dest; -} - -void * -memmove(void *dest, const void *src, size_t n) -{ - const char *src_ptr; - char *dest_ptr; - size_t i; - - if (src == dest) - return dest; - else if (src < dest) { - dest_ptr = (char *)dest + n - 1; - src_ptr = (const char *)src + n - 1; - - for (i = 0; i < n; i++) - *dest_ptr-- = *src_ptr--; - } else if (src > dest) { - dest_ptr = dest; - src_ptr = src; - - for (i = 0; i < n; i++) - *dest_ptr++ = *src_ptr++; - } - - return dest; -} - -void * -memset(void *s, int c, size_t n) -{ - char *buffer; - size_t i; - - buffer = s; - - for (i = 0; i < n; i++) - buffer[i] = c; - - return s; -} - -int -memcmp(const void *s1, const void *s2, size_t n) -{ - const char *a1, *a2; - size_t i; - - a1 = s1; - a2 = s2; - - for (i = 0; i < n; i++) - if (a1[i] != a2[i]) - return a2[i] - a1[i]; - - return 0; -} - -size_t -strlen(const char *s) -{ - size_t i; - - i = 0; - - while (*s++ != '\0') - i++; - - return i; -} - -char * -strcpy(char *dest, const char *src) -{ - char *tmp; - - tmp = dest; - - while ((*dest = *src) != '\0') { - dest++; - src++; - } - - return tmp; -} - -int -strcmp(const char *s1, const char *s2) -{ - char c1, c2; - - while ((c1 = *s1) == (c2 = *s2)) { - if (c1 == '\0') - return 0; - - s1++; - s2++; - } - - return (c1 < c2) ? -1 : 1; -} diff --git a/lib/string.h b/lib/string.h deleted file mode 100644 index 936892bd..00000000 --- a/lib/string.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * Copyright (c) 2012 Richard Braun. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef _LIB_STRING_H -#define _LIB_STRING_H - -#include - -void * memcpy(void *dest, const void *src, size_t n); -void * memmove(void *dest, const void *src, size_t n); -void * memset(void *s, int c, size_t n); -int memcmp(const void *s1, const void *s2, size_t n); -size_t strlen(const char *s); -char * strcpy(char *dest, const char *src); -int strcmp(const char *s1, const char *s2); - -#endif /* _LIB_STRING_H */ diff --git a/vm/vm_kmem.c b/vm/vm_kmem.c index 72d02899..a90fb058 100644 --- a/vm/vm_kmem.c +++ b/vm/vm_kmem.c @@ -15,12 +15,12 @@ * along with this program. If not, see . */ +#include #include #include #include +#include #include -#include -#include #include #include #include diff --git a/vm/vm_map.c b/vm/vm_map.c index 6eecab73..8343472f 100644 --- a/vm/vm_map.c +++ b/vm/vm_map.c @@ -19,18 +19,18 @@ * needed for kernel allocation. */ +#include #include #include #include +#include +#include #include #include #include -#include -#include -#include -#include -#include -#include +#include +#include +#include #include #include #include diff --git a/vm/vm_map.h b/vm/vm_map.h index 7231b6a3..9759ff4b 100644 --- a/vm/vm_map.h +++ b/vm/vm_map.h @@ -21,9 +21,9 @@ #ifndef _VM_VM_MAP_H #define _VM_VM_MAP_H -#include -#include -#include +#include +#include +#include #include /* diff --git a/vm/vm_page.h b/vm/vm_page.h index e499dc52..e5ad8fc5 100644 --- a/vm/vm_page.h +++ b/vm/vm_page.h @@ -18,8 +18,8 @@ #ifndef _VM_VM_PAGE_H #define _VM_VM_PAGE_H -#include -#include +#include +#include #include #include diff --git a/vm/vm_phys.c b/vm/vm_phys.c index 81e655bf..9fcc7cc9 100644 --- a/vm/vm_phys.c +++ b/vm/vm_phys.c @@ -29,17 +29,17 @@ * The symmetric case is handled likewise. */ +#include #include +#include +#include #include #include #include +#include +#include +#include #include -#include -#include -#include -#include -#include -#include #include #include #include -- cgit v1.2.3