LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Kentaro Takeda <takedakn@nttdata.co.jp>
To: Stephen Smalley <sds@tycho.nsa.gov>,
	James Morris <jmorris@namei.org>,
	Chris Wright <chrisw@sous-sol.org>
Cc: "Serge E. Hallyn" <serue@us.ibm.com>,
	linux-security-module@vger.kernel.org,
	linux-kernel@vger.kernel.org,
	Toshiharu Harada <haradats@nttdata.co.jp>,
	Andrew Morton <akpm@linux-foundation.org>,
	Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Subject: [TOMOYO #11 (linux-next) 03/11] Singly linked list implementation.
Date: Mon, 20 Oct 2008 16:34:26 +0900	[thread overview]
Message-ID: <20081020073648.682014372@nttdata.co.jp> (raw)
In-Reply-To: <20081020073423.024299308@nttdata.co.jp>

Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 include/linux/list1.h |   81 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

--- /dev/null
+++ linux-next/include/linux/list1.h
@@ -0,0 +1,81 @@
+#ifndef _LINUX_LIST1_H
+#define _LINUX_LIST1_H
+
+#include <linux/list.h>
+#include <linux/rcupdate.h>
+
+/*
+ * Singly linked list implementation.
+ *
+ * This list supports only two operations.
+ * (1) Append an entry to the tail of the list.
+ * (2) Read all entries starting from the head of the list.
+ *
+ * This list is designed for holding "write once, read many" entries.
+ * This list requires no locks for read operation.
+ * This list doesn't support "remove an entry from the list" operation.
+ */
+
+/* To reduce memory usage, this list doesn't use "->prev" pointer. */
+struct list1_head {
+	struct list1_head *next;
+};
+
+#define LIST1_HEAD_INIT(name) { &(name) }
+#define LIST1_HEAD(name) struct list1_head name = LIST1_HEAD_INIT(name)
+
+static inline void INIT_LIST1_HEAD(struct list1_head *list)
+{
+	list->next = list;
+}
+
+/* Reuse list_entry because it doesn't use "->prev" pointer. */
+#define list1_entry list_entry
+
+/* Reuse list_for_each_rcu because it doesn't use "->prev" pointer. */
+#define list1_for_each list_for_each_rcu
+/* Reuse list_for_each_entry_rcu because it doesn't use "->prev" pointer. */
+#define list1_for_each_entry list_for_each_entry_rcu
+
+/**
+ * list1_for_each_cookie - iterate over a list with cookie.
+ * @pos:        the &struct list1_head to use as a loop cursor.
+ * @cookie:     the &struct list1_head to use as a cookie.
+ * @head:       the head for your list.
+ *
+ * Same with list_for_each_rcu() except that this primitive uses @cookie
+ * so that we can continue iteration.
+ * @cookie must be NULL when iteration starts, and @cookie will become
+ * NULL when iteration finishes.
+ *
+ * Since list elements are never removed, we don't need to get a lock
+ * or a reference count.
+ */
+#define list1_for_each_cookie(pos, cookie, head)                      \
+	for (({ if (!cookie)                                          \
+				     cookie = head; }),               \
+	     pos = rcu_dereference((cookie)->next);                   \
+	     prefetch(pos->next), pos != (head) || ((cookie) = NULL); \
+	     (cookie) = pos, pos = rcu_dereference(pos->next))
+
+/**
+ * list1_add_tail - add a new entry to list1 list.
+ * @new: new entry to be added.
+ * @head: list head to add it before.
+ *
+ * Same with list_add_tail_rcu() without "->prev" pointer.
+ *
+ * Caller must hold a lock for protecting @head.
+ */
+static inline void list1_add_tail(struct list1_head *new,
+				  struct list1_head *head)
+{
+	struct list1_head *prev = head;
+
+	new->next = head;
+	while (prev->next != head)
+		prev = prev->next;
+	rcu_assign_pointer(prev->next, new);
+}
+
+#endif

--


  parent reply	other threads:[~2008-10-20  7:38 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-10-20  7:34 [TOMOYO #11 (linux-next) 00/11] TOMOYO Linux Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 01/11] Introduce new LSM hooks where vfsmount is available Kentaro Takeda
2008-10-20 12:27   ` Shaya Potter
2008-10-20 19:34     ` crispin
2008-10-20 21:23       ` Shaya Potter
2008-10-23 17:57         ` Shaya Potter
2008-10-20 16:44   ` Miklos Szeredi
2008-10-21  5:09     ` Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 02/11] Add in_execve flag into task_struct Kentaro Takeda
2008-10-20  7:34 ` Kentaro Takeda [this message]
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 04/11] Introduce d_realpath() Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 05/11] Memory and pathname management functions Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 06/11] Common functions for TOMOYO Linux Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 07/11] File operation restriction part Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 08/11] Domain transition handler Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 09/11] LSM adapter functions Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 10/11] Kconfig and Makefile Kentaro Takeda
2008-10-20  7:34 ` [TOMOYO #11 (linux-next) 11/11] MAINTAINERS info Kentaro Takeda
2008-10-27  2:18 ` [TOMOYO #11 (linux-next) 00/11] TOMOYO Linux Kentaro Takeda
2008-10-29 19:18   ` Serge E. Hallyn
2008-10-30  5:27     ` Toshiharu Harada

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20081020073648.682014372@nttdata.co.jp \
    --to=takedakn@nttdata.co.jp \
    --cc=akpm@linux-foundation.org \
    --cc=chrisw@sous-sol.org \
    --cc=haradats@nttdata.co.jp \
    --cc=jmorris@namei.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-security-module@vger.kernel.org \
    --cc=penguin-kernel@I-love.SAKURA.ne.jp \
    --cc=sds@tycho.nsa.gov \
    --cc=serue@us.ibm.com \
    --subject='Re: [TOMOYO #11 (linux-next) 03/11] Singly linked list implementation.' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).