Hi, On 2021-11-06 14:06:12 -0400, Tom Lane wrote: > I wrote: > > Hm. I think it's not the only list function with O(N) behavior; > > in fact there used to be more such functions than there are now. > > But I could get behind a patch that annotates all of them.
Personally I think the delete first is particularly easy to run into, due to implementing fifo like behaviour. But I'm i > Here's a quick hack at that. Having done it, I'm not sure if it's > really worth the trouble or not ... thoughts? In favor of adding them. > @@ -870,6 +890,9 @@ list_delete_oid(List *list, Oid datum) > * where the intent is to alter the list rather than just traverse it. > * Beware that the list is modified, whereas the Lisp-y coding leaves > * the original list head intact in case there's another pointer to it. > + * > + * Note that this takes time proportional to the length of the list, > + * since the remaining entries must be moved. > */ > List * > list_delete_first(List *list) Perhaps we could point to list_delete_last()? But it's an improvement without that too. This reminds me that I wanted a list splicing operation for ilist.h... Greetings, Andres Freund
