3. Kritik für URL Encoder erbeten

Kritik für URL Encoder erbeten

  • ?

    TNA schrieb:

    Die String Implementation von libcxx scheint das auch nicht zu machen wenn ich das richtig sehe: http://llvm.org/svn/llvm-project/libcxx/trunk/include/string

    Wo siehst du das? Ich sehe was anderes

    // in: basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)

    if (__sz == __cap)
    {
        __grow_by(__cap, 1, __sz, __sz, 0);
        __is_short = !__is_long();
    }

    Heisst: "Wenn neue size()==capacity(), mach capacity() += capacity()".

    stringstream macht das genau gleich, nur hat der einen enormen Overhead pro operator<<.

    0
  • T

    encoder schrieb:

    Wo siehst du das? Ich sehe was anderes

    Ups, ich hatte nicht berücksichtigt, dass du einen char anhängst und keinen String. Wäre es aber nicht trotzdem sinnvoll, ein

    escaped.reserve(value.size());

    zu machen?

    0
  • ?

    Sorry, hab mich verguckt, es wird nur um 1 vergrössert. Scheint so, als wäre std::string da noch refcounted, also gar nicht mehr C++11-konform.

    Dann nimm solange halt vector<char>.

    0
  • T

    Soweit ich weiß wurde libcxx extra für c++11 designed und der string ist nicht refcounted. Mir ist allerdings noch die Idee gekommen, einfach am Anfang genug Speicher mit reserve() zu reservieren und nachher ein shrink_to_fit() zu machen. Würde da etwas gegen sprechen?

    0
  • S

    @encoder:

    static std::array<bool, 256> unreserved;

  if( !unreserved['A'] )
    for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") 
      unreserved[c] = true;

    ?

    infach am Anfang genug Speicher mit reserve() zu reservieren und nachher ein shrink_to_fit() zu machen. Würde da etwas gegen sprechen?

    Nein, genau so sind diese Funktionen gedacht, damit würde das hin- und her kopieren eliminiert.

    0
  • T
     

    std::string url_encode(const std::string &value) { 
  static std::array<bool, 256> unreserved = []{ 
    std::array<bool, 256> a{{}}; 
    for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") 
      a[c] = true; 
    return a; 
  }(); 
  std::string escaped;
  escaped.reserve(value.size()*3);
  for (unsigned char c : value) { 
    if (unreserved[c]) 
      escaped += c; 
    else { 
      escaped += '%'; 
      escaped += "0123456789ABCDEF"[(c/0xF)&0xF]; 
      escaped += "0123456789ABCDEF"[(c&0xF)]; 
    } 
  }
  escaped.shrink_to_fit();
  return escaped; 
}
    0
  • T
     

    #include <string>
#include <array>
#include <bitset>
#include <cassert>

std::string url_encode(const std::string &value) {
  static std::array<bool, 256> unreserved = []{
    std::array<bool, 256> a{{}};
    for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~")
      a[c] = true;
    return a;
  }();
  std::string escaped;
  escaped.reserve(value.size()*3);
  for (unsigned char c : value) {
    if (unreserved[c])
      escaped += c;
    else {
      escaped += '%';
      escaped += "0123456789ABCDEF"[(c/16)&0xF]; //hier stand 15 statt 16
      escaped += "0123456789ABCDEF"[(c&0xF)];
    }
  }
  escaped.shrink_to_fit();
  return escaped;
}

namespace generalized
{
	bool needs_escape(char c)
	{
		static std::bitset<256> const flags = []()
		{
			std::bitset<256> result;
			for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~")
			{
				result.set(c);
			}
			return result;
		}();
		return ! flags.test(static_cast<unsigned char>(c));
	}

	template <class OutputIterator>
	OutputIterator escape(char c, OutputIterator dest)
	{
		*dest++ = '%';
		unsigned const uc = static_cast<unsigned char>(c);
		char const * const digits = "0123456789ABCDEF";
		*dest++ = digits[uc / 16];
		*dest++ = digits[uc & 15];
		return dest;
	}

	template <class InputIterator, class OutputIterator>
	OutputIterator
	url_encode(InputIterator source_begin,
			   InputIterator source_end,
			   OutputIterator dest)
	{
		for (; source_begin != source_end; ++source_begin)
		{
			char const c = *source_begin;
			if (needs_escape(c))
			{
				dest = escape(c, dest);
			}
			else
			{
				*dest++ = c;
			}
		}
		return dest;
	}

	template <class InputIterator>
	std::size_t size_when_encoded(InputIterator begin, InputIterator end)
	{
		std::size_t size = 0;
		for (; begin != end; ++begin)
		{
			if (needs_escape(*begin))
			{
				size += 3;
			}
			else
			{
				size += 1;
			}
		}
		return size;
	}

	///Fordert zuerst die mindestens benötigte Menge Speicher an und vergrößert
	///dann bei Bedarf mit string::push_back. Die Kapazität des Ergebnisses ist
	///möglicherweise höher als die Länge.
	std::string url_encode_to_string(std::string const &value)
	{
		std::string encoded;
		encoded.reserve(value.size());
		url_encode(begin(value), end(value), std::back_inserter(encoded));
		return encoded;
	}

	///Berechnet die Länge des Ergebnisses und fordert genau so viel Speicher an.
	///Es gibt maximal eine dynamische Speicheranforderung.
	///Die Kapazität des Ergebnisses entspricht in der Regel der Länge.
	std::string url_encode_to_string_fit(std::string const &value)
	{
		std::string encoded;
		encoded.resize(size_when_encoded(begin(value), end(value)));
		url_encode(begin(value), end(value), begin(encoded));
		return encoded;
	}
}

template <class UrlEncode>
void test_url_encode(UrlEncode const &encode)
{
	assert(encode("") == "");
	assert(encode("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") ==
	              "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~");
	assert(encode(" \xff") == "%20%FF");
}

int main()
{
	test_url_encode(url_encode);
	test_url_encode(generalized::url_encode_to_string);
	test_url_encode(generalized::url_encode_to_string_fit);
}
    0

  • encoder schrieb:

    Sorry, hab mich verguckt, es wird nur um 1 vergrössert.

    Ich glaube du hast dich doppelt verguckt, so dass die ursprüngliche Aussage wieder stimmt:

    template <class _CharT, class _Traits, class _Allocator>
void
basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                                     size_type __n_copy,  size_type __n_del,     size_type __n_add)
{
    size_type __ms = max_size();
    if (__delta_cap > __ms - __old_cap - 1)
        this->__throw_length_error();
    pointer __old_p = __get_pointer();
    size_type __cap = __old_cap < __ms / 2 - __alignment ?             // vvvvvvvvvvvvv -- HIER
                          __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                          __ms - 1;
    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
    __invalidate_all_iterators();
    if (__n_copy != 0)
        traits_type::copy(_VSTD::__to_raw_pointer(__p),
                          _VSTD::__to_raw_pointer(__old_p), __n_copy);
    size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
    if (__sec_cp_sz != 0)
        traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
                          _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del,
                          __sec_cp_sz);
    if (__old_cap+1 != __min_cap)
        __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
    __set_long_pointer(__p);
    __set_long_cap(__cap+1);
}

    Heisst: wenn __old_cap noch verdoppelt werden kann, dann wird immer mindestens verdoppelt. Und nur falls __delta_cap > __old_cap spielt __delta_cap eine Rolle -- in dem Fall wird dann mehr als verdoppelt.

    => Fragwürdiger name. __min_grow_amount wäre mMn. ein besserer Name. Hätte zumindest bei mir gleich den Verdacht geweckt dass vermutlich oft mehr "gegrowd" wird als man da übergibt.

    encoder schrieb:

    Scheint so, als wäre std::string da noch refcounted, also gar nicht mehr C++11-konform.

    Wo scheint das so 😕
    Ich seh' da nur ne Small-String-Optimization.

    0
  • T

    Ich habe noch eine Frage zum Ausdruck

    (c/0xF)&0xF

    c/0xF ist doch ein "trickreicher" Rechtsshift oder? Warum ist das besser als x >> 4 ? Wozu muss man danach noch maskieren? Sollten in den ersten 4 Bits nicht ohnehin Nullen drin stehen?

    0
  • S

    c/0xF ist doch ein "trickreicher" Rechtsshift oder?

    Nein.
    http://ideone.com/YuHfoS
    Also ich sehe nicht das selbe Bitmuster nur ein wenig weiter rechts....

    0
  • T

    TNA schrieb:

    Ich habe noch eine Frage zum Ausdruck

    (c/0xF)&0xF

    c/0xF ist doch ein "trickreicher" Rechtsshift oder? Warum ist das besser als x >> 4 ? Wozu muss man danach noch maskieren? Sollten in den ersten 4 Bits nicht ohnehin Nullen drin stehen?

    15 ist einfach die falsche Zahl. Es müsste 16 heißen, damit die Division einen Rechts-Shift um 4 bewirkt.
    Das Maskieren ist in der Tat überflüssig, wenn ein char genau 8 Bits hat oder die Werte unter 256 liegen.

    0
  • T

    TyRoXx schrieb:

    15 ist einfach die falsche Zahl. Es müsste 16 heißen, damit die Division einen Rechts-Shift um 4 bewirkt.

    Hätte mir auch auffallen sollen, dass das keine Zweierpotenz ist. Genau darum würde ich x >> 4 bevorzugen, weil man da sofort sieht was gemeint ist und der Compiler wahrscheinlich ohnehin den schnellstmöglichen Code generiert.

    0
Anmelden zum Antworten