Re: [PATCH v7 1/3] worktree: add top-level worktree.c

> On Wed, Sep 16, 2015 at 4:32 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
>> On Mon, Sep 14, 2015 at 8:20 AM, Mike Rappazzo <rappazzo@gmail.com> wrote:
>>> On Sat, Sep 12, 2015 at 10:39 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
>>>> I don't care too strongly, but an alternate approach (which I probably
>>>> would have taken) would be to have get_worktrees() simply return an
>>>> array of 'struct worktree' objects, hence no need for the additional
>>>> 'struct worktree_list'. The slight complication with this approach,
>>>> though, is that get_worktrees() either also needs to return the length
>>>> of the array, or the array should end with some sort of end-of-array
>>>> sentinel. An obvious sentinel would be path==NULL or git_dir==NULL or
>>>> all of the above.
>>>>
>>>> Client iteration is just about the same with the array approach as
>>>> with the linked-list approach.
>>>
>>> I can't see what benefit this would provide.  I would sooner change
>>> the returned list into
>>> an array-backed list struct.  Alternatively, I think adding a
>>> list_head pointer to this structure
>>> could benefit client code.
>>
>> The benefit is a reduction in complexity, which is an important goal.
>> Linked lists are inherently more complex than arrays, requiring extra
>> effort, and especially extra care, to manage the head, each "next"
>> pointer (and possibly a tail pointer). Arrays are used often in Git,
>> thus are familiar in this code-base, and Git has decent support for
>> making their management relatively painless. Your suggestions of
>> changing into "an array-backed list structure" or "adding list_head
>> pointer" increase complexity, rather than reduce it.
>>
>> Aside from the complexity issue, arrays allow random access, whereas
>> linked lists allow only sequential access. While this limitation may
>> not impact your current, planned use of get_worktrees(), it places a
>> potentially unnecessary restriction on future clients.
>>
>> And, as noted, client iteration is at least as convenient with arrays,
>> if not moreso, due to the reduction in noise ("p++" rather than "p =
>> p->next").
>>
>>     struct worktree *p;
>>     for (p = get_worktrees(); p->path; p++)
>>         blarp(p);
>>
>> There are cases where linked lists are an obvious win, but this
>> doesn't seem to be such a case. On the other hand, there are obvious
>> benefits to making this an array, such as reduced complexity and
>> removal of the sequential-access-only restriction.
>
> What you are suggesting makes sense, but I feel it falls short when it
> comes to the "sentinel".  Would the last element in the list be a
> dummy worktree?  I would sooner add a NULL to the end.  Would that be
> an acceptable implementation?