Project

General

Profile

Actions
Copy link

Feature #2998

closed

Block::insert and Block::erase

Added by Junxiao Shi almost 10 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 almost 10 years ago

Actions
Copy link
 #2

Updated by Joao Pereira almost 10 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 almost 10 years ago

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

Actions
Copy link
 #4

Updated by Joao Pereira almost 10 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 almost 10 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 almost 10 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 almost 10 years ago

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

Updated by Joao Pereira almost 10 years ago

Added UT

Actions
Copy link
 #9

Updated by Joao Pereira almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 years ago

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

Actions
Copy link
 #14

Updated by Eric Newberry almost 10 years ago

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

Actions
Copy link
 #15

Updated by Eric Newberry almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 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 almost 10 years ago

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

Actions
Copy link
 #26

Updated by Junxiao Shi almost 10 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