Refactor the PacketTagList class

Refactor the PacketTagList class:  

* Document the implementation.
* Remove the freelist.  Micro benchmarks show it's no faster than new/delete.
* Trim copy-on-write to minimum copies; this was not completely implemented before.
* Refactor copy-on-write to reduce code duplication
* Add a Remove () method.

[Jeff Y, 2012-07-26 17:20:29]

Hi Peter,

  I'm still looking through the code, but I had one quick question. This patch
is listed as the last of three to address Bug 582 (serialization/deserialization
of tags), but there don't seem to be any changes to the serialization functions
in packet.cc. I can definitely understand why the last piece of the bug fix
would be separate from the PacketTagList refactor, but I just wasn't sure if I
was missing something.

--Jeff

http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-list.h
File src/network/model/packet-tag-list.h (right):

http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-lis...
src/network/model/packet-tag-list.h:45: *
This class definitely is tricky to understand, especially for a first-time
viewer. Could you briefly explain why COW semantics are used for the
PacketTagList before jumping into more details? Maybe an addition to the doxygen
comments here would help. 

My (basic) understanding is something like "PacketTagList implements a
singly-linked list of TagData objects using the Copy-on-Write (COW) scheme
because Tags are often copied (when Packets are copied) but infrequently
updated. COW allows for fast copies, and it uses branches to handle the addition
of new Tags."

[Peter Barnes, 2012-07-26 18:20:29]

On 2012/07/26 17:20:29, Jeff Y wrote:
> Hi Peter,
> 
>   I'm still looking through the code, but I had one quick question. This patch
> is listed as the last of three to address Bug 582
(serialization/deserialization
> of tags), but there don't seem to be any changes to the serialization
functions
> in packet.cc. I can definitely understand why the last piece of the bug fix
> would be separate from the PacketTagList refactor, but I just wasn't sure if I
> was missing something.

This is independent of tag serialization.

I'll add the overview as you suggest.

[Mathieu Lacage, 2012-07-28 08:01:19]

looks pretty good. I was wondering like jeff where the serialization of tags
themselves was.

http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-list.h
File src/network/model/packet-tag-list.h (right):

http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-lis...
src/network/model/packet-tag-list.h:252: typedef bool
(PacketTagList::*COWWriter_fp)
I am not a big fan of the _fp postfix...

[Peter Barnes, 2012-08-20 17:57:40]

On 2012/07/28 08:01:19, Mathieu Lacage wrote:
> looks pretty good. I was wondering like jeff where the serialization of tags
> themselves was.
> 
>
http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-list.h
> File src/network/model/packet-tag-list.h (right):
> 
>
http://codereview.appspot.com/6354061/diff/1/src/network/model/packet-tag-lis...
> src/network/model/packet-tag-list.h:252: typedef bool
> (PacketTagList::*COWWriter_fp)
> I am not a big fan of the _fp postfix...

Removed.

[Jeff Y, 2012-08-20 21:08:42]

Hi Peter,

   Your code looks good stylistically and functionally, although I'll admit I'm
not super-familiar with the freelist approach that was previously used. I would
suggest this for commit unless Mathieu had any other comments or suggestions.

   I had two  thoughts that shouldn't hold up the commit process: 
1) Would the ByteTagList benefit from using the COW semantics in a similar
fashion, or is the benefit limited due to the simplicity of ByteTags? 

2) Does COW affect traversing the PacketTagList in a deterministic fashion? For
instance, if I wanted to write a print function that prints the Tags in the same
order each time (no tags modified), can I just use "m_next" to get to the next
tag? I assume this is the case, but if not it might be nice to have a short
example of a "reader" that could be used for debug purposes (print all the tags,
for instance).   

Jeff

[Peter Barnes, 2012-08-20 22:50:16]

On 2012/08/20 21:08:42, Jeff Y wrote:
> 1) Would the ByteTagList benefit from using the COW semantics in a similar
> fashion, or is the benefit limited due to the simplicity of ByteTags? 

ByteTagList also uses COW semantics, but it's implemented differently.

> 2) Does COW affect traversing the PacketTagList in a deterministic fashion?

No.  Each packet sees an ordered list of PacketTags.  The ordering is a stack
(last in first out), and not modified by COW.