From patchwork Tue Mar 22 23:17:32 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: ben@skyportsystems.com X-Patchwork-Id: 601071 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from archives.nicira.com (archives.nicira.com [96.126.127.54]) by ozlabs.org (Postfix) with ESMTP id 3qV80L1b4Xz9sBf for ; Wed, 23 Mar 2016 10:24:02 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=skyportsystems.com header.i=@skyportsystems.com header.b=pHpE8vmw; dkim-atps=neutral Received: from archives.nicira.com (localhost [127.0.0.1]) by archives.nicira.com (Postfix) with ESMTP id 632E410535; Tue, 22 Mar 2016 16:24:01 -0700 (PDT) X-Original-To: dev@openvswitch.org Delivered-To: dev@openvswitch.org Received: from mx1e4.cudamail.com (mx1.cudamail.com [69.90.118.67]) by archives.nicira.com (Postfix) with ESMTPS id 5E35D1039D for ; Tue, 22 Mar 2016 16:23:59 -0700 (PDT) Received: from bar5.cudamail.com (unknown [192.168.21.12]) by mx1e4.cudamail.com (Postfix) with ESMTPS id D42B51E0139 for ; Tue, 22 Mar 2016 17:23:58 -0600 (MDT) X-ASG-Debug-ID: 1458688681-09eadd116d03db0001-byXFYA Received: from mx3-pf3.cudamail.com ([192.168.14.3]) by bar5.cudamail.com with ESMTP id VjDaVcPldykYmND7 (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 22 Mar 2016 17:18:01 -0600 (MDT) X-Barracuda-Envelope-From: ben@skyportsystems.com X-Barracuda-RBL-Trusted-Forwarder: 192.168.14.3 Received: from unknown (HELO mail-pf0-f176.google.com) (209.85.192.176) by mx3-pf3.cudamail.com with ESMTPS (RC4-SHA encrypted); 22 Mar 2016 23:18:00 -0000 Received-SPF: pass (mx3-pf3.cudamail.com: SPF record at _netblocks.google.com designates 209.85.192.176 as permitted sender) X-Barracuda-RBL-Trusted-Forwarder: 209.85.192.176 Received: by mail-pf0-f176.google.com with SMTP id x3so330007918pfb.1 for ; Tue, 22 Mar 2016 16:18:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=skyportsystems.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :in-reply-to:references; bh=5q19H8uniea5mLPDY2rW9NFGvdAUAOrNN2rwurN8sa8=; b=pHpE8vmwmUb5iTAlXfhfHAnAC4+cOJnTJMxb9aWsXkYRnsDF3l7CLciuIRNdVRRjhD AODTKEuVR7Htk1XJeM3D100aPNCbrsznGB1qOqqV2a1Lqub6XzpM341zHFkzAW1+NeAn b902iAJz5JkVE8HRikSvbkXKC1JdUFZKXKOF8= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:in-reply-to:references; bh=5q19H8uniea5mLPDY2rW9NFGvdAUAOrNN2rwurN8sa8=; b=S08nhMC0KQNiet2h2ASm/JL/eSEHiQkKIZEHJFHRjjnruIJndYPqdJ+CJITOpL249W vwY4l4bV6jSocqpNOWbhMYidWA80y/qvKzZ92zzt0LWpz2c1lUaNf6ouk9nXJ0z+RA5R /oueNO5GvFeKEEQoyHSFSTbHOuxOu2nO4BQ0wDmaKc0O498AYIoGug9dXqjzxfK/7CGi mDyOG3rDEBUj/SSfSDgap/gYvTQaUpBLTb8v8VymdQZ+BiJo02QFwPg74Q6ixcdF9FeJ z7sq/QyPVQ/KuDY6fekA9DSCrxvBdpoRxDvOUv0UCRI7BNCHmkREFeuGJ3cv+m/Oe7Ss hhtg== X-Gm-Message-State: AD7BkJJXSQWutlhvQtCoXZ8+IKacC+HpNi2b8iwi6bv15KEe/pfiORgF52xHVq88IocIF03o X-Received: by 10.98.32.5 with SMTP id g5mr57962888pfg.95.1458688680000; Tue, 22 Mar 2016 16:18:00 -0700 (PDT) Received: from Arrow.corp.skyportsystems.com (67-207-112-138.static.wiline.com. [67.207.112.138]) by smtp.gmail.com with ESMTPSA id 9sm50729385pft.44.2016.03.22.16.17.59 (version=TLS1 cipher=AES128-SHA bits=128/128); Tue, 22 Mar 2016 16:17:59 -0700 (PDT) X-CudaMail-Envelope-Sender: ben@skyportsystems.com X-Barracuda-Apparent-Source-IP: 67.207.112.138 From: ben@skyportsystems.com To: dev@openvswitch.org X-CudaMail-MID: CM-V3-321068376 X-CudaMail-DTE: 032216 X-CudaMail-Originating-IP: 209.85.192.176 Date: Tue, 22 Mar 2016 16:17:32 -0700 X-ASG-Orig-Subj: [##CM-V3-321068376##][PATCH v4 01/22] Move contents of lib/list.h to include/openvswitch directory Message-Id: <951c9115d97dff1d9805772a8d1a662674576abf.1458688104.git.ben@skyportsystems.com> X-Mailer: git-send-email 2.5.4 (Apple Git-61) In-Reply-To: References: In-Reply-To: References: X-GBUdb-Analysis: 0, 209.85.192.176, Ugly c=0.430172 p=-0.476923 Source Normal X-MessageSniffer-Rules: 0-0-0-32767-c X-Barracuda-Connect: UNKNOWN[192.168.14.3] X-Barracuda-Start-Time: 1458688681 X-Barracuda-Encrypted: DHE-RSA-AES256-SHA X-Barracuda-URL: https://web.cudamail.com:443/cgi-mod/mark.cgi X-Virus-Scanned: by bsmtpd at cudamail.com X-Barracuda-BRTS-Status: 1 X-Barracuda-Spam-Score: 0.60 X-Barracuda-Spam-Status: No, SCORE=0.60 using per-user scores of TAG_LEVEL=3.5 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=4.0 tests=BSF_SC5_MJ1963, DKIM_SIGNED, NO_REAL_NAME, RDNS_NONE X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.28069 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.00 NO_REAL_NAME From: does not include a real name 0.00 DKIM_SIGNED Domain Keys Identified Mail: message has a signature 0.10 RDNS_NONE Delivered to trusted network by a host with no rDNS 0.50 BSF_SC5_MJ1963 Custom Rule MJ1963 Cc: Ben Warren Subject: [ovs-dev] [PATCH v4 01/22] Move contents of lib/list.h to include/openvswitch directory X-BeenThere: dev@openvswitch.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: dev-bounces@openvswitch.org Sender: "dev" From: Ben Warren Most of the list code is properly namespaced, so is OK to move to the global export directory. Some "lib/util.h" code had to move to the other directory as well, but I've tried to make that as small as possible Signed-off-by: Ben Warren Acked-by: Ryan Moats --- include/openvswitch/list.h | 269 ++++++++++++++++++++++++++++++++++++++++++++- include/openvswitch/util.h | 101 +++++++++++++++++ lib/list.h | 263 +------------------------------------------- lib/util.h | 100 ----------------- 4 files changed, 370 insertions(+), 363 deletions(-) diff --git a/include/openvswitch/list.h b/include/openvswitch/list.h index e2b97c6..105538e 100644 --- a/include/openvswitch/list.h +++ b/include/openvswitch/list.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010, 2011, 2013 Nicira, Inc. + * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2015, 2016 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,6 +16,12 @@ #ifndef OPENVSWITCH_LIST_H #define OPENVSWITCH_LIST_H 1 +#include +#include +#include +#include +#include + /* Doubly linked list head or element. */ struct ovs_list { struct ovs_list *prev; /* Previous list element. */ @@ -24,4 +30,265 @@ struct ovs_list { #define OVS_LIST_INITIALIZER(LIST) { LIST, LIST } +/* "struct ovs_list" with pointers that will (probably) cause segfaults if + * dereferenced and, better yet, show up clearly in a debugger. + + * MSVC2015 doesn't support designated initializers when compiling C++, + * and doesn't support ternary operators with non-designated initializers. + * So we use these static definitions rather than using initializer macros. */ +static const struct ovs_list OVS_LIST_POISON = + { (struct ovs_list *) (UINTPTR_MAX / 0xf * 0xc), + (struct ovs_list *) (UINTPTR_MAX / 0xf * 0xc) }; +#define OVS_LIST_POISON \ +(struct ovs_list) { (struct ovs_list *) (uintptr_t) 0xccccccccccccccccULL, \ + (struct ovs_list *) (uintptr_t) 0xccccccccccccccccULL } + +static inline void list_init(struct ovs_list *); +static inline void list_poison(struct ovs_list *); + +/* List insertion. */ +static inline void list_insert(struct ovs_list *, struct ovs_list *); +static inline void list_splice(struct ovs_list *before, struct ovs_list *first, + struct ovs_list *last); +static inline void list_push_front(struct ovs_list *, struct ovs_list *); +static inline void list_push_back(struct ovs_list *, struct ovs_list *); +static inline void list_replace(struct ovs_list *, const struct ovs_list *); +static inline void list_moved(struct ovs_list *, const struct ovs_list *orig); +static inline void list_move(struct ovs_list *dst, struct ovs_list *src); + +/* List removal. */ +static inline struct ovs_list *list_remove(struct ovs_list *); +static inline struct ovs_list *list_pop_front(struct ovs_list *); +static inline struct ovs_list *list_pop_back(struct ovs_list *); + +/* List elements. */ +static inline struct ovs_list *list_front(const struct ovs_list *); +static inline struct ovs_list *list_back(const struct ovs_list *); + +/* List properties. */ +static inline size_t list_size(const struct ovs_list *); +static inline bool list_is_empty(const struct ovs_list *); +static inline bool list_is_singleton(const struct ovs_list *); +static inline bool list_is_short(const struct ovs_list *); + +#define LIST_FOR_EACH(ITER, MEMBER, LIST) \ + for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) +#define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST) \ + for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) +#define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST) \ + for (INIT_CONTAINER(ITER, (LIST)->prev, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) +#define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST) \ + for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) +#define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST) \ + for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ + (&(ITER)->MEMBER != (LIST) \ + ? INIT_CONTAINER(NEXT, (ITER)->MEMBER.next, MEMBER), 1 \ + : 0); \ + (ITER) = (NEXT)) +#define LIST_FOR_EACH_POP(ITER, MEMBER, LIST) \ + while (!list_is_empty(LIST) \ + && (INIT_CONTAINER(ITER, list_pop_front(LIST), MEMBER), 1)) + +/* Inline implementations. */ + +/* Initializes 'list' as an empty list. */ +static inline void +list_init(struct ovs_list *list) +{ + list->next = list->prev = list; +} + +/* Initializes 'list' with pointers that will (probably) cause segfaults if + * dereferenced and, better yet, show up clearly in a debugger. */ +static inline void +list_poison(struct ovs_list *list) +{ + *list = OVS_LIST_POISON; +} + +/* Inserts 'elem' just before 'before'. */ +static inline void +list_insert(struct ovs_list *before, struct ovs_list *elem) +{ + elem->prev = before->prev; + elem->next = before; + before->prev->next = elem; + before->prev = elem; +} + +/* Removes elements 'first' though 'last' (exclusive) from their current list, + then inserts them just before 'before'. */ +static inline void +list_splice(struct ovs_list *before, struct ovs_list *first, struct ovs_list *last) +{ + if (first == last) { + return; + } + last = last->prev; + + /* Cleanly remove 'first'...'last' from its current list. */ + first->prev->next = last->next; + last->next->prev = first->prev; + + /* Splice 'first'...'last' into new list. */ + first->prev = before->prev; + last->next = before; + before->prev->next = first; + before->prev = last; +} + +/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in + 'list'. */ +static inline void +list_push_front(struct ovs_list *list, struct ovs_list *elem) +{ + list_insert(list->next, elem); +} + +/* Inserts 'elem' at the end of 'list', so that it becomes the back in + * 'list'. */ +static inline void +list_push_back(struct ovs_list *list, struct ovs_list *elem) +{ + list_insert(list, elem); +} + +/* Puts 'elem' in the position currently occupied by 'position'. + * Afterward, 'position' is not part of a list. */ +static inline void +list_replace(struct ovs_list *element, const struct ovs_list *position) +{ + element->next = position->next; + element->next->prev = element; + element->prev = position->prev; + element->prev->next = element; +} + +/* Adjusts pointers around 'list' to compensate for 'list' having been moved + * around in memory (e.g. as a consequence of realloc()), with original + * location 'orig'. + * + * ('orig' likely points to freed memory, but this function does not + * dereference 'orig', it only compares it to 'list'. In a very pedantic + * language lawyer sense, this still yields undefined behavior, but it works + * with actual compilers.) */ +static inline void +list_moved(struct ovs_list *list, const struct ovs_list *orig) +{ + if (list->next == orig) { + list_init(list); + } else { + list->prev->next = list->next->prev = list; + } +} + +/* Initializes 'dst' with the contents of 'src', compensating for moving it + * around in memory. The effect is that, if 'src' was the head of a list, now + * 'dst' is the head of a list containing the same elements. */ +static inline void +list_move(struct ovs_list *dst, struct ovs_list *src) +{ + *dst = *src; + list_moved(dst, src); +} + +/* Removes 'elem' from its list and returns the element that followed it. + Undefined behavior if 'elem' is not in a list. */ +static inline struct ovs_list * +list_remove(struct ovs_list *elem) +{ + elem->prev->next = elem->next; + elem->next->prev = elem->prev; + return elem->next; +} + +/* Removes the front element from 'list' and returns it. Undefined behavior if + 'list' is empty before removal. */ +static inline struct ovs_list * +list_pop_front(struct ovs_list *list) +{ + struct ovs_list *front = list->next; + + list_remove(front); + return front; +} + +/* Removes the back element from 'list' and returns it. + Undefined behavior if 'list' is empty before removal. */ +static inline struct ovs_list * +list_pop_back(struct ovs_list *list) +{ + struct ovs_list *back = list->prev; + + list_remove(back); + return back; +} + +/* Returns the front element in 'list_'. + Undefined behavior if 'list_' is empty. */ +static inline struct ovs_list * +list_front(const struct ovs_list *list_) +{ + struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); + + ovs_assert(!list_is_empty(list)); + + return list->next; +} + +/* Returns the back element in 'list_'. + Undefined behavior if 'list_' is empty. */ +static inline struct ovs_list * +list_back(const struct ovs_list *list_) +{ + struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); + + ovs_assert(!list_is_empty(list)); + + return list->prev; +} + +/* Returns the number of elements in 'list'. + Runs in O(n) in the number of elements. */ +static inline size_t +list_size(const struct ovs_list *list) +{ + const struct ovs_list *e; + size_t cnt = 0; + + for (e = list->next; e != list; e = e->next) { + cnt++; + } + return cnt; +} + +/* Returns true if 'list' is empty, false otherwise. */ +static inline bool +list_is_empty(const struct ovs_list *list) +{ + return list->next == list; +} + +/* Returns true if 'list' has exactly 1 element, false otherwise. */ +static inline bool +list_is_singleton(const struct ovs_list *list) +{ + return list_is_short(list) && !list_is_empty(list); +} + +/* Returns true if 'list' has 0 or 1 elements, false otherwise. */ +static inline bool +list_is_short(const struct ovs_list *list) +{ + return list->next == list->prev; +} + #endif /* list.h */ diff --git a/include/openvswitch/util.h b/include/openvswitch/util.h index 683f76b..63c8a45 100644 --- a/include/openvswitch/util.h +++ b/include/openvswitch/util.h @@ -18,6 +18,7 @@ #define OPENVSWITCH_UTIL_H 1 #include +#include #ifdef __cplusplus extern "C" { @@ -46,6 +47,106 @@ const char *ovs_get_program_version(void); : (X) <= UINT_MAX / (Y) ? (unsigned int) (X) * (unsigned int) (Y) \ : UINT_MAX) +/* Like the standard assert macro, except writes the failure message to the + * log. */ +#ifndef NDEBUG +#define ovs_assert(CONDITION) \ + if (!OVS_LIKELY(CONDITION)) { \ + ovs_assert_failure(OVS_SOURCE_LOCATOR, __func__, #CONDITION); \ + } +#else +#define ovs_assert(CONDITION) ((void) (CONDITION)) +#endif +OVS_NO_RETURN void ovs_assert_failure(const char *, const char *, const char *); + +/* This is a void expression that issues a compiler error if POINTER cannot be + * compared for equality with the given pointer TYPE. This generally means + * that POINTER is a qualified or unqualified TYPE. However, + * BUILD_ASSERT_TYPE(POINTER, void *) will accept any pointer to object type, + * because any pointer to object can be compared for equality with "void *". + * + * POINTER can be any expression. The use of "sizeof" ensures that the + * expression is not actually evaluated, so that any side effects of the + * expression do not occur. + * + * The cast to int is present only to suppress an "expression using sizeof + * bool" warning from "sparse" (see + * http://permalink.gmane.org/gmane.comp.parsers.sparse/2967). */ +#define BUILD_ASSERT_TYPE(POINTER, TYPE) \ + ((void) sizeof ((int) ((POINTER) == (TYPE) (POINTER)))) + +/* Casts 'pointer' to 'type' and issues a compiler warning if the cast changes + * anything other than an outermost "const" or "volatile" qualifier. + * + * The cast to int is present only to suppress an "expression using sizeof + * bool" warning from "sparse" (see + * http://permalink.gmane.org/gmane.comp.parsers.sparse/2967). */ +#define CONST_CAST(TYPE, POINTER) \ + (BUILD_ASSERT_TYPE(POINTER, TYPE), \ + (TYPE) (POINTER)) + +/* Given a pointer-typed lvalue OBJECT, expands to a pointer type that may be + * assigned to OBJECT. */ +#ifdef __GNUC__ +#define OVS_TYPEOF(OBJECT) typeof(OBJECT) +#else +#define OVS_TYPEOF(OBJECT) void * +#endif + +/* Given OBJECT of type pointer-to-structure, expands to the offset of MEMBER + * within an instance of the structure. + * + * The GCC-specific version avoids the technicality of undefined behavior if + * OBJECT is null, invalid, or not yet initialized. This makes some static + * checkers (like Coverity) happier. But the non-GCC version does not actually + * dereference any pointer, so it would be surprising for it to cause any + * problems in practice. + */ +#ifdef __GNUC__ +#define OBJECT_OFFSETOF(OBJECT, MEMBER) offsetof(typeof(*(OBJECT)), MEMBER) +#else +#define OBJECT_OFFSETOF(OBJECT, MEMBER) \ + ((char *) &(OBJECT)->MEMBER - (char *) (OBJECT)) +#endif + +/* Yields the size of MEMBER within STRUCT. */ +#define MEMBER_SIZEOF(STRUCT, MEMBER) (sizeof(((STRUCT *) NULL)->MEMBER)) + +/* Yields the offset of the end of MEMBER within STRUCT. */ +#define OFFSETOFEND(STRUCT, MEMBER) \ + (offsetof(STRUCT, MEMBER) + MEMBER_SIZEOF(STRUCT, MEMBER)) + +/* Given POINTER, the address of the given MEMBER in a STRUCT object, returns + the STRUCT object. */ +#define CONTAINER_OF(POINTER, STRUCT, MEMBER) \ + ((STRUCT *) (void *) ((char *) (POINTER) - offsetof (STRUCT, MEMBER))) + +/* Given POINTER, the address of the given MEMBER within an object of the type + * that that OBJECT points to, returns OBJECT as an assignment-compatible + * pointer type (either the correct pointer type or "void *"). OBJECT must be + * an lvalue. + * + * This is the same as CONTAINER_OF except that it infers the structure type + * from the type of '*OBJECT'. */ +#define OBJECT_CONTAINING(POINTER, OBJECT, MEMBER) \ + ((OVS_TYPEOF(OBJECT)) (void *) \ + ((char *) (POINTER) - OBJECT_OFFSETOF(OBJECT, MEMBER))) + +/* Given POINTER, the address of the given MEMBER within an object of the type + * that that OBJECT points to, assigns the address of the outer object to + * OBJECT, which must be an lvalue. + * + * Evaluates to (void) 0 as the result is not to be used. */ +#define ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER) \ + ((OBJECT) = OBJECT_CONTAINING(POINTER, OBJECT, MEMBER), (void) 0) + +/* As explained in the comment above OBJECT_OFFSETOF(), non-GNUC compilers + * like MSVC will complain about un-initialized variables if OBJECT + * hasn't already been initialized. To prevent such warnings, INIT_CONTAINER() + * can be used as a wrapper around ASSIGN_CONTAINER. */ +#define INIT_CONTAINER(OBJECT, POINTER, MEMBER) \ + ((OBJECT) = NULL, ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER)) + #ifdef __cplusplus } #endif diff --git a/lib/list.h b/lib/list.h index 96bbafd..f641d39 100644 --- a/lib/list.h +++ b/lib/list.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2015, 2016 Nicira, Inc. + * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2015 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -18,267 +18,6 @@ /* Doubly linked list. */ -#include -#include -#include "util.h" #include "openvswitch/list.h" -/* "struct ovs_list" with pointers that will (probably) cause segfaults if - * dereferenced and, better yet, show up clearly in a debugger. - - * MSVC2015 doesn't support designated initializers when compiling C++, - * and doesn't support ternary operators with non-designated initializers. - * So we use these static definitions rather than using initializer macros. */ -static const struct ovs_list OVS_LIST_POISON = - { (struct ovs_list *) (UINTPTR_MAX / 0xf * 0xc), - (struct ovs_list *) (UINTPTR_MAX / 0xf * 0xc) }; - -static inline void list_init(struct ovs_list *); -static inline void list_poison(struct ovs_list *); - -/* List insertion. */ -static inline void list_insert(struct ovs_list *, struct ovs_list *); -static inline void list_splice(struct ovs_list *before, struct ovs_list *first, - struct ovs_list *last); -static inline void list_push_front(struct ovs_list *, struct ovs_list *); -static inline void list_push_back(struct ovs_list *, struct ovs_list *); -static inline void list_replace(struct ovs_list *, const struct ovs_list *); -static inline void list_moved(struct ovs_list *, const struct ovs_list *orig); -static inline void list_move(struct ovs_list *dst, struct ovs_list *src); - -/* List removal. */ -static inline struct ovs_list *list_remove(struct ovs_list *); -static inline struct ovs_list *list_pop_front(struct ovs_list *); -static inline struct ovs_list *list_pop_back(struct ovs_list *); - -/* List elements. */ -static inline struct ovs_list *list_front(const struct ovs_list *); -static inline struct ovs_list *list_back(const struct ovs_list *); - -/* List properties. */ -static inline size_t list_size(const struct ovs_list *); -static inline bool list_is_empty(const struct ovs_list *); -static inline bool list_is_singleton(const struct ovs_list *); -static inline bool list_is_short(const struct ovs_list *); - -#define LIST_FOR_EACH(ITER, MEMBER, LIST) \ - for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ - &(ITER)->MEMBER != (LIST); \ - ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) -#define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST) \ - for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER); \ - &(ITER)->MEMBER != (LIST); \ - ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) -#define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST) \ - for (INIT_CONTAINER(ITER, (LIST)->prev, MEMBER); \ - &(ITER)->MEMBER != (LIST); \ - ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) -#define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST) \ - for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ - &(ITER)->MEMBER != (LIST); \ - ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) -#define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST) \ - for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ - (&(ITER)->MEMBER != (LIST) \ - ? INIT_CONTAINER(NEXT, (ITER)->MEMBER.next, MEMBER), 1 \ - : 0); \ - (ITER) = (NEXT)) -#define LIST_FOR_EACH_POP(ITER, MEMBER, LIST) \ - while (!list_is_empty(LIST) \ - && (INIT_CONTAINER(ITER, list_pop_front(LIST), MEMBER), 1)) - -/* Inline implementations. */ - -/* Initializes 'list' as an empty list. */ -static inline void -list_init(struct ovs_list *list) -{ - list->next = list->prev = list; -} - -/* Initializes 'list' with pointers that will (probably) cause segfaults if - * dereferenced and, better yet, show up clearly in a debugger. */ -static inline void -list_poison(struct ovs_list *list) -{ - *list = OVS_LIST_POISON; -} - -/* Inserts 'elem' just before 'before'. */ -static inline void -list_insert(struct ovs_list *before, struct ovs_list *elem) -{ - elem->prev = before->prev; - elem->next = before; - before->prev->next = elem; - before->prev = elem; -} - -/* Removes elements 'first' though 'last' (exclusive) from their current list, - then inserts them just before 'before'. */ -static inline void -list_splice(struct ovs_list *before, struct ovs_list *first, struct ovs_list *last) -{ - if (first == last) { - return; - } - last = last->prev; - - /* Cleanly remove 'first'...'last' from its current list. */ - first->prev->next = last->next; - last->next->prev = first->prev; - - /* Splice 'first'...'last' into new list. */ - first->prev = before->prev; - last->next = before; - before->prev->next = first; - before->prev = last; -} - -/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in - 'list'. */ -static inline void -list_push_front(struct ovs_list *list, struct ovs_list *elem) -{ - list_insert(list->next, elem); -} - -/* Inserts 'elem' at the end of 'list', so that it becomes the back in - * 'list'. */ -static inline void -list_push_back(struct ovs_list *list, struct ovs_list *elem) -{ - list_insert(list, elem); -} - -/* Puts 'elem' in the position currently occupied by 'position'. - * Afterward, 'position' is not part of a list. */ -static inline void -list_replace(struct ovs_list *element, const struct ovs_list *position) -{ - element->next = position->next; - element->next->prev = element; - element->prev = position->prev; - element->prev->next = element; -} - -/* Adjusts pointers around 'list' to compensate for 'list' having been moved - * around in memory (e.g. as a consequence of realloc()), with original - * location 'orig'. - * - * ('orig' likely points to freed memory, but this function does not - * dereference 'orig', it only compares it to 'list'. In a very pedantic - * language lawyer sense, this still yields undefined behavior, but it works - * with actual compilers.) */ -static inline void -list_moved(struct ovs_list *list, const struct ovs_list *orig) -{ - if (list->next == orig) { - list_init(list); - } else { - list->prev->next = list->next->prev = list; - } -} - -/* Initializes 'dst' with the contents of 'src', compensating for moving it - * around in memory. The effect is that, if 'src' was the head of a list, now - * 'dst' is the head of a list containing the same elements. */ -static inline void -list_move(struct ovs_list *dst, struct ovs_list *src) -{ - *dst = *src; - list_moved(dst, src); -} - -/* Removes 'elem' from its list and returns the element that followed it. - Undefined behavior if 'elem' is not in a list. */ -static inline struct ovs_list * -list_remove(struct ovs_list *elem) -{ - elem->prev->next = elem->next; - elem->next->prev = elem->prev; - return elem->next; -} - -/* Removes the front element from 'list' and returns it. Undefined behavior if - 'list' is empty before removal. */ -static inline struct ovs_list * -list_pop_front(struct ovs_list *list) -{ - struct ovs_list *front = list->next; - - list_remove(front); - return front; -} - -/* Removes the back element from 'list' and returns it. - Undefined behavior if 'list' is empty before removal. */ -static inline struct ovs_list * -list_pop_back(struct ovs_list *list) -{ - struct ovs_list *back = list->prev; - - list_remove(back); - return back; -} - -/* Returns the front element in 'list_'. - Undefined behavior if 'list_' is empty. */ -static inline struct ovs_list * -list_front(const struct ovs_list *list_) -{ - struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); - - ovs_assert(!list_is_empty(list)); - - return list->next; -} - -/* Returns the back element in 'list_'. - Undefined behavior if 'list_' is empty. */ -static inline struct ovs_list * -list_back(const struct ovs_list *list_) -{ - struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); - - ovs_assert(!list_is_empty(list)); - - return list->prev; -} - -/* Returns the number of elements in 'list'. - Runs in O(n) in the number of elements. */ -static inline size_t -list_size(const struct ovs_list *list) -{ - const struct ovs_list *e; - size_t cnt = 0; - - for (e = list->next; e != list; e = e->next) { - cnt++; - } - return cnt; -} - -/* Returns true if 'list' is empty, false otherwise. */ -static inline bool -list_is_empty(const struct ovs_list *list) -{ - return list->next == list; -} - -/* Returns true if 'list' has exactly 1 element, false otherwise. */ -static inline bool -list_is_singleton(const struct ovs_list *list) -{ - return list_is_short(list) && !list_is_empty(list); -} - -/* Returns true if 'list' has 0 or 1 elements, false otherwise. */ -static inline bool -list_is_short(const struct ovs_list *list) -{ - return list->next == list->prev; -} - #endif /* list.h */ diff --git a/lib/util.h b/lib/util.h index 389c093..df545fe 100644 --- a/lib/util.h +++ b/lib/util.h @@ -67,44 +67,6 @@ #define BUILD_ASSERT_DECL_GCCONLY(EXPR) ((void) 0) #endif -/* Like the standard assert macro, except writes the failure message to the - * log. */ -#ifndef NDEBUG -#define ovs_assert(CONDITION) \ - if (!OVS_LIKELY(CONDITION)) { \ - ovs_assert_failure(OVS_SOURCE_LOCATOR, __func__, #CONDITION); \ - } -#else -#define ovs_assert(CONDITION) ((void) (CONDITION)) -#endif -OVS_NO_RETURN void ovs_assert_failure(const char *, const char *, const char *); - -/* This is a void expression that issues a compiler error if POINTER cannot be - * compared for equality with the given pointer TYPE. This generally means - * that POINTER is a qualified or unqualified TYPE. However, - * BUILD_ASSERT_TYPE(POINTER, void *) will accept any pointer to object type, - * because any pointer to object can be compared for equality with "void *". - * - * POINTER can be any expression. The use of "sizeof" ensures that the - * expression is not actually evaluated, so that any side effects of the - * expression do not occur. - * - * The cast to int is present only to suppress an "expression using sizeof - * bool" warning from "sparse" (see - * http://permalink.gmane.org/gmane.comp.parsers.sparse/2967). */ -#define BUILD_ASSERT_TYPE(POINTER, TYPE) \ - ((void) sizeof ((int) ((POINTER) == (TYPE) (POINTER)))) - -/* Casts 'pointer' to 'type' and issues a compiler warning if the cast changes - * anything other than an outermost "const" or "volatile" qualifier. - * - * The cast to int is present only to suppress an "expression using sizeof - * bool" warning from "sparse" (see - * http://permalink.gmane.org/gmane.comp.parsers.sparse/2967). */ -#define CONST_CAST(TYPE, POINTER) \ - (BUILD_ASSERT_TYPE(POINTER, TYPE), \ - (TYPE) (POINTER)) - extern char *program_name; #define __ARRAY_SIZE_NOCHECK(ARRAY) (sizeof(ARRAY) / sizeof((ARRAY)[0])) @@ -191,68 +153,6 @@ ovs_prefetch_range(const void *start, size_t size) #define OVS_NOT_REACHED() abort() -/* Given a pointer-typed lvalue OBJECT, expands to a pointer type that may be - * assigned to OBJECT. */ -#ifdef __GNUC__ -#define OVS_TYPEOF(OBJECT) typeof(OBJECT) -#else -#define OVS_TYPEOF(OBJECT) void * -#endif - -/* Given OBJECT of type pointer-to-structure, expands to the offset of MEMBER - * within an instance of the structure. - * - * The GCC-specific version avoids the technicality of undefined behavior if - * OBJECT is null, invalid, or not yet initialized. This makes some static - * checkers (like Coverity) happier. But the non-GCC version does not actually - * dereference any pointer, so it would be surprising for it to cause any - * problems in practice. - */ -#ifdef __GNUC__ -#define OBJECT_OFFSETOF(OBJECT, MEMBER) offsetof(typeof(*(OBJECT)), MEMBER) -#else -#define OBJECT_OFFSETOF(OBJECT, MEMBER) \ - ((char *) &(OBJECT)->MEMBER - (char *) (OBJECT)) -#endif - -/* Yields the size of MEMBER within STRUCT. */ -#define MEMBER_SIZEOF(STRUCT, MEMBER) (sizeof(((STRUCT *) NULL)->MEMBER)) - -/* Yields the offset of the end of MEMBER within STRUCT. */ -#define OFFSETOFEND(STRUCT, MEMBER) \ - (offsetof(STRUCT, MEMBER) + MEMBER_SIZEOF(STRUCT, MEMBER)) - -/* Given POINTER, the address of the given MEMBER in a STRUCT object, returns - the STRUCT object. */ -#define CONTAINER_OF(POINTER, STRUCT, MEMBER) \ - ((STRUCT *) (void *) ((char *) (POINTER) - offsetof (STRUCT, MEMBER))) - -/* Given POINTER, the address of the given MEMBER within an object of the type - * that that OBJECT points to, returns OBJECT as an assignment-compatible - * pointer type (either the correct pointer type or "void *"). OBJECT must be - * an lvalue. - * - * This is the same as CONTAINER_OF except that it infers the structure type - * from the type of '*OBJECT'. */ -#define OBJECT_CONTAINING(POINTER, OBJECT, MEMBER) \ - ((OVS_TYPEOF(OBJECT)) (void *) \ - ((char *) (POINTER) - OBJECT_OFFSETOF(OBJECT, MEMBER))) - -/* Given POINTER, the address of the given MEMBER within an object of the type - * that that OBJECT points to, assigns the address of the outer object to - * OBJECT, which must be an lvalue. - * - * Evaluates to (void) 0 as the result is not to be used. */ -#define ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER) \ - ((OBJECT) = OBJECT_CONTAINING(POINTER, OBJECT, MEMBER), (void) 0) - -/* As explained in the comment above OBJECT_OFFSETOF(), non-GNUC compilers - * like MSVC will complain about un-initialized variables if OBJECT - * hasn't already been initialized. To prevent such warnings, INIT_CONTAINER() - * can be used as a wrapper around ASSIGN_CONTAINER. */ -#define INIT_CONTAINER(OBJECT, POINTER, MEMBER) \ - ((OBJECT) = NULL, ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER)) - /* Given ATTR, and TYPE, cast the ATTR to TYPE by first casting ATTR to * (void *). This is to suppress the alignment warning issued by clang. */ #define ALIGNED_CAST(TYPE, ATTR) ((TYPE) (void *) (ATTR))