[15:27] Keybuk: for the lists, what if we swapped the prev and next pointers for cursors? [15:28] if list->next->prev != self (list->next is a cursor) [15:30] huh? [15:31] Keybuk: for cursors, cursor->next points to the previous element, and cursor->prev points to the next. We can detect this condition easily. if list->next->prev != list then list->next is a cursor [15:32] there's lots of ways like that [15:32] but they all invalidate the list in such a way that you can't just iterate on list->next [15:35] Keybuk: well, in the list head right now, the ordering is the only bit of information that isn't used [15:35] well, it is used, but that can be parted with [15:36] ? [15:37] Keybuk: if you're serious about making this multithreaded one day, I suggest you just add the flag variable, because you're going to have to put a semaphore in the list head later anyway, so the space is going to get used. [15:38] the flag still means you have to know about cursors [15:38] which means an nih_list_next () and nih_list_prev () function [15:38] (that know how to skip over them) [15:38] macros more like [15:38] and that's the nature of the problem [15:38] the stock linked list just doesn't display reentrant behavior [15:38] they have to be while loops [15:39] with a temporary variable at least [15:40] for (NihList *ptr = iter; ptr != iter && nih_list_is_cursor (ptr); ptr = ptr->next) [15:40] ; [15:41] Keybuk: you're next solution, from what I can gather, is to drop linked lists altogether. I can solve these sorts of issues slightly better with an auto-array [15:50] how does that help? [15:53] at the point you're not using a linked list, you're in strange territory that's rarely worth bothering with [17:07] what?? [17:08] an auto array helps because next and prev can be calculated for items that have gone out of existence [17:08] prev for foo[i] is foo[i-1] [17:09] and I really don't think linked list are that special [17:32] #define NIH_LIST_FOREACH_SAFE(list, i) \ [17:32] for (NihList *_copy_##i = nih_list_dup (list), *_##i = 0; \ [17:32] *(int *)&_##i < 2; ++ *(int *)&_##i) \ [17:32] if (*(int *)&_##i == 1) nih_free (_copy_##i); \ [17:32] else NIH_LIST_FOREACH (_copy_##i, i) [17:34] Wait. No, it wouldn’t work. [17:40] I didn’t think far enough. :-) [17:55] heh, copy the list? [17:55] has the same basic problem, you can't free the current or next pointer [17:56] I don't think linked lists are right here [17:56] sadmac2: any option has the same fundamental problem [17:57] Keybuk: Ordered vector + iterators listed in head structure fixes it [17:58] ?! [17:58] remove(list, x) { list.values[x] = list.values[--list.size]; for( k in list.iters) { if k >= x; k-- } } [17:59] being able to iterate by an index number rather than a pointer has its advantages [17:59] which means you can't reference from anywhere else [17:59] because the pointer to the object changes [17:59] so you have to refer by index *everywhere* [17:59] Job * becomes guint32 job_idx [18:00] not quite everywhere [18:00] only where list location is relevant [18:00] no, everywhere [18:00] because the pointer will change if you move it in the array [18:00] Keybuk: ah, but you can still have a list head in the objects [18:00] if you have a list head, then it's a linked list [18:00] not a vector [18:00] foojob->list_idx [18:01] the head contains a pointer to a parent list and its index number therein [18:01] vectors are also insanely expensive to do inserts on [18:01] Keybuk: I just did it in O(1) [18:01] it's O(len list) [18:01] Keybuk: its only expensive if you preserve order [18:02] your above was not O(1) [18:02] it was O(1 + num iters) [18:02] which leaves holes in the list [18:03] no [18:03] to remove 1) remove last element 2) put it back on top of the element you want gone 3) count-- [18:03] that doesn't preserve order [18:03] nope [18:04] * Keybuk is writing an init daemon, not a STL [18:04] well you've seen all the defects of all the possible solutions [18:04] which one do you want to live with? [18:05] honestly, I don't have a problem with the solution we had before [18:05] which is? [18:05] I still can't see why you're affected by it [18:05] cache the next pointer [18:06] fix my segfaults plz [18:06] you haven't filed any bugs [18:06] nor have you attached any core files [18:06] or stack traces [18:06] etc. [18:07] notting: can you help here^^ [18:08] oof. basically, when exiting single user mode, we would get random crashes and segfaults [18:08] but i don't have a trace with current code at the moment [18:09] notting: I don't think we've pushed anything new since 0.5.0 that would change this, and since it seems to be race-related, probably best to reproduce it on the code that failed [18:11] * sadmac2 goes to class [18:21] this is much easier in a reference/gc language :) [18:26] init.js [18:27] init.cs [18:30] the real problem is just that the nih main loop code sucks [18:30] if I fix that, then the "best way to line up a series of data structures" debate goes away :p [18:31] Switch to... glib! [18:31] * ion_ ducks [18:34] tempting [19:41] Keybuk: I'm pretty sure we fixed the main looop [19:41] we were getting an analogous issue elsewhere [19:42] the fix wasn't great I grant you, but I think that instance of the bug went away [19:42] given the main loop is the only place this pattern is used, it might simply be not in the loop functions [19:42] ie in the timer or child or signal code [19:42] by "fix the main loop" I include those [19:42] Keybuk: the other option is to do your multiparent allocator and fix it that way [19:43] I believe by doing both, I can eliminate all uses of _SAFE in the first place [19:43] Keybuk: i.e. instead of caching the next pointer, the loop simply becomes a parent as it iterates [19:43] yes === Keybuk_ is now known as Keybuk