On Wed, Sep 16, 2015 at 4:49 PM, Mike Rappazzo <rappazzo@xxxxxxxxx> wrote:
> On Wed, Sep 16, 2015 at 4:32 PM, Eric Sunshine <sunshine@xxxxxxxxxxxxxx> wrote:
>> On Mon, Sep 14, 2015 at 8:20 AM, Mike Rappazzo <rappazzo@xxxxxxxxx> wrote:
>>> On Sat, Sep 12, 2015 at 10:39 PM, Eric Sunshine <sunshine@xxxxxxxxxxxxxx> 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?
The sentinel would indeed be a dummy worktree structure, which may be
very slightly ugly, however, it's dead simple, both in implementation
and from client viewpoint, whereas other approaches increase
complexity.
Making the last entry a NULL means get_worktrees() would have to
return an array of pointers rather than an array of structures, which
is more syntactically noisy, and complex since it's harder to reason
about pointer-to-pointer. In my mind, at least, the simplicity of the
array of structures approach (even with the slight ugliness of the
dummy sentinel) outweighs the complexity of the array-of-pointers
approach.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html