From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-we0-x234.google.com (mail-we0-x234.google.com [IPv6:2a00:1450:400c:c03::234]) by hurricane.the-brannons.com (Postfix) with ESMTPS id B35D27863F for ; Sat, 1 Mar 2014 11:02:26 -0800 (PST) Received: by mail-we0-f180.google.com with SMTP id p61so490503wes.25 for ; Sat, 01 Mar 2014 11:01:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:cc:subject:message-id:references:mime-version :content-type:content-disposition:in-reply-to:user-agent; bh=0dM1dc3guX+d9877WhQn+svxFntzgsbMvBW8I9DS90s=; b=DkEnKh2Mw7d7wVJG9ErBLiziAQ1GWj5UenxX+uyhKl7WojahNw072VMOQ//hND/ebn UXVuVmGvuChq3hPR/tb06dSNLcBhQFFPB39ZlhTI5plrZ+qGvWg3j8asxov9OlJaPZHH MumymbQV1FDUb4MFsTt0pJ2grNRbjKjFrUoNlfablYWppfWWi4ekthVDaX7E2kPMdjoU +DZkULxUP8CCCfd6m3WdVZKf5B3zPjv1PVFT7XdbaZqj+XqIji5UqYAynkKXnKF2b6WH mc1h3R7RPThqpHAqMKwyoNxHqGt7MpXNYRnKdy0WlqHklLZZQkX8yh7ryf+KngLC6jJS TH4w== X-Received: by 10.194.234.106 with SMTP id ud10mr8482128wjc.0.1393700478346; Sat, 01 Mar 2014 11:01:18 -0800 (PST) Received: from toaster.adamthompson.me.uk (toaster.adamthompson.me.uk. [2001:8b0:1142:9042::2]) by mx.google.com with ESMTPSA id v6sm16629317wif.0.2014.03.01.11.01.16 for (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Sat, 01 Mar 2014 11:01:17 -0800 (PST) Date: Sat, 1 Mar 2014 19:01:14 +0000 From: Adam Thompson To: Karl Dahlke Message-ID: <20140301190114.GL19851@toaster.adamthompson.me.uk> References: <20140201090007.eklhad@comcast.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="ztcJpsdPpsnnlAp8" Content-Disposition: inline In-Reply-To: <20140201090007.eklhad@comcast.net> User-Agent: Mutt/1.5.21 (2010-09-15) Cc: Edbrowse-dev@lists.the-brannons.com Subject: Re: [Edbrowse-dev] tag list X-BeenThere: edbrowse-dev@lists.the-brannons.com X-Mailman-Version: 2.1.17 Precedence: list List-Id: Edbrowse Development List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 01 Mar 2014 19:02:27 -0000 --ztcJpsdPpsnnlAp8 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Mar 01, 2014 at 09:00:07AM -0500, Karl Dahlke wrote: > Well the tags are built in a growing linked list as the page is parsed, > but at the end of parse I plop them all into an array, > so it is easy to grab tag 243 (example), just index the array, > because the text in your buffer actually has encoded >=20 > tag 243 {go to this link} >=20 > You don't see tag code 243 but it's there, > and it is accessed when you go to that link. >=20 > If we want tags to continue to grow after page parse, > new tags because of javascript creating html structures etc, > then we want something with the dynamic power of a linked list or a tree > but also an easy way to index like an array. > Not sure if C++ list has this much power, or vector, > but in C there wasn't anything, which is why I made the compromise I did. > Anyways we might be able to forget the array and stay with the c++ list, > and use its power to move forward. > Create tags whenever javascript tells us to, > and they can have parent links inside them to define the tree structure > of forms and tables and so on. Yeah, I know vectors will do this for us, with the allocation policy being implementation dependant, but usually not too bad I think. In C I'd implement this manually using rea= lloc but as we're using c++ for the js stuff we can probably put the tags in a v= ector. The index into the tag vector for creating the tree structure sounds kind of nice and prevents a lot of pointers being passed around. What this means in terms of changes I think is that we stop using the list class (is this ok to do) and change tagarray from an array to a vector (not sure of capitalisation off the top of my head), then use tagArray.push_back to add tags. The parent links in the tags would be size_t variables, and each tag would also need to maintain a vector of indices to its children (of type vector I think). This is a little messy, but I'm not sure of a better implementation right now as efficient tree traversal requires an easy way to work out what a tag's children are. This implementation would allow that whilst keeping the efficient indexing required for normal browsing. The reason I'm using size_t for the parent "links" is that they'll be indices into the tag vector which means that, if in a realloc the whole lot gets moved, pointers don't suddenly become invalid etc. Cheers, Adam. --ztcJpsdPpsnnlAp8 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAEBAgAGBQJTEi56AAoJELZ22lNQBzHOBBUIAM7U5/y7H06sBMvfs9Y0uKXP I0cvyEt0Nw/2UHNszEIlR+OzLowjT8iJtb6oLyTdnAgbNVOcxLiUWKIJwfjkVUSN n037wu77+ytD7W89Xm872YWvpI8aF11ZW/Y+7agyW8rBHv+JSuY0QWUYJ40zvNMD xDS4sU+fLXfrDuUTTykPZAnWSQnyy1rf1GpDTAxTN6JiuxeOY21J6gMqi02GddtR DunJJtuWKvqUlrePWxEf1rTnf3R6sK2pKvPfV6fo0Ly+5WgFt3EH97Se86HM8wzJ XlbxtDVwmcx4NWGg/a0VpWw7UFAukOnBlGj5HMu8u/dRCA2E3j3eQdl3fz9zJQo= =uz8V -----END PGP SIGNATURE----- --ztcJpsdPpsnnlAp8--