Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:43353
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.158 as permitted sender)
DomainKey-Status: bad
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:sender:in-reply-to:references:date
         :x-google-sender-auth:message-id:subject:from:to:cc:content-type
         :content-transfer-encoding;
        b=THvdDgJ5odyMP2mVja8f3lntuB6SH9gTJFhh0UhZzq+KekBpHl7q+j4ZwlhlVn6OmG
         0jB7zJfdCRUPeylKzn5EkodC9UQuIoQJlJ3KNgXoM2sr5Qk2v5m8upsN3VdDI8bbReil
         GFIlKZ0cCE1kVAEGXVQu47PYyYz8jzkFz6kAM=
MIME-Version: 1.0
Sender: ekneuss@gmail.com
In-Reply-To: <AF.96.06903.F700DB94@pb1.pair.com>
References: <AF.96.06903.F700DB94@pb1.pair.com>
Date: Sun, 15 Mar 2009 19:09:10 +0100
Message-ID: <e666c3890903151109k1261165q17b6e954624d14cd@mail.gmail.com>
To: Ben Smithers <gingerrobot@gmail.com>
Cc: internals@lists.php.net
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] SplStack Implementation
From: webmaster@colder.ch (Etienne Kneuss)

Hello,

On Sun, Mar 15, 2009 at 2:19 PM, Ben Smithers <gingerrobot@gmail.com> wrote:
> Firstly, apologies if this is not the correct place to ask such a question -
> I was directed here from a forum.
>
> I recently discovered the datastructures found in the Standard PHP Library.
> I noticed that SplStack is implemented using a doubly-linked list and
> wondered why. Given that a stack is LIFO store and the only operations
> really needed are push and pop, why would next and previous pointers be
> required on each item? There's no requirement to allow iteration over a
> stack.
>
> It would seem to me that a stack should require a linear linked list and a
> pointer to the top of the stack - which would have roughly half the memory
> overhead of a doubly-linked list (half the number of pointers).
>
> Do i just have no idea what i'm talking about or have i missed something
> obvious?

You're right, a stack can be implemented in a simpler way that would
reduce slightly the memory usage.
However, storing one additional pointer per doubly linkedlist (DLL)
node and managing it is totally irrelevant when placed in context of
PHP code.

If you look at the code, you'll see that the additionnal code to make
a DLL work as a stack is very small, and that's why it was implemented
like that.

One could implement a stack and a queue using a single linked list,
but that would mean code duplication which ends up to be not worth the
irrelevant speed/memory improvement.

If SPLinkedList is implemented once, we might consider move SplStack
and SplQueue to use that new implementation, but I believe there are
other priorities for SPL right now, such as documentation.

Regards,


>
> Thanks in advance,
>
> Ben
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>



-- 
Etienne Kneuss
http://www.colder.ch

Men never do evil so completely and cheerfully as
when they do it from a religious conviction.
-- Pascal