__rw_new_capacity() doesn't control map, set

• Key: STDCXX-995
• Type: Bug
• Status: Open
• Priority: Minor
• Assignee: Unassigned
• Reporter: Martin Sebor
• Component/s: 23. Containers
• Affects Version/s: 4.1.2, 4.1.3, 4.1.4, 4.2.0, 4.2.1
• Fix Version/s: 4.2.2

Description

-------- Original Message --------
Subject: Re: Controlling allocation policy of STL set.
Date: Thu, 17 Jul 2008 17:18:17 -0700 (PDT)
From: Dennis Handly <dhandly AT cup DOT hp DOT com>
To: sebor AT roguewave DOT com
CC: boris.gubenko AT hp DOT com, dhandly AT cup DOT hp DOT com, premanand.rao AT hp DOT com

We had this question from a user recently. I was able to reverse engineer
how to do this with map/set.

Is this level of difficulty known?

Here is a link where we mention the info about __rw_new_capacity:
http://docs.hp.com/en/10946/libs.htm#container_alloc

I would be nice if we could just use the private typedef
std::map<K,V>::__rep_type.

Then we could just use:

#include <set>

typedef std::set<key_type> BlagPset;
typedef BlagPset::__rep_type BlagPtree;
// forward
template<>
inline size_t __rw::__rw_new_capacity<BlagPtree>(size_t size, BlagPtree const*);

Do you see any issues with making __rep_type public?

(Your Apache code still has it private but as _C_repT.)

===========================================================================
Do you know why the following code fragment does not work for me?
i.e it controls the vector's allocation policy as I expect, but not the
set's. I can believe there is some stupid mistake in there, but I have been
staring at it for a while now...

#include <stdio.h>
#include <vector>
#include <set>
class Blag { int a; };
std::vector<Blag*> bvec;
std::set<Blag*> bset;

template<>
inline size_t __rw::__rw_new_capacity<std::vector<Blag*> >(size_t size,
                                      std::vector<Blag*> const*) {
    if (size == 0) {
        fprintf(stderr, "Initial size will be 8 for vector\n");
        return 8;
    } else
        return size * 2;
}

template<>
inline size_t __rw::__rw_new_capacity<std::set<Blag*> >(size_t size,
                                       std::set<Blag*> const*) {
    if (size == 0) {
        fprintf(stderr, "Initial size will be 8 for set\n");
        return 8;
    } else
        return size * 2;
}
int main() {
    bset.insert(0);
    bvec.push_back(0);
}

===========================================================================
>From: Dennis Handly <dhandly AT cup DOT hp DOT com>

>Do you know why the following code fragment does not work for me?

Storage isn't allocated for the set but by the __rbtree.

>I can believe there is some stupid mistake in there

It isn't easy, you have to find the __rw_new_capacity call.

#include <stdio.h>
#include <vector>

class Blag { int a; };
typedef Blag* key_type;

// start kludge
#include <functional>
namespace __rw {
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree;
template <class _TypeT, class _TypeU>
struct __ident;
} // namespace __rw
typedef __rw::__rb_tree<key_type, key_type, __rw::__ident<key_type, key_type>,
                        std::less<key_type>, std::allocator<key_type> >
                        BlagPtree;
// forward
template<>
inline size_t __rw::__rw_new_capacity<BlagPtree>(size_t size, BlagPtree const*);
// end kludge

#include <set>

typedef std::vector<key_type> BlagPvec;
typedef std::set<key_type> BlagPset;
BlagPvec bvec;
BlagPset bset;

template<>
inline size_t __rw::__rw_new_capacity<BlagPvec>(size_t size, BlagPvec const*) {
    if (size == 0) {
        fprintf(stderr, "Initial size will be 8 for vector\n");
        return 8;
    } else
        return size * 2;
}
// useless
template<>
inline size_t __rw::__rw_new_capacity<BlagPset>(size_t size, BlagPset const*) {
    if (size == 0) {
        fprintf(stderr, "Initial size will be 8 for set\n");
        return 8;
    } else
        return size * 2;
}
template<>
inline size_t __rw::__rw_new_capacity<BlagPtree>(size_t size, BlagPtree const*){
    if (size == 0) {
        fprintf(stderr, "Initial size will be 8 for tree\n");
        return 8;
    } else
        return size * 2;
}

int main() {
    bset.insert(0);
    bvec.push_back(0);
}

Comments

[Farid Zaripov]

What about just passing the particular container type to __rb_tree<> class using additional template parameter?

The proposed patch is attached.

[Martin Sebor]

It's an interesting idea but I have a couple of concerns with the proposed patch:

1. it's binary incompatible
2. it seems a bit heavy-weight

By heavy-weight I mean that this type of a circular dependency (a template using another with the first as an argument to the second) has been problematic in the past (it tends to cause issues during instantiation when type completeness is required). Passing the type of the container (e.g., std::map) as _Owner to the implementation template (__rw::__rb_tree) as an entire new parameter also seems to obviates the need for several of the other parameters (e.g., _Key, _Val, and _Alloc) as they could be extracted from _Owner. That said, I think this extraction would further increase the coupling between the templates and exacerbate the instantiation problem.