Passkey Idiom

如果出于某些目的希望将某个类的构造函数设置为 private,并提供工厂函数 Make() 创建最终对象;工厂函数中通常会使用 std::make_unique() 或者 std::make_shared() 来创建由对应智能指针托管的对象。

但是因为构造函数被设置成了 private,因此这两个 make 函数内部创建对象会编译失败。

如果我们实在不希望使用 new 去构造对象,可以使用 passkey 手法规避无法编译的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Widget {
class Token {
private:
Token() {}
friend Widget;
};

public:
static std::shared_ptr<Widget> Make() {
return std::make_shared<Widget>(Token{}, GenerateId());
}

Widget(Token, int id) : id_(id) {}

private:
static int GenerateId();

int id_;
};

上面例子使用的是 make_shared()make_unique() 也是类似。

需要注意,不管 Token 类是否是 Widget 的 private 成员,Token 自身的构造函数必须满足

  • private access level
  • 显式定义(即不能使用 = default

否则会存在一个漏洞,即下面的代码能够编译通过

1
2
3
4
5
6
7
8
9
10
class Widget {
class Token {
private:
Token() = default;
friend Widget;
};
...
};

Widget w({}, 0); // Compiled.

因为 {} 被认为是 aggregate initialization,进而无视 default constructor 的访问级别。

显式定义构造函数可以避免 {} 被“理解”为 aggregate initialization。

Misc

使用 make_unique 的最大优点是可以做到异常安全;对于这样的代码

1
2
3
4
void HeavyRender(std::unique_ptr<Widget> w, Foobar&& fb);

// If an exception is thrown from `AcquireFoobar()`, the newed memory would leak
HeavyRender(std::unique_ptr<Widget>(new Widget()), AcquireFoobar());

编译器无法保证函数 AcquireFoobar() 执行的时候 new 返回的地址已经被用于构造 unique_ptr<Widget>;因此如果此时前者抛出了一个异常,动态分配的对象就泄露了。

不过通常来说,只要记住涉及 new 的语句只有一个 side-effect 就可以很大程度避免这个问题。

对于 make_shared(),除了异常安全的优势之外,内部只做一次内存分配带来的性能提升可能是大多数人使用这个函数的初衷。

Golang's Options Pattern

可以将 Golang 的 Options Pattern 视作(有副作用)函数式版的 Builder Pattern,其核心是:特定的 option-function 调用会生成对应的类型为 Option 的闭包,执行闭包会修改内部的 Options 结构。

Golang 的函数支持同一类型的不定参数,因此上面的闭包类型一致。

区别传统 Builder Pattern:

  • builder pattern 通过成员函数调用直接修改 builder 对象的属性成员;或者通过成员函数直接修改实例对象的成员

  • options pattern 是通过函数调用生成闭包,内部通过执行闭包来修改对应成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import (
"fmt"
"time"
)

// ClientOptions defines options of a client instance
type ClientOptions struct {
Timeout time.Duration
Retry int
}

type ClientOption func(*ClientOptions)

func WithTimeout(dur time.Duration) ClientOption {
return func(opts *ClientOptions) {
opts.Timeout = dur
}
}

func WithRetry(cnt int) ClientOption {
return func(opts *ClientOptions) {
opts.Retry = cnt
}
}

type Client struct {
opts *ClientOptions
}

func NewClient(opts ...ClientOption) *Client {
// can use some default values for options
cli := &Client{
opts: &ClientOptions{},
}

// apply options
for _, opt := range opts {
opt(cli.opts)
}

return cli
}

func main() {
cli := NewClient(WithTimeout(time.Second * 3))
fmt.Println(cli.opts.Timeout)
}

基于 interface 的扩展

除了生成闭包,option 函数也可以生成实现了对应接口的结构:

1
2
3
4
5
type Options struct {}

type Option interface {
apply(*Options)
}

参考 uber-golang-style 里的 functional options

Rant

根据 @vizze 的说法,golang 创建闭包的开销比直接函数调用高不少。默认 golang 行尾自动添加分号的策略导致多个函数调用换行写法难看。

另,对于 C++ 来说也可以使用 golang 这种风格。不定模板参数解决不定参数问题,同时这里需要的是一个 callable concept,lambda 或者 std::function<> 都可以做到,前者应该可以做到 zero-cost abstraction,后者会有一些额外开销。

保持 ASIO io_context 无任务时运行

ASIO 的 io_context::run() 如果发现没有 pending 的任务就会返回,对于 server 的监听线程来说这是符合常理的,因为无论如何至少有个 acceptor::async_accept() 在 pending。

但是如果想利用多核能力,那么一个常用的设计是:master 线程只负责 accept 进来的请求;将接受的 conn_sock 传递到 worker pool 里由其中一个 worker thread 处理。

每个 worker thread 其实也跑了一个 io_context,但是因为我们无法保证每个 worker 都有 pending task,所以如果不做特殊处理,io_context::run() 会直接返回,导致 worker thread 也退出,这和我们希望的背道而驰。

ASIO 中的 work guard 就是用了该解决这个问题:一个 work guard 能防止其关联的 io_context 在没有任务时退出。

1
2
[[maybe_unused]] auto work_guard = asio::make_work_guard(io_ctx_);
io_ctx_.run();
  1. work_guard 不影响 io_context::stop() 的功能和语义;如果需要结束 io_context loop,推荐的依然是使用这个方法
  2. 如果向去掉 work_guard 的影响,使用 work_guard::reset() 即可;调用后 io_context::run() 会在没有 pending task 时返回

Ref

  1. Prevent io_context::run from returning

atoi With Overflow Handled

leetcode 上有一题是让你实现一个 atoi(),但是因为函数类型是 32-bit int,所以可以直接内部转换到 64-bit int,避免需要直接处理溢出的情况。

如果要针对 int64 实现一个 atoi() 又该如何做?

我翻了一下 golang 的标准库源码,大致梳理了一下

(1) 如果对象是 int32,并且输入字符串有效数据长度小于10位,则一定不会溢出,所以可以直接处理

(2) 否则统一走 int64 处理;int64 内部会先处理掉符号位 neg,然后转成 uint64

(3) 溢出处理的核心部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Cutoff is the smallest number such that cutoff*base > maxUint64.
// Use compile-time constants for common cases.
var cutoff uint64
switch base {
case 10:
cutoff = maxUint64/10 + 1
case 16:
cutoff = maxUint64/16 + 1
default:
cutoff = maxUint64/uint64(base) + 1
}

if n >= cutoff {
// n*base overflows
return maxVal, rangeError(fnParseUint, s0)
}

maxVal := uint64(1)<<uint(bitSize) - 1

n *= uint64(base)

n1 := n + uint64(d)
if n1 < n || n1 > maxVal {
// n+v overflows
return maxVal, rangeError(fnParseUint, s0)
}
n = n1

(4) cutoff 是防止溢出的第一重栅栏

对于 uint64 来说

1
2
cutoff     = 1844674407370955162
UINT64_MAX = 18446744073709551615

parse 的时候如果当前数已经 >= cutoff 那么后面的数字不管是几都绝对溢出。

但是即使 cutoff 这里满足,加上后一位数字之后仍然可能会溢出,所以这里要做溢出处理。

因为类型是 uint64,所以只可能发生上溢出,数值会 wrap-around,所以用 n + uint64(d) < n 来判断

n1 > maxVal 是用来处理 int32 的时候的情况(函数的输入类型已经被转成了 64-bit)

(5) 如果输入类型本身就是无符号,那么到这里就结束了。

如果是有符号,需要判断最终结果是否落在范围里,另外要注意补码体系下两端的值是不对称的。

Allow Connections From LAN for Trojan-qt5

因为众所周知的原因,机场的服务商把协议从 SS 切换到了 Trojan。但是之前的 SS windows 客户端只支持 SS 协议,所以切换后只能换 Trojan-qt5 作为客户端。

但是这个客户端做的实在不怎么样,作者似乎是在原来的 ss-qt5 的基础上做的修改,集成了 libtrojan;以至于之前 SS-Windows 用的好好的 Allow Connections From LAN 功能到这里没法用了。

更改 socks5 监听地址为 INETADDR_ANY 确实能让局域网内的其他主机链接 socks5 代理,但是 HTTP 代理就神奇的不能用了…

试验了一番结果发现要使 HTTP 代理能够正常工作,socks5 代理监听地址必须是 localhost… 🤪

因为我的 Linux 开发环境是搭建在虚拟机里并通过 X11 转发到宿主机的,所以不能使用来自 LAN 的连接会严重影响开发效率。

解决方案

  1. 自己写一个 tcp socket 运行在宿主机上,并监听 INETADDR_ANY,Mint 把转发器作为代理
  2. 用 netcat 实现
  3. 找其他替代品

先考虑 (1),然而发现 netcat 可以实现单次连接转发,但是后续的同一个连接的通信会直接 hang 住,可能哪里姿势不对

再考虑 (2),发现可以用 socat。

WSL 里通过 apt 安装,然后

1
socat tcp-l:10086,fork,reuseaddr tcp:127.0.0.1:10081

Mint 把宿主机的 10086 端口作为代理端口

嗯,发现工作非常顺畅…

这样就不用考虑 (3) 了,不然哪怕用 ASIO 也差不多要百来行代码。

Randomly Generate Base62 for URL Shortening

Last week I wrote a post about how to design an URL shortening service, like TinyURL, and came up with 2 strategies to encode an URL, and one of which is to randomly generate base64 sequence.

Although I knew it works, in theory, I was not so confident deep in mind.

So I wrote some code and made a simulation for generating 10^8 6-digit and 8-digit base62 sequences, respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct Alphabet {
std::array<char, 62> arr;
constexpr Alphabet()
: arr()
{
for (auto ch = 'a'; ch <= 'z'; ++ch) {
arr[ch - 'a'] = ch;
}

for (auto ch = 'A'; ch <= 'Z'; ++ch) {
arr[ch - 'A' + 26] = ch;
}

for (auto ch = '0'; ch <= '9'; ++ch) {
arr[ch - '0' + 52] = ch;
}
}

constexpr operator std::array<char, 62>()
{
return arr;
}
};

constexpr std::array<char, 62> kAlphabet = Alphabet();

int main()
{
std::default_random_engine engine(std::random_device{}());
std::uniform_int_distribution<> dist(0, 61);

std::unordered_set<std::string> keys;

constexpr size_t kNum = 100000000; // 10^8

for (auto i = 0; i < kNum; ++i) {
std::string key;
key.reserve(8);
for (auto k = 0; k < 8; ++k) {
key.append(1, kAlphabet[dist(engine)]);
}

keys.insert(std::move(key));
}

std::cout << "keys-size=" << keys.size() << "; total=" << kNum << "\n"
<< "unique ratio=" << static_cast<double>(keys.size()) / kNum;

return 0;
}

The result shows

  • for generating 10^8 6-digit sequences, unique ratio of one-time generation is 0.9991
  • for the 8-digit case, the unique ratio of one-time generation is high as 0.99999975

Even for 6-digit sequences, probability of two consecutive repeated generation is only 0.000001; and we can generate at least 1 million keys in less than 1 second.

Therefore, this strategy is indeed feasible in practice.

Notwithstanding, there is still one concernn we need to pay: the success ratio of one-time generation may drop dramatically after years, when number of generated combinations exceeds a threshould, like half of the entire combination space.

Unfortunately, I don’t know what this threshould is in probability thoery; but if that day came, we can extend our sample space by extend length of base62 sequence, XD.

How To Design a URL Shortening Service

1. Encoding Actual URL

The path part, which we would call it key, of an encoded URL can consist of 6 ~ 8 digits in base62, up to desired uniqueness rate.

Randomly Generated

We can randomly generate those digits each within the range [0, 61].

Then we must check if the generated key is unique by consulting our key storage.

Aside: this checking process can be optimized with data structures like bloom-filter, provided we have to deal hundres of million records.

If we are unlucky, we may have a key collision; in this case, just re-generate another key until its unique.

To make encoding more efficient, we can have a standalone Key Generation Service(KGS) that generates those random key beforehand, and store them.