WebSVN – HelenOS-historic – Path Comparison – / – /kernel/ Rev 787 and /kernel/ Rev 788

Ignore whitespace Rev 787 → Rev 788

 /kernel/trunk/genarch/src/mm/asid.c
 ,7 → 53,7
 #include <arch/mm/asid.h>
 #include <synch/spinlock.h>
 #include <arch.h>
-#include <list.h>
+#include <adt/list.h>
 #include <debug.h>
 /**

 /kernel/trunk/genarch/src/mm/asid_fifo.c
 ,7 → 30,7
 #include <arch/mm/asid.h>
 #include <mm/asid.h>
 #include <typedefs.h>
-#include <fifo.h>
+#include <adt/fifo.h>
 /**
  * FIFO queue containing unassigned ASIDs.

/kernel/trunk/generic/include/fifo.h
File deleted

/kernel/trunk/generic/include/list.h
File deleted

 /kernel/trunk/generic/include/time/timeout.h
 ,7 → 32,7
 #include <arch/types.h>
 #include <typedefs.h>
 #include <synch/spinlock.h>
-#include <list.h>
+#include <adt/list.h>
 #define us2ticks(us)    ((__u64)(((__u32) (us)/(1000000/HZ))))

 /kernel/trunk/generic/include/proc/scheduler.h
 ,7 → 33,7
 #include <time/clock.h>     /* HZ */
 #include <typedefs.h>
 #include <arch/atomic.h>
-#include <list.h>
+#include <adt/list.h>
 #define RQ_COUNT        16
 #define NEEDS_RELINK_MAX    (HZ)

 /kernel/trunk/generic/include/proc/task.h
 ,7 → 31,7
 #include <typedefs.h>
 #include <synch/spinlock.h>
-#include <list.h>
+#include <adt/list.h>
 /** Task structure. */
 struct task {

 /kernel/trunk/generic/include/proc/thread.h
 ,7 → 38,7
 #include <time/timeout.h>
 #include <synch/rwlock.h>
 #include <config.h>
-#include <list.h>
+#include <adt/list.h>
 #define THREAD_STACK_SIZE   STACK_SIZE

 /kernel/trunk/generic/include/cpu.h
 ,7 → 37,7
 #include <typedefs.h>
 #include <arch/context.h>
 #include <config.h>
-#include <list.h>
+#include <adt/list.h>
 #define CPU_STACK_SIZE  STACK_SIZE

 /kernel/trunk/generic/include/synch/waitq.h
 ,7 → 33,7
 #include <typedefs.h>
 #include <synch/spinlock.h>
 #include <synch/synch.h>
-#include <list.h>
+#include <adt/list.h>
 #define WAKEUP_FIRST    0
 #define WAKEUP_ALL  1

 /kernel/trunk/generic/include/console/kconsole.h
 ,7 → 30,7
 #define __KCONSOLE_H__
 #include <typedefs.h>
-#include <list.h>
+#include <adt/list.h>
 #include <synch/spinlock.h>
 #define MAX_CMDLINE     256

 /kernel/trunk/generic/include/adt/list.h
 ,0 → 1,177
+/*
+ * Copyright (C) 2001-2004 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#ifndef __LIST_H__
+#define __LIST_H__
+#include <arch/types.h>
+#include <typedefs.h>
+/** Doubly linked list head and link type. */
+struct link {
+    link_t *prev;   /**< Pointer to the previous item in the list. */
+    link_t *next;   /**< Pointer to the next item in the list. */
+};
+/** Declare and initialize statically allocated list.
+ *
+ * @param name Name of the new statically allocated list.
+ */
+#define LIST_INITIALIZE(name)       link_t name = { .prev = &name, .next = &name }
+/** Initialize doubly-linked circular list link
+ *
+ * Initialize doubly-linked list link.
+ *
+ * @param link Pointer to link_t structure to be initialized.
+ */
+static inline void link_initialize(link_t *link)
+{
+    link->prev = NULL;
+    link->next = NULL;
+}
+/** Initialize doubly-linked circular list
+ *
+ * Initialize doubly-linked circular list.
+ *
+ * @param head Pointer to link_t structure representing head of the list.
+ */
+static inline void list_initialize(link_t *head)
+{
+    head->prev = head;
+    head->next = head;
+}
+/** Add item to the beginning of doubly-linked circular list
+ *
+ * Add item to the beginning of doubly-linked circular list.
+ *
+ * @param link Pointer to link_t structure to be added.
+ * @param head Pointer to link_t structure representing head of the list.
+ */
+static inline void list_prepend(link_t *link, link_t *head)
+{
+    link->next = head->next;
+    link->prev = head;
+    head->next->prev = link;
+    head->next = link;
+}
+/** Add item to the end of doubly-linked circular list
+ *
+ * Add item to the end of doubly-linked circular list.
+ *
+ * @param link Pointer to link_t structure to be added.
+ * @param head Pointer to link_t structure representing head of the list.
+ */
+static inline void list_append(link_t *link, link_t *head)
+{
+    link->prev = head->prev;
+    link->next = head;
+    head->prev->next = link;
+    head->prev = link;
+}
+/** Remove item from doubly-linked circular list
+ *
+ * Remove item from doubly-linked circular list.
+ *
+ * @param link Pointer to link_t structure to be removed from the list it is contained in.
+ */
+static inline void list_remove(link_t *link)
+{
+    link->next->prev = link->prev;
+    link->prev->next = link->next;
+    link_initialize(link);
+}
+/** Query emptiness of doubly-linked circular list
+ *
+ * Query emptiness of doubly-linked circular list.
+ *
+ * @param head Pointer to link_t structure representing head of the list.
+ */
+static inline bool list_empty(link_t *head)
+{
+    return head->next == head ? true : false;
+}
+/** Split or concatenate headless doubly-linked circular list
+ *
+ * Split or concatenate headless doubly-linked circular list.
+ *
+ * Note that the algorithm works both directions:
+ * concatenates splitted lists and splits concatenated lists.
+ *
+ * @param part1 Pointer to link_t structure leading the first (half of the headless) list.
+ * @param part2 Pointer to link_t structure leading the second (half of the headless) list.
+ */
+static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
+{
+    link_t *hlp;
+    part1->prev->next = part2;
+    part2->prev->next = part1;
+    hlp = part1->prev;
+    part1->prev = part2->prev;
+    part2->prev = hlp;
+}
+/** Split headless doubly-linked circular list
+ *
+ * Split headless doubly-linked circular list.
+ *
+ * @param part1 Pointer to link_t structure leading the first half of the headless list.
+ * @param part2 Pointer to link_t structure leading the second half of the headless list.
+ */
+static inline void headless_list_split(link_t *part1, link_t *part2)
+{
+    headless_list_split_or_concat(part1, part2);
+}
+/** Concatenate two headless doubly-linked circular lists
+ *
+ * Concatenate two headless doubly-linked circular lists.
+ *
+ * @param part1 Pointer to link_t structure leading the first headless list.
+ * @param part2 Pointer to link_t structure leading the second headless list.
+ */
+static inline void headless_list_concat(link_t *part1, link_t *part2)
+{
+    headless_list_split_or_concat(part1, part2);
+}
+#define list_get_instance(link,type,member) (type *)(((__u8*)(link))-((__u8*)&(((type *)NULL)->member)))
+extern bool list_member(const link_t *link, const link_t *head);
+extern void list_concat(link_t *head1, link_t *head2);
+#endif

 /kernel/trunk/generic/include/adt/fifo.h
 ,0 → 1,80
+/*
+ * Copyright (C) 2006 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+/*
+ * This implementation of FIFO stores values in a statically
+ * allocated array created on each FIFO's initialization.
+ * As such, these FIFOs have upper bound on number of values
+ * they can store. Push and pop operations are done via accessing
+ * the array through head and tail indices. Because of better
+ * operation ordering in fifo_pop(), the access policy for these
+ * two indices is to 'increment (mod size of FIFO) and use'.
+ */
+#ifndef __FIFO_H__
+#define __FIFO_H__
+#include <typedefs.h>
+/** Create and initialize FIFO.
+ *
+ * @param name Name of FIFO.
+ * @param t Type of values stored in FIFO.
+ * @param itms Number of items that can be stored in FIFO.
+ */
+#define FIFO_INITIALIZE(name, t, itms)          \
+    struct {                    \
+        t fifo[(itms)];             \
+        count_t items;              \
+        index_t head;               \
+        index_t tail;               \
+    } name = {                  \
+        .items = (itms),            \
+        .head = 0,              \
+        .tail = 0               \
+    }
+/** Pop value from head of FIFO.
+ *
+ * @param name FIFO name.
+ *
+ * @return Leading value in FIFO.
+ */
+#define fifo_pop(name) \
+    name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
+/** Push value to tail of FIFO.
+ *
+ * @param name FIFO name.
+ * @param value Value to be appended to FIFO.
+ *
+ */
+#define fifo_push(name, value) \
+    name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
+#endif

 /kernel/trunk/generic/include/mm/frame.h
 ,7 → 32,7
 #include <arch/types.h>
 #include <typedefs.h>
-#include <list.h>
+#include <adt/list.h>
 #include <synch/spinlock.h>
 #include <mm/buddy.h>
 #include <mm/slab.h>

 /kernel/trunk/generic/include/mm/slab.h
 ,7 → 29,7
 #ifndef __SLAB_H__
 #define __SLAB_H__
-#include <list.h>
+#include <adt/list.h>
 #include <synch/spinlock.h>
 #include <arch/atomic.h>

 /kernel/trunk/generic/include/mm/as.h
 ,7 → 35,7
 #include <arch/types.h>
 #include <typedefs.h>
 #include <synch/spinlock.h>
-#include <list.h>
+#include <adt/list.h>
 #define KERNEL_ADDRESS_SPACE_START  KERNEL_ADDRESS_SPACE_START_ARCH
 #define KERNEL_ADDRESS_SPACE_END    KERNEL_ADDRESS_SPACE_END_ARCH

 /kernel/trunk/generic/src/console/cmd.c
 ,7 → 39,7
 #include <panic.h>
 #include <typedefs.h>
 #include <arch/types.h>
-#include <list.h>
+#include <adt/list.h>
 #include <arch.h>
 #include <func.h>
 #include <macros.h>

 /kernel/trunk/generic/src/console/kconsole.c
 ,7 → 34,7
 #include <panic.h>
 #include <typedefs.h>
 #include <arch/types.h>
-#include <list.h>
+#include <adt/list.h>
 #include <arch.h>
 #include <macros.h>
 #include <debug.h>

 /kernel/trunk/generic/src/proc/scheduler.c
 ,7 → 41,7
 #include <context.h>
 #include <func.h>
 #include <arch.h>
-#include <list.h>
+#include <adt/list.h>
 #include <panic.h>
 #include <typedefs.h>
 #include <cpu.h>

 /kernel/trunk/generic/src/proc/task.c
 ,7 → 34,7
 #include <synch/spinlock.h>
 #include <arch.h>
 #include <panic.h>
-#include <list.h>
+#include <adt/list.h>
 SPINLOCK_INITIALIZE(tasks_lock);
 LIST_INITIALIZE(tasks_head);

 /kernel/trunk/generic/src/proc/thread.c
 ,10 → 41,10
 #include <cpu.h>
 #include <func.h>
 #include <context.h>
-#include <list.h>
+#include <adt/list.h>
 #include <typedefs.h>
 #include <time/clock.h>
-#include <list.h>
+#include <adt/list.h>
 #include <config.h>
 #include <arch/interrupt.h>
 #include <smp/ipi.h>

 /kernel/trunk/generic/src/synch/rwlock.c
 ,7 → 56,7
 #include <synch/mutex.h>
 #include <synch/waitq.h>
 #include <synch/synch.h>
-#include <list.h>
+#include <adt/list.h>
 #include <typedefs.h>
 #include <arch/asm.h>
 #include <arch.h>

 /kernel/trunk/generic/src/synch/waitq.c
 ,7 → 37,7
 #include <time/timeout.h>
 #include <arch.h>
 #include <context.h>
-#include <list.h>
+#include <adt/list.h>
 /** Initialize wait queue
  *

/kernel/trunk/generic/src/lib/list.c
File deleted

 /kernel/trunk/generic/src/cpu/cpu.c
 ,7 → 37,7
 #include <panic.h>
 #include <typedefs.h>
 #include <memstr.h>
-#include <list.h>
+#include <adt/list.h>
 #include <print.h>
 cpu_t *cpus;

 /kernel/trunk/generic/src/adt/list.c
 ,0 → 1,80
+/*
+ * Copyright (C) 2004 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include <adt/list.h>
+/** Check for membership
+ *
+ * Check whether link is contained in the list head.
+ * The membership is defined as pointer equivalence.
+ *
+ * @param link Item to look for.
+ * @param head List to look in.
+ *
+ * @return true if link is contained in head, false otherwise.
+ *
+ */
+bool list_member(const link_t *link, const link_t *head)
+{
+    bool found = false;
+    link_t *hlp = head->next;
+    while (hlp != head) {
+        if (hlp == link) {
+            found = true;
+            break;
+        }
+        hlp = hlp->next;
+    }
+    return found;
+}
+/** Concatenate two lists
+ *
+ * Concatenate lists head1 and head2, producing a single
+ * list head1 containing items from both (in head1, head2
+ * order) and empty list head2.
+ *
+ * @param head1 First list and concatenated output
+ * @param head2 Second list and empty output.
+ *
+ */
+void list_concat(link_t *head1, link_t *head2)
+{
+    if (list_empty(head2))
+        return;
+    head2->next->prev = head1->prev;
+    head2->prev->next = head1;
+    head1->prev->next = head2->next;
+    head1->prev = head2->prev;
+    list_initialize(head2);
+}

 /kernel/trunk/generic/src/mm/slab.c
 ,7 → 93,7
 #include <synch/spinlock.h>
 #include <mm/slab.h>
-#include <list.h>
+#include <adt/list.h>
 #include <memstr.h>
 #include <align.h>
 #include <mm/heap.h>

 /kernel/trunk/generic/src/mm/as.c
 ,7 → 46,7
 #include <typedefs.h>
 #include <synch/spinlock.h>
 #include <config.h>
-#include <list.h>
+#include <adt/list.h>
 #include <panic.h>
 #include <arch/asm.h>
 #include <debug.h>

 /kernel/trunk/generic/src/mm/buddy.c
 ,7 → 31,7
 #include <mm/heap.h>
 #include <arch/types.h>
 #include <typedefs.h>
-#include <list.h>
+#include <adt/list.h>
 #include <debug.h>
 #include <print.h>

 /kernel/trunk/generic/src/mm/frame.c
 ,7 → 34,7
 #include <mm/as.h>
 #include <panic.h>
 #include <debug.h>
-#include <list.h>
+#include <adt/list.h>
 #include <synch/spinlock.h>
 #include <arch/asm.h>
 #include <arch.h>

 /kernel/trunk/generic/src/time/clock.c
 ,7 → 37,7
 #include <cpu.h>
 #include <print.h>
 #include <arch.h>
-#include <list.h>
+#include <adt/list.h>
 #include <arch/atomic.h>
 #include <proc/thread.h>

/kernel/trunk/Makefile
94,6 → 94,7
#

GENERIC_SOURCES = \
generic/src/adt/list.c \
generic/src/console/chardev.c \
generic/src/console/console.c \
generic/src/console/kconsole.c \
117,7 → 118,6
generic/src/mm/as.c \
generic/src/mm/slab.c \
generic/src/lib/func.c \
generic/src/lib/list.c \
generic/src/lib/memstr.c \
generic/src/lib/sort.c \
generic/src/debug/print.c \

Subversion Repositories HelenOS-historic

Compare Revisions

Ignore whitespace Rev 787 → Rev 788