Project

General

Profile

Actions
Copy link

Feature #2998

closed

Block::insert and Block::erase

Added by Junxiao Shi over 9 years ago. Updated over 9 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Joao Pereira
Category:
Base
Target version:
v0.4
Start date:
07/07/2015
Due date:
% Done:

100%

Estimated time:
1.50 h

Description

In Block abstraction, allow inserting an element at a specified position.

element_iterator
insert(element_const_iterator pos, const Block& element);

Change the parameter type and return type of Block::erase from element_iterator to element_const_iterator.

Parameter type is element_const_iterator, because both find and elements_begin return element_const_iterator, so that the caller is unable to obtain a element_iterator.
Using element_const_iterator is also consistent with C++11 APIs.

std::vector<..>::insert and std::vector<..>::erase installed with gcc46 on Ubuntu 12.04 does not take const_iterator.

This problem can be solved by internally converting from elements_const_iterator to elements_iterator with std::advance.

Compiler-feature detection should be performed to detect the necessity of this trick; this trick shall be wrapped in #ifdef.

Related issues 1 (0 open — 1 closed)

Blocks ndn-cxx - Feature #2879: NDNLPv2: Packet and FieldsClosedEric Newberry06/10/2015

Actions
Actions
Copy link
 #1

Updated by Junxiao Shi over 9 years ago

Actions
Copy link
 #2

Updated by Joao Pereira over 9 years ago

Does this feature one need to add 1 functions or are we going to implement the same overloads of std::vector::insert??

Actions
Copy link
 #3

Updated by Junxiao Shi over 9 years ago

Answer to note-2: For the purpose of #2879, only one function is needed.

Actions
Copy link
 #4

Updated by Joao Pereira over 9 years ago

Should the function do any kind of checking or just call the insert method in the vector?

Actions
Copy link
 #5

Updated by Junxiao Shi over 9 years ago

Reply to note-4: I do not have an answer. The assignee should figure this out.

Actions
Copy link
 #6

Updated by Joao Pereira over 9 years ago

  • Status changed from New to In Progress
  • Assignee set to Joao Pereira
  • Start date set to 07/07/2015
Actions
Copy link
 #7

Updated by Joao Pereira over 9 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 0 to 100
Actions
Copy link
 #8

Updated by Joao Pereira over 9 years ago

Added UT

Actions
Copy link
 #9

Updated by Joao Pereira over 9 years ago

I just read again the specification and the function that should be added should not use const's.

Can I change the prototype of the function to 

element_const_iterator
insert(element_const_iterator pos, const Block& element);
Actions
Copy link
 #10

Updated by Junxiao Shi over 9 years ago

Answer to note-9:

You can, but gcc46 on Ubuntu 12.04 doesn't like const_iterator in std::vector<..>::insert, so there would be lots of trouble to make it work.

Actions
Copy link
 #11

Updated by Joao Pereira over 9 years ago

I just saw the error in Jenkins. I developed it with the const iterators because looking at the interface there is no function that returns a non constant reference to the elements vector.

With the consts this would work

  Block::element_const_iterator it = masterBlock.find(tlv::NameComponent);
  it = masterBlock.insert(it, firstBlock);

Without the const's I am not sure if we have any scenario where we can use the function

Can you give me an example of usage of the insert without the const?

Actions
Copy link
 #12

Updated by Junxiao Shi over 9 years ago

  • Status changed from Code review to Feedback

Reply to note-11:

This problem applies to not only Block::insert, but also Block::erase.

There are two solutions:

  • Add non-const overloads that returns element_iterator for find, elements_begin, and elements_end.
  • Accept and return element_const_iterator in insert and erase. For gcc46, internally convert to element_iterator with:
    std::advance(m_subBlocks.begin(), std::distance(m_subBlocks.cbegin(), it)) reference
    This has no performance penalty given the m_subBlocks is a vector.

I prefer the second solution which is more consistent with C++11 API.
The workaround can also be deleted after we drop Ubuntu 12.04 support in Apr 2016.

I have invited @Alex and @Eric to comment on this question.

Actions
Copy link
 #13

Updated by Joao Pereira over 9 years ago

I agree with the suggestion of std::advance from note-12

Actions
Copy link
 #14

Updated by Eric Newberry over 9 years ago

The second solution from note-12 makes the most sense to me.

Actions
Copy link
 #15

Updated by Eric Newberry over 9 years ago

Similarly, Block::erase() requires a non-const iterator. Should it be changed to use a const iterator or be overloaded to allow a const iterator to be provided?

Actions
Copy link
 #16

Updated by Eric Newberry over 9 years ago

I tried a similar solution to note-12's second solution to get an element_iterator for use with Block::erase(). I wasn't able to get std::advance to compile, but calling boost::next with the same arguments and setting a new element_iterator to it's return value did seem to work. The linked reference recommended using either of the functions. I wasn't able to test it, but it did compile.

Actions
Copy link
 #17

Updated by Junxiao Shi over 9 years ago

  • Subject changed from Block::insert to Block::insert and Block::erase
  • Description updated (diff)

The std::advance syntax shown in note-12 is wrong. erase function with the correct syntax is:

Block::element_const_iterator
Block::erase(element_const_iterator position)
{
  resetWire();
  element_iterator pos = m_subBlocks.begin();
  std::advance(pos, std::distance(m_subBlocks.cbegin(), position));
  return m_subBlocks.erase(pos);
}
Actions
Copy link
 #18

Updated by Joao Pereira over 9 years ago

I just implemented the insert with the const iterators as advised and launched a compilation in travis:

https://travis-ci.org/joaopapereira/ndn-cxx/builds/70247481

Looks good.

I am going to implement the erase now.

Shall we keep the current versions of erase?

PS: The jenkins script is all messed up it compiles the code 4 times :s

Actions
Copy link
 #19

Updated by Junxiao Shi over 9 years ago

Answer to note-18:

No, don't keep old erase.

If ndn-cxx-breaks detects regression, I'll reconsider.

It's intentional for Jenkins to build ndn-cxx- multiple times.
Each build is using a different ./waf configure line.

Actions
Copy link
 #20

Updated by Joao Pereira over 9 years ago

  • Status changed from Feedback to Code review

Corrected the implementation of Block::insert and changed both the overloads of Block::erase to use constants in:

http://gerrit.named-data.net/#/c/2211/

Actions
Copy link
 #21

Updated by Joao Pereira over 9 years ago

The latest review in gerrit says that the functions first should be moved to the body and only then this Issue should be resolved.

Well not sure if I agree with it. As I said before I do not mind to create a new task under #1694 to solve the problem in the Block class, but it will involve creating UT and UT with the current layout of the class are not worth it for Block::erase.

But if you believe that the order should be first move to cpp and then solve this Issue, then open the issue and tell me what it is and I will solve it.

PS: I see the issue 1694 as already a patch but it is 1 year old, maybe it will not be usefull now and only changes things in name and name-component, not "block" maybe we should create a separated issue for block

Actions
Copy link
 #22

Updated by Junxiao Shi over 9 years ago

Reply to note-21:

The order is:

  1. Move function definitions from block.hpp to block.cpp. This commit refs #1694, not a separate issue.
  2. Add insert and modify erase including unit testing. This commit refs #2998.
Actions
Copy link
 #23

Updated by Joao Pereira over 9 years ago

So will we have 2 commits for #1694? Or the commit must move the functions from name and name-component?

Actions
Copy link
 #24

Updated by Junxiao Shi over 9 years ago

So will we have 2 commits for #1694? Or the commit must move the functions from name and name-component?

There is no one-to-one relation between Redmine issue and commit.

Forget about Name and name::Component.
Just upload a commit for Block with refs #1694.

Actions
Copy link
 #25

Updated by Joao Pereira over 9 years ago

Gerrit for the change in Block http://gerrit.named-data.net/2223

Actions
Copy link
 #26

Updated by Junxiao Shi over 9 years ago

What shall be the name of the define?

HAVE_VECTOR_CONST_ITERATOR
HAVE_STD_VECTOR_CONST_ITERATOR
HAVE_VECTOR_CONST_ITERATOR_INSERT_ERASE

I prefer NDN_CXX_HAVE_VECTOR_INSERT_ERASE_CONST_ITERATOR.

@Davide?

Actions
Copy link
 #27

Updated by Davide Pesavento over 9 years ago

Junxiao Shi wrote:

I prefer NDN_CXX_HAVE_VECTOR_INSERT_ERASE_CONST_ITERATOR.

@Davide?

Sounds good to me.

Actions
Copy link
 #28

Updated by Junxiao Shi over 9 years ago

  • Status changed from Code review to Closed
Actions
Copy link

Also available in: Atom PDF