On Apr 24, 2015 4:46 PM, "Rob Clark" <<a href="mailto:robdclark@gmail.com">robdclark@gmail.com</a>> wrote: > > On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > This commit adds a C-based linked list implementation for NIR. Unlike > > exec_list in glsl/list.h, there is no C++ API. Also, this list is based on > > wl_list (from the Wayland project) which is, in turn, based on the kernel > > list. As such, it should be fairly familiar to people who have done > > anything in kernel space. > > > > Doesn't exec_list already have a C api? > > > > Yes, it does. However, exec_list has C++ constructors for exec_list and > > exec_node. In the patches that follow, I use linked lists for use/def sets > > for registers and SSA values. In order to do so, I have to be able to > > place lists and links inside of unions. Since exec_list and exec_node have > > constructors, doing so causes any C++ code that includes nir.h to die in a > > fire. Therefore, we can't just use exec_list. > > > > What about simple_list? Why re-create it? > > > > I thought about that too. However, the simple_list is badly named and the > > API isn't that great. Making it usable as a first-class datastructure > > would have taken as much work as adding nir_list. Also, simple_list isn't > > really a standard as it's only ever used in errors.c and the vc4 driver. > > > > Why a kernel list; why not keep the symantics of exec_list? > > > > The short version: I like it better. Also, while exec_list is familiar to > > people who have worked inside the mesa GLSL compiler, I think that the > > kernel list will be more familiar to people in the open-source graphics > > community in general. For whatever it's worth, I explicitly designed it > > with separate nir_list and nir_link structures so that we can switch from > > kernel list to exec_list symantics if we want to. > > jfwiw, I am in favor of kernel(ish) lists.. although (as mentioned on > irc) maybe we just want to hoist gallium's u_double_list.h out into > util so it can be used more widely. (fwiw, I am already using > u_double_list in freedreno) I took a quick look through it. While I like the nir_list api a little better, it would work just as well. I'm not going to quibble to much over what gets used. I prefer C99 iterators, it's a *lot* better than simple_list. --Jason > > Why put this in NIR and not in util? > > > > At the moment, NIR is the only user. I do expect that Eric may want to use > > it in vc4 over simple_list. However, vc4 is already using NIR anyway, so > > it's not really that polluting. > > > > It has also been suggested by Ken that we just pull the C bits out of > > exec_list and keep one underlying implementation for both C and C++ only > > with different names. While I think that this is definitely doable and may > > be the best long-term solution, I didn't want to do that refactoring prior > > to getting this series up-and-going and adding a list was easier. I'm ok > > with doing that instead of adding a list. > > --- > > src/glsl/Makefile.sources | 1 + > > src/glsl/nir/nir_list.h | 183 ++++++++++++++++++++++++++++++++++++++++++++++ > > 2 files changed, 184 insertions(+) > > create mode 100644 src/glsl/nir/nir_list.h > > > > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources > > index c471eca..fa51dcb 100644 > > --- a/src/glsl/Makefile.sources > > +++ b/src/glsl/Makefile.sources > > @@ -28,6 +28,7 @@ NIR_FILES = \ > > nir/nir_from_ssa.c \ > > nir/nir_intrinsics.c \ > > nir/nir_intrinsics.h \ > > + nir/nir_list.h \ > > nir/nir_live_variables.c \ > > nir/nir_lower_alu_to_scalar.c \ > > nir/nir_lower_atomics.c \ > > diff --git a/src/glsl/nir/nir_list.h b/src/glsl/nir/nir_list.h > > new file mode 100644 > > index 0000000..330a660 > > --- /dev/null > > +++ b/src/glsl/nir/nir_list.h > > @@ -0,0 +1,183 @@ > > +/* > > + * Copyright © 2015 Intel Corporation > > + * > > + * Permission is hereby granted, free of charge, to any person obtaining a > > + * copy of this software and associated documentation files (the "Software"), > > + * to deal in the Software without restriction, including without limitation > > + * the rights to use, copy, modify, merge, publish, distribute, sublicense, > > + * and/or sell copies of the Software, and to permit persons to whom the > > + * Software is furnished to do so, subject to the following conditions: > > + * > > + * The above copyright notice and this permission notice (including the next > > + * paragraph) shall be included in all copies or substantial portions of the > > + * Software. > > + * > > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR > > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, > > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL > > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER > > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING > > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS > > + * IN THE SOFTWARE. > > + * > > + * Authors: > > + * Jason Ekstrand (<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>) > > + * > > + */ > > + > > +#pragma once > > + > > +#ifndef _NIR_LIST_H_ > > +#define _NIR_LIST_H_ > > + > > +/** A simple linked list implementation. > > + * > > + * This linked list implementation is based on wl_list from the Wayland > > + * project which is, in turn, based on the kernel list. As such, it should > > + * be fairly familiar to anyone who has worked in kernel space. > > + */ > > + > > +/* Required for exec_node_data */ > > +#include "../list.h" > > + > > +struct nir_link; > > + > > +/** \class nir_list > > + * > > + * \brief doubly-linked list > > + * > > + * The list head is of type nir_list and must be initialized using > > + * nir_list_init(). All entries in the list must be of the same type. The > > + * item type must have a nir_link member which must be initialized to zero. > > + * To query if the list is empty in O(1), use nir_list_is_empty(). > > + * > > + * Let's call the list reference "nir_list foo_list", the item type as > > + * "item_t", and the item member as "nir_link link". > > + * > > + * The following code will initialize a list: > > + * \code > > + * nir_list foo_list; > > + * > > + * struct item_t { > > + * int foo; > > + * nir_link link; > > + * }; > > + * struct item_t item1, item2, item3; > > + * > > + * nir_list_init(&foo_list); > > + * nir_list_insert_after(&foo_list, &item1.link); // Pushes item1 at the head > > + * nir_list_insert_after(&foo_list, &item2.link); // Pushes item2 at the head > > + * nir_list_insert_after(&item2.link, &item3.link); // Pushes item3 after item2 > > + * \endcode > > + * > > + * The list now looks like [item2, item3, item1] > > + * > > + * Iterate the list in ascending order: > > + * \code > > + * item_t *item; > > + * nir_list_foreach(item, foo_list, link) { > > + * Do_something_with_item(item); > > + * } > > + * \endcode > > + */ > > +typedef struct nir_list { > > + struct nir_link *tail; > > + struct nir_link *head; > > +} nir_list; > > + > > +typedef struct nir_link { > > + struct nir_link *prev; > > + struct nir_link *next; > > +} nir_link; > > + > > +static inline void > > +nir_list_init(nir_list *list) > > +{ > > + list->head = (nir_link *)list; > > + list->tail = (nir_link *)list; > > +} > > + > > +static inline bool > > +nir_list_is_empty(nir_list *list) > > +{ > > + return list->head == (nir_link *)list; > > +} > > + > > +static inline void > > +nir_link_init(nir_link *link) > > +{ > > + link->next = NULL; > > + link->prev = NULL; > > +} > > + > > +static inline void > > +nir_link_insert_after(nir_link *link_in_list, nir_link *after) > > +{ > > + assert(after->next == NULL && after->prev == NULL); > > + after->prev = link_in_list; > > + after->next = link_in_list->next; > > + link_in_list->next = after; > > + after->next->prev = after; > > +} > > + > > +static inline void > > +nir_link_insert_before(nir_link *link_in_list, nir_link *before) > > +{ > > + assert(before->next == NULL && before->prev == NULL); > > + before->next = link_in_list; > > + before->prev = link_in_list->prev; > > + link_in_list->prev = before; > > + before->prev->next = before; > > +} > > + > > +static inline void > > +nir_link_remove(nir_link *link) > > +{ > > + link->prev->next = link->next; > > + link->next->prev = link->prev; > > + nir_link_init(link); > > +} > > + > > +static inline void > > +nir_list_push_head(nir_list *list, nir_link *elem) > > +{ > > + nir_link_insert_after((nir_link *)list, elem); > > +} > > + > > +static inline void > > +nir_list_push_tail(nir_list *list, nir_link *elem) > > +{ > > + nir_link_insert_before((nir_link *)list, elem); > > +} > > + > > +#define nir_list_foreach(__type, __node, __field, __list) \ > > + for (__type *__node = exec_node_data(__type, (__list)->head, __field); \ > > + &(__node)->__field != (nir_link *)(__list); \ > > + __node = exec_node_data(__type, (__node)->__field.next, __field)) > > + > > +#define nir_list_foreach_safe(__type, __node, __field, __list) \ > > + for (__type *__node = exec_node_data(__type, (__list)->head, __field), \ > > + *__next = exec_node_data(__type, (__node)->__field.next, __field); \ > > + &(__node)->__field != (nir_link *)(__list); \ > > + __node = __next, \ > > + __next = exec_node_data(__type, (__next)->__field.next, __field)) > > + > > +static inline unsigned > > +nir_list_length(nir_list *list) > > +{ > > + unsigned count = 0; > > + for (nir_link *l = list->head; l != (nir_link *)list; l = l->next) > > + count++; > > + return count; > > +} > > + > > +static inline void > > +nir_list_validate(nir_list *list) > > +{ > > + assert(list->head->prev == (nir_link *)list); > > + assert(list->tail->next == (nir_link *)list); > > + for (nir_link *l = list->head; l != (nir_link *)list; l = l->next) > > + assert(l->next->prev == l && l->prev->next == l); > > +} > > + > > +#endif /* _NIR_LIST_H_ */ > > -- > > 2.3.6 > > > > _______________________________________________ > > mesa-dev mailing list > > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a>