利用 Boost Unit Test Framework,可以方便的進行單元測試。 而在 UVa Online Judge 的練習中,我們也可以導入 Boost Unit Test Framework 來對我們寫的 function 進行測試。 不過 UVa Online Judge 的編譯環境是不支援 Boost 的,但在編譯時,它會給一個特別的編譯參數 -DONLINE_JUDGE。 所以我們可以利用Uva 這個特有的編譯參數,在導入 Boost Unit Test Framework 時,又不會發生Compiler Error.

單元測試時:

$ g++ 530.cpp -lboost_unit_test_framework
$ ./a.out 
Running 2 test cases...

*** No errors detected

以測資做為輸入的測試:

$ g++ 530.cpp -DONLINE_JUDGE
$ ./a.out <input.txt
6
252
13983816

程式碼:

//============================================================================
// Name        : 530.cpp
// Author      :
// Version     :
// Copyright   : copyright notice
//============================================================================

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

#ifndef ONLINE_JUDGE
#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE acm
#include <boost/test/unit_test.hpp>
#endif

long long combinations(long long int n, long long int k) {
	long long int ans = 1;
	if (k > n - k) {
		k = n - k;
	}

	for (long long int idx = 1; idx <= k; idx++) {
		ans *= (n - idx + 1);
		ans = ans / idx;
	}
	return ans;
}

#ifdef ONLINE_JUDGE
int main() {
	long long int n, k;
	while (cin >> n >> k) {
		if (n == 0 && k == 0) {
			break;
		}

		cout << combinations(n, k) << endl;
	}
	return 0;
}
#else
BOOST_AUTO_TEST_SUITE(test)

BOOST_AUTO_TEST_CASE(testSmall) {
	BOOST_CHECK(combinations(0, 0) == 1);
	BOOST_CHECK(combinations(2, 2) == 1);
	BOOST_CHECK(combinations(2, 1) == 2);
	BOOST_CHECK(combinations(4, 2) == 6);
	BOOST_CHECK(combinations(6, 3) == 20);
	BOOST_CHECK(combinations(10, 5) == 252);
}

BOOST_AUTO_TEST_CASE(testLarge) {
	BOOST_CHECK(combinations(49, 6) == 13983816);
}

BOOST_AUTO_TEST_SUITE_END()
#endif

RIP, Google Reader
2013-03-14

今天 Google 宣布了 Google Reader 將於 2013/7/1 結束運作。

另一個 RSS 訂閱服務 Feedly 則馬上做出了回應, Feedly 這項服務提供 Google Reader 使用者連結自己所訂閱的 RSS, 並以 Feedly 較為活潑清爽的版面來進行閱讀。 於 Feedly 上連結 Google Reader 的使用者,將可以在 2013/7/1 後,無痛延續閱讀自己訂閱的 RSS 來源.

就我先前的經驗來說,Feedly是個有趣的閱讀介面, 雖然我比較喜歡簡單的閱讀介面,所以還是維持使用 Google Reader, 不過既然現在 Feedly 提供這樣的服務(事實上提供Google Reader的連結訂閱,一直是Feedly的主力服務), 我想就開始使用看看吧。

有興趣的人可以到: Feedly

Ref:
1. A second spring of cleaning
2. Powering Down Google Reader
3. Transitioning from Google Reader to feedly

今天讀到的文章 Using Valgrind to debug memory leaks {% codeblock lang:c %} #include #include #include

char *lower;

char *to_lower (const char *str) { char *l = strdup (str); char *c;

for (c = l; *c; c++) {
    if (isupper(*c))
        *c = tolower(*c);
}

return l;

}

int main (int argc, char *argv[]) { lower = to_lower (argv[1]);

while (*lower)
    putchar (*(lower++));
puts ("");

return 0;

} {% endcodeblock %}

輸出訊息 {% codeblock %} ==28578== 5 bytes in 1 blocks are possibly lost in loss record 1 of 1 ==28578== at 0x4025D2E: malloc (vg_replace_malloc.c:207) ==28578== by 0x40D805F: strdup (in /lib/tls/i686/cmov/libc-2.8.90.so) ==28578== by 0x8048504: to_lower (test2.c:9) ==28578== by 0x804857F: main (test2.c:22) {% endcodeblock %}

This time memory is possibly lost. Why it’s not sure? Because at the program exit time we didn’t completely lost the pointer to the allocated memory, we’ve only advanced it to print the lower string in a funny way. It’s theoretically possible that we have a variable, a counter that tells us how much we’ve advanced, so we could compute the pointer to the memory to free it.

文章還提到了 Valgrind In practice. 很值得一看

At the beginning of using Valgrind to debug my programs I used to think this way: It’s just an automatic, dumb tool that tracks memory allocations and can be wrong. I looked at the code and there can be no memory leak at this point, it’s one of the cases when Valgrind is wrong.. But I was wrong! After years of using it I can see that 99,9% of it’s messages are right but it’s often hard to see it in the code.

One real world case was when I was writing a multi-threaded program that used libmysqlclient library and valgrind showed memory leaks in mysql_real_connect()/mysql_init(). It’s clear from documentation that the memory allocated by the library when using those functions should be freed by mysql_close(). From the code it was clear that I do it properly: every created connection was closed. I even added a counter to the places when I create connection and destroy it and saw all connections were destroyed. I started to think that there is a memory leak in the libmysqlclient_r library (a thread-safe version) but when I separated the code (wrote a simple program that allocates conenctions and free them) Valgrind showed no errors. So there are no leaks in the library. If I had less believe in Valgrind I would give up at this moment, but I knew it’s right. As I found out there is a special requirement by libmysqlclient_r, I just didn’t read the documentation. If you are creating MYSQL objects in different threads the library automatically allocates per-thread global data, but to free them you must use mysql_thread_end(). It’s not done

Octopress 的第一篇文章,簡單介紹 Valgrind - 檢查程式記憶體的小工具

前陣子我對 project 進行 Debug 其中有一些 runtime error, 包含 memory leak

我使用 Valgrind 來檢查 Memory Leak

小範例,由 Valgrind 找出 test.cpp 第8行的 Bug ( Invalid read )

{% codeblock lang:cpp %} #include #include using namespace std ;

int main() { vector array(1024); cout << array[1024] << endl ; return 0; } {% endcodeblock %}

$g++ -g test.cpp $valgrind ./a.out

輸出訊息 {% codeblock %} ==9247== Memcheck, a memory error detector ==9247== Copyright © 2002-2011, and GNU GPL’d, by Julian Seward et al. ==9247== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info ==9247== Command: ./a.out ==9247== ==9247== Invalid read of size 8 ==9247== at 0x80487C4: main (test.cpp:8) ==9247== Address 0x4336028 is 0 bytes after a block of size 8,192 alloc’d ==9247== at 0x402B9B4: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) ==9247== by 0x8048BD1: __gnu_cxx::new_allocator::allocate(unsigned int, void const*) (new_allocator.h:92) ==9247== by 0x8048B1D: std::_Vector_base >::_M_allocate(unsigned int) (in /home/stanleyhsiao/a.out) ==9247== by 0x80489BC: std::_Vector_base >::_Vector_base(unsigned int, std::allocator const&) (stl_vector.h:123) ==9247== by 0x80488D1: std::vector >::vector(unsigned int, double const&, std::allocator const&) (stl_vector.h:265) ==9247== by 0x80487A3: main (test.cpp:7) ==9247== 0 ==9247== ==9247== HEAP SUMMARY: ==9247== in use at exit: 0 bytes in 0 blocks ==9247== total heap usage: 1 allocs, 1 frees, 8,192 bytes allocated ==9247== ==9247== All heap blocks were freed – no leaks are possible ==9247== ==9247== For counts of detected and suppressed errors, rerun with: -v ==9247== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) {% endcodeblock %}