C语言宏的特殊用法和几个坑

总结一下C语言中宏的一些特殊用法和几个容易踩的坑。由于本文主要参考GCC文档,某些细节(如宏参数中的空格是否处理之类)在别的编译器可能有细微差别,请参考相应文档。

宏基础

宏仅仅是在C预处理阶段的一种文本替换工具,编译完之后对二进制代码不可见。基本用法如下:

1. 标示符别名

#define BUFFER_SIZE 1024

预处理阶段,foo = (char *) malloc (BUFFER_SIZE);会被替换成foo = (char *) malloc (1024);

宏体换行需要在行末加反斜杠\

#define NUMBERS 1, \
                2, \
                3

预处理阶段int x[] = { NUMBERS };会被扩展成int x[] = { 1, 2, 3 };

2. 宏函数

宏名之后带括号的宏被认为是宏函数。用法和普通函数一样,只不过在预处理阶段,宏函数会被展开。优点是没有普通函数保存寄存器和参数传递的开销,展开后的代码有利于CPU cache的利用和指令预测,速度快。缺点是可执行代码体积大。

#define min(X, Y)  ((X) < (Y) ? (X) : (Y))

y = min(1, 2);会被扩展成y = ((1) < (2) ? (1) : (2));


宏特殊用法

1. 字符串化(Stringification)

在宏体中,如果宏参数前加个#,那么在宏体扩展的时候,宏参数会被扩展成字符串的形式。如:

#define WARN_IF(EXP) \
     do { if (EXP) \
             fprintf (stderr, "Warning: " #EXP "\n"); } \
     while (0)

WARN_IF (x == 0);会被扩展成:

do { if (x == 0)
    fprintf (stderr, "Warning: " "x == 0" "\n"); }
while (0);

这种用法可以用在assert中,如果断言失败,可以将失败的语句输出到反馈信息中

2. 连接(Concatenation)

在宏体中,如果宏体所在标示符中有##,那么在宏体扩展的时候,宏参数会被直接替换到标示符中。如:

#define COMMAND(NAME)  { #NAME, NAME ## _command }

struct command
{
    char *name;
    void (*function) (void);
};

在宏扩展的时候

struct command commands[] =
{
    COMMAND (quit),
    COMMAND (help),
    ...
};

会被扩展成:

struct command commands[] =
{
    { "quit", quit_command },
    { "help", help_command },
    ...
};

这样就节省了大量时间,提高效率。


几个坑

1. 语法问题

由于是纯文本替换,C预处理器不对宏体做任何语法检查,像缺个括号、少个分号神马的预处理器是不管的。这里要格外小心,由此可能引出各种奇葩的问题,一下还很难找到根源。

2. 算符优先级问题

不仅宏体是纯文本替换,宏参数也是纯文本替换。有以下一段简单的宏,实现乘法:

#define MULTIPLY(x, y) x * y

MULTIPLY(1, 2)没问题,会正常展开成1 * 2。有问题的是这种表达式MULTIPLY(1+2, 3),展开后成了1+2 * 3,显然优先级错了。

在宏体中,给引用的参数加个括号就能避免这问题。

#define MULTIPLY(x, y) (x) * (y)

MULTIPLY(1+2, 3)就会被展开成(1+2) * (3),优先级正常了。

其实这个问题和下面要说到的某些问题都属于由于纯文本替换而导致的语义破坏问题,要格外小心。

3. 分号吞噬问题

有如下宏定义:

#define SKIP_SPACES(p, limit)  \
     { char *lim = (limit);         \
       while (p < lim) {            \
         if (*p++ != ' ') {         \
           p--; break; }}}

假设有如下一段代码:

if (*p != 0)
   SKIP_SPACES (p, lim);
else ...

一编译,GCC报error: ‘else’ without a previous ‘if’。原来这个看似是一个函数的宏被展开后是一段大括号括起来的代码块,加上分号之后这个if逻辑块就结束了,所以编译器发现这个else没有对应的if。

这个问题一般用do ... while(0)的形式来解决:

#define SKIP_SPACES(p, limit)     \
     do { char *lim = (limit);         \
          while (p < lim) {            \
            if (*p++ != ' ') {         \
              p--; break; }}}          \
     while (0)

展开后就成了

if (*p != 0)
    do ... while(0);
else ...

这样就消除了分号吞噬问题。

这个技巧在Linux内核源码里很常见,比如这个置位宏#define SET_REG_BIT(reg, bit) do { (reg |= (1 << (bit))); } while (0)(位于arch/mips/include/asm/mach-pnx833x/gpio.h)

4. 宏参数重复调用

有如下宏定义:

#define min(X, Y)  ((X) < (Y) ? (X) : (Y))

当有如下调用时next = min (x + y, foo (z));,宏体被展开成next = ((x + y) < (foo (z)) ? (x + y) : (foo (z)));,可以看到,foo(z)被重复调用了两次,做了重复计算。更严重的是,如果foo是不可重入的(foo内修改了全局或静态变量),程序会产生逻辑错误。

所以,尽量不要在宏参数中传入函数调用。

5. 对自身的递归引用

有如下宏定义:

#define foo (4 + foo)

按前面的理解,(4 + foo)会展开成(4 + (4 + foo)),然后一直展开下去,直至内存耗尽。但是,预处理器采取的策略是只展开一次。也就是说,foo只会展开成(4 + foo),而展开之后foo的含义就要根据上下文来确定了。

对于以下的交叉引用,宏体也只会展开一次。

#define x (4 + y)
#define y (2 * x)

x展开成(4 + y) -> (4 + (2 * x))y展开成(2 * x) -> (2 * (4 + y))

注意,这是极不推荐的写法,程序可读性极差。

6. 宏参数预处理

宏参数中若包含另外的宏,那么宏参数在被代入到宏体之前会做一次完全的展开,除非宏体中含有###

有如下宏定义:

#define AFTERX(x) X_ ## x
#define XAFTERX(x) AFTERX(x)
#define TABLESIZE 1024
#define BUFSIZE TABLESIZE
  • AFTERX(BUFSIZE)会被展开成X_BUFSIZE。因为宏体中含有##,宏参数直接代入宏体。
  • XAFTERX(BUFSIZE)会被展开成X_1024。因为XAFTERX(x)的宏体是AFTERX(x),并没有###,所以BUFSIZE在代入前会被完全展开成1024,然后才代入宏体,变成X_1024

-EOF-


参考资料:

http://gcc.gnu.org/onlinedocs/cpp/Macros.html

Python descriptor

一次偶然发现,Python的对象竟然可以在运行期动态添加类定义时没有的属性,这又颠覆了我对Python OO机制的理解。Google了一把,顺着__dict__属性一路找到descriptor,揭开了隐藏在Python对象之后的内幕。

本文主要记录Python的descriptor机制,以及其在Python对象的属性、方法绑定上的作用。

先从本文的始作俑者,运行期动态添加对象属性开始讲起。

class A:
    def __init__(self):
        self.value = 'value'
    def f(self):
        print('function f')
a = A()
a.attr = 1
print(a.attr)

以上代码奇迹般的没有报错,而且还输出了1。这肯定会让写过C++/Java代码的童鞋表示吃惊,Python变量类型动态也就不稀奇了,对象属性还能动态添加的?Python到底在背后做了什么?

神奇的__dict__

a.attr = 1前后分别加上一行print(a.__dict__)就会得到如下结果:

{'value': 'value'}  
1  
{'value': 'value', 'attr': 1} 

显而易见,我们在运行期定义的属性和类定义时定义的属性都被放在了__dict__里。

到这里有人可能就有疑问了,Python里的一切不都是对象麽?为什么成员函数__init__f不在这个字典里?

看看A.__dict__里有什么就明白了:

{'__dict__': <attribute '__dict__' of 'A' objects>,
 '__doc__': None,
 '__init__': <function __main__.__init__>,
 '__module__': '__main__',
 '__weakref__': <attribute '__weakref__' of 'A' objects>,
 'f': <function __main__.f>}

这时才恍然大悟,如果成员变量看做是对象的属性,那么成员函数就应该看成是类的属性,被全部对象共享嘛。

更精确地讲,以object.attribute访问一个对象的属性时,属性的搜索顺序为:

  1. 对象自身,object.__dict__
  2. 对象类型,object.__class__.__dict__
  3. 对象类型的基类,object.__class__.__bases__中的所有__dict__。注意,当多重继承的情况下有菱形继承的时候,Python会根据MRO确定的顺序进行搜索。关于MRO(Method Resolution Order)是什么有时间专门写一篇文章总结一下。

当以上三个步骤都没有找到要访问的属性的时候Python就只能抛出AttributeError异常了。

Descriptor是什么

讲了这么多,貌似跟descriptor半毛钱关系没有嘛。别急,接着往下看。

class RevealAccess(object):
    def __init__(self, initval=None, name='var'):
        self.val = initval
        self.name = name

    def __get__(self, obj, objtype):
        print 'Retrieving', self.name
        return self.val

    def __set__(self, obj, val):
        print 'Updating' , self.name
        self.val = val

来测试一下这个类

>>> class MyClass(object):
    x = RevealAccess(10, 'var "x"')
    y = 5

>>> m = MyClass()
>>> m.x
Retrieving var "x"
10
>>> m.x = 20
Updating var "x"
>>> m.x
Retrieving var "x"
20
>>> m.y
5

这个RevealAccess的对象就是一个descriptor,其作用就是在存取变量的时候做了一个hook。访问属性m.x就是调用__get__方法,设置属性值就是调用__set__方法。还可以有一个__delete__方法,在del m.x时被调用。

只要一个类定义了以上三种方法,其对象就是一个descriptor。我们把同时定义__get____set__方法的descriptor叫做data descriptor,把只定义__get__方法的叫non-data descriptor

Method binding

有了以上两个概念,我们就能讨论Python的方法绑定了。

还记得讨论__dict__时的成员函数f吗?按照我们的推测,A.__dict__['f']应该和a.f是一个东西。但是!!!

>>> A.__dict__['f']
<function __main__.f>
>>> a.f
<bound method A.f of <__main__.A object at 0x7f9d69cc5950>>

这两个显然不是一个东西,一个是function,一个是bound method。这是什么情况?淡定,看下面

>>> A.__dict__['f'].__get__(a, A)
<bound method A.f of <__main__.A object at 0x7f9d69cc5950>>
>>> a.f
<bound method A.f of <__main__.A object at 0x7f9d69cc5950>>

这下放心了吧:D

其实,类的成员函数就是一个descriptor,在实例化对象a的时候,Python就做了这么一个过程(伪码,详见Objects/funcobject.c):a.f = A.__dict__['f'].__get__(a, A)

纯Python模拟的函数对象就像这样:

class Function(object):
    . . .
    def __get__(self, obj, objtype=None):
        "Simulate func_descr_get() in Objects/funcobject.c"
        return types.MethodType(self, obj, objtype)

然后就好理解staticmethodclassmethod这两个decorator了吧。staticmethod无视了传入的第一个self参数,classmethod手工加了一个类对象参数进去。它们的纯Python模拟就像下面所示:

class StaticMethod(object):
 "Emulate PyStaticMethod_Type() in Objects/funcobject.c"

 def __init__(self, f):
      self.f = f

 def __get__(self, obj, objtype=None):
      return self.f

class ClassMethod(object):
     "Emulate PyClassMethod_Type() in Objects/funcobject.c"

     def __init__(self, f):
          self.f = f

     def __get__(self, obj, klass=None):
          if klass is None:
               klass = type(obj)
          def newfunc(*args):
               return self.f(klass, *args)
          return newfunc

研究Python的底层实现是个很有意思的事,至少能让我在使用Python时更加放心:)

全文完


参考资料:

  1. How-To Guide for Descriptors: http://users.rcn.com/python/download/Descriptor.htm
  2. Python Attributes and Methods: http://www.cafepy.com/article/python_attributes_and_methods/python_attributes_and_methods.html
  3. 《Expert Python Programming》,Tarek Ziadé: http://book.douban.com/subject/3285148/

Trie树的Python实现

又是一个由需求驱动的算法学习的例子。

最近weii需要实现一个这样的功能:在发送AT好友的时候能给出自动补全的列表。

最先想到的是当我给出一个用户名的前几个字的时候能自动提示以这个字开头的所有用户名列表(虽然最后发现这是个很2的解决方案-_-),所以最理想的数据结构就是Trie树,也就是字典树。

以前只听过Trie树,现在实际要用了就得把他落到实处了。

首先是Trie树在维基百科上的定义:在计算机科学中,trie,又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

说白了就跟在字典里查单词一样:先拿第一个字母在根节点查找下一结点的位置,如果找到就拿第二个字母在刚刚找到的节点下继续往下查找;如果找不到就说明这个字符串在树中不存在。

C语言实现的代码也在维基百科上:http://zh.wikipedia.org/wiki/Trie#.E5.AE.9E.E4.BE.8B

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TREE_WIDTH 256

#define WORDLENMAX 128

struct trie_node_st {
        int count;
        struct trie_node_st *next[TREE_WIDTH];
};

static struct trie_node_st root={0, {NULL}};

static char *spaces=" \t\n/.\"\'()";

static int
insert(const char *word)
{
        int i;
        struct trie_node_st *curr, *newnode;

        if (word[0]=='\0') {
                return 0;
        }
        curr = &root;
        for (i=0; ; ++i) {
                if (word[i] == '\0') {
                        break;
                }
                if (curr->next[ word[i] ] == NULL) {
                        newnode=(struct trie_node_st*)malloc(sizeof(struct trie_node_st));
                        memset(newnode, 0, sizeof(struct trie_node_st));
                        curr->next[ word[i] ] = newnode;
                } 
                curr = curr->next[ word[i] ];
        }
        curr->count ++;

        return 0;
}

static void
printword(const char *str, int n)
{
        printf("%s\t%d\n", str, n);
}

static int
do_travel(struct trie_node_st *rootp)
{
        static char worddump[WORDLENMAX+1];
        static int pos=0;
        int i;

        if (rootp == NULL) {
                return 0;
        }
        if (rootp->count) {
                worddump[pos]='\0';
                printword(worddump, rootp->count);
        }
        for (i=0;i<TREE_WIDTH;++i) {
                worddump[pos++]=i;
                do_travel(rootp->next[i]);
                pos--;
        }
        return 0;
}

int
main(void)
{
        char *linebuf=NULL, *line, *word;
        size_t bufsize=0;
        int ret;

        while (1) {
                ret=getline(&linebuf, &bufsize, stdin);
                if (ret==-1) {
                        break;
                }
                line=linebuf;
                while (1) {
                        word = strsep(&line, spaces);
                        if (word==NULL) {
                                break;
                        }
                        if (word[0]=='\0') {
                                continue;
                        }
                        insert(word);
                }
        }

/* free(linebuf); */

        do_travel(&root);

        exit(0);
}

但这个版本的实现有两个问题:

  1. 非常耗内存,一个节点下必须有TREE_WIDTH个子节点,不管子节点代表的字母是否出现在Trie树里。这是非常暴力的哈希。。。
  2. 设定了这个TREE_WIDTH也就意味着这个实现只支持ASCII表中的字符作键,不支持中文。

Python内置的dict是用哈希实现的,正好可以解决这两个问题。(dict的基本原理可以参考《Python源码剖析》阅读笔记:第五章-dict对象

  1. dict采用的是开放寻址法解决冲突,节省了内存,但时间复杂度还是O(1)。
  2. dict这个哈希表里可以放任意字符作为键,中文当然也不例外。

Python版的关键改造就是节点的next表用dict代替,维护的是字符->子节点的映射。查找时,若待查询字符是next里的一个键就说明该字符在Trie树里,以这个键得到值就能找到下一节点。插入时也只要插入字符->子节点的映射就可以了。

具体代码在:https://github.com/hbprotoss/codejam/blob/master/trie.py

#!/usr/bin/env python3

class Trie:
    root = dict()

    def insert(self, string):
        index, node = self.findLastNode(string)
        for char in string[index:]:
            new_node = dict()
            node[char] = new_node
            node = new_node

    def find(self, string):
        index, node = self.findLastNode(string)
        return (index == len(string))

    def findLastNode(self, string):
        '''
        @param string: string to be searched
        @return: (index, node).
            index: int. first char(string[index]) of string not found in Trie tree. Otherwise, the length of string
            node: dict. node doesn't have string[index].
        '''
        node = self.root
        index = 0
        while index < len(string):
            char = string[index]
            if char in node:
                node = node[char]
            else:
                break
            index += 1
        return (index, node)

    def printTree(self, node, layer):
        if len(node) == 0:
            return '\n'

        rtns = []
        items = sorted(node.items(), key=lambda x:x[0])
        rtns.append(items[0][0])
        rtns.append(self.printTree(items[0][1], layer+1))

        for item in items[1:]:
            rtns.append('.' * layer)
            rtns.append(item[0])
            rtns.append(self.printTree(item[1], layer+1))

        return ''.join(rtns)

    def __str__(self):
        return self.printTree(self.root, 0)

if __name__ == '__main__':
    tree = Trie()
    while True:
        src = input()
        if src == '':
            break
        else:
            tree.insert(src)
        print(tree)

全文完。

通俗演绎KMP

最近要实现关键字过滤功能,小看了一些经典的字符串匹配算法。
本文要介绍的是KMP算法(Knuth–Morris–Pratt Algorithm),那个Knuth应该再熟悉不过了。

KMP算法是从朴素匹配算法改进而来。回忆一下朴素的匹配算法是怎么完成字符串的匹配的呢?
1. 将原串和模式串左对齐,然后一位一位比较,直到有一个字符不匹配
KMP1.png
2. 发现第二位的B和C不匹配,模式串右移一位
KMP2.png
3. 重复这个流程,直到找到完全匹配的子串或者匹配失败。

但这过程中显然有多比较的地方。如,原串为ABCDEABCDF,模式串为ABCDF。第一轮可以发现E和F不匹配
KMP3.png
很显然右移一位必定不匹配,这时模式串可以直接右移4位跳过ABCD,从E开始再次比较
KMP4.png

那是不是跳过的长度就是前面相同部分的长度呢?其实不是这样的,这种直接跳过前面相同部分的做法在某些情况下会有问题。如,原串为ABCDABCDABF,模式串为ABCDABF,直接跳过相同部分就会遗漏匹配的串
KMP5.png
所以跳过的长度并不是前面完全匹配的部分,可以跳过的长度一般存储在模式串的partial match table中,即KMP算法需要对模式串进行预处理。

先来看看这个partial match table在跳过的过程中是怎么用的,然后再来考察计算partial match table的算法。
ABCDABF的partial match table如下:
KMP6.png
可以跳过的长度 = 当前已匹配长度 - 最后一个字母在partial match table中的值。例如:
KMP7.png
当发现C和F不匹配时,根据公式,当前已匹配串ABCDAB长度为6, 最后一个字母B在partial match table中的对应值为2,所以可以跳过的长度 = 6 - 2 = 4,即:
KMP8.png
这样就能正确匹配了。

partial match table中每个位置i记录的其实就是从0到i的子串中,同时出现在子串前缀和后缀中的最大长度。还是以上面那个例子为例:

  • A没有前缀或后缀,所以长度为0
  • AB前缀为A,后缀为B,没有相同部分,长度为0
  • ABC前缀为A、AB,后缀为BC、C,没有相同部分,长度为0
  • ABCD前缀为A、AB、ABC,后缀为BCD、CD、D,没有相同部分,长度为0
  • ABCDA前缀为A、AB、ABC、ABCD,后缀为BCDA、CDA、DA、A,相同部分为A,长度为1
  • ABCDAB前缀为A、AB、ABC、ABCD、ABCDA,后缀为BCDAB、CDAB、DAB、AB、B,相同部分为AB,长度为2
  • ABCDABF前缀为A、AB、ABC、ABCD、ABCDA、ABCDAB,后缀为BCDABF、BCDAB、CDAB、DAB、AB、B,没有相同部分,长度为0

具体代码参考https://github.com/hbprotoss/codejam/blob/master/kmp.py

全文完。

Python decorator的应用

Decorator是23种设计模式之一,提出的目的是为了在不改变现有代码的前提下,通过在头部或尾部添加代码来扩展功能。
Python语言内建支持decorator模式。由于语法不是本文重点,对语法不熟悉的童鞋可以参考以下几篇文章:

  1. Stackoverflow上的神文:Understanding Python decorators
  2. [Python学习]decorator的使用
  3. PEP318

下面说一下最近在写SNS客户端插件时Python decorator的应用。
插件的方法完成的任务是:

  • 根据OAuth协议,设置好参数,访问HTTP API
  • 读取服务器返回的json
  • 解析json

异常可能来自访问API过程中的网络问题,以及解析json发现服务器返回了错误代码(比如API访问过于频繁,access token有问题等)。在写头几个API的时候做法很自然,用try-except块包裹可能出异常的代码,将各种标准库的异常或者服务器返回的错误信息封装成自己的exception,raise一下告诉主程序有异常需要处理。
但是写了几个方法后发现,每个方法的异常处理流程几乎一模一样,特别是封装标准库的异常,唯一不同的就是解析服务器返回的错误信息。伪码如下:

def method(xxx):
    try:
        f = urllib.request.urlopen(url, data, headers)
        raw_data = f.read().decode('utf-8')
        rtn = json.loads(raw_data)
    except Exception1 as e:
        log.error(e)
        raise CustomException1()
    except Exception2 as e:
        log.error(e)
        raise CustomException2()
        xxx
    else:
        return rtn

出于懒的原因(说得好听点,出于代码复用的目的:D),得想个办法把这些重复性的工作提取出来。
仔细观察可以发现,这些方法在except处理完异常之后都没有额外的工作需要进行。换句话说,可以认为这些代码都位于核心处理代码之后,这是自然就想到了decorator模式,将异常处理放在decorator里,再decorate一下各个方法就可以了。
Decorator如下:

def sinaMethod(func):
    def func_wrapper(*args, **kwargs):
        try:
            raw_rtn = func(*args, **kwargs)
        except urllib.error.HTTPError as e:
            if e.fp:
                # Sina app error
                error_msg = json.loads(e.fp.read().decode('utf-8'))
                error_code = str(error_msg['error_code'])
                if error_code in exception_dict:
                    raise exception_dict[error_code](error_msg['error'])
                else:
                    raise weiUnknownError(str(e))
            else:
                # Network error
                raise weiNetworkError(str(e))
        else:
            return raw_rtn
    return func_wrapper

其作用就是,尝试调用被装饰函数,如果顺利的话直接返回结果。如果有HTTPError异常发生,则解析之,并根据相应情况封装成自定义的异常抛出。
这里使得代码比较简短的一个关键就是这个exception_dict,里面维护了新浪错误代码和需要抛出的异常类之间的映射。根据返回的error_code查找这个字典,如果有则说明这是我们需要关心的异常,那么就用错误消息构造异常对象抛出。如果没有,就不是需要关心的异常,以weiUnknownError异常抛出。
由于新浪在出错时除了返回HTTP报头,还有一段附加data,所以如果e.fp为None则说明不是应用层的异常,可能是网络层及以下出了问题,抛出weiNetworkError。

使用就很简单了,在被装饰的函数前一行加@sinaMethod就可以了。
就这么简单~~


PS:附带说一句,编程语言对设计模式在语法上的支持会大大简化程序猿的编码量。如果是C++/Java,甚至C要用decorator模式就得协商老长一段了~~^_^

multipart/form-data的实现

写之前先吐槽几句:Python社区太懒了,Python3都推出多少年了,那么多第三方库还不port到Python3。不能安于现状啊!


下面是正题:

最近写微博客户端,上传图片需要multipart/form-data编码图片和参数,由于前面说的原因,没有第三方库可用,所以就自己实现一下。

先贴一下multipart/form-data的RFC文档地址:点这里

multipart/form-data主要由三部分组成:

  1. HTTP Header。需要添加头"Content-Type: multipart/form-data; boundary=%s",这个boundary就是分隔符,见第二条。
  2. 分隔符boundary。分隔符是一串和正文内容不冲突的字符串,用以分割多个参数。一般都是N个减号+随机字符串,比如"----------当前时间"。
    正文需要加header:
    Content-Disposition: form-data; name="%s",%s为需要传递的变量名。
    Content-Type: 指定正文MIME类型,默认是纯文本text/plain,未知类型可以填application/octet-stream。
  3. 数据。要注意的是数据的编码,文档上说"7BIT encoding",ISO-8859-1即可。

下面贴一段上传新浪微博图片的代码:

 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
51
52
53
54
#!/usr/bin/env python3

import urllib.request
import urllib.parse
import urllib.error
import time
import json
import mimetypes

def _encode_multipart(params_dict):
    '''
    Build a multipart/form-data body with generated random boundary.
    '''
    boundary = '----------%s' % hex(int(time.time() * 1000))
    data = []
    for k, v in params_dict.items():
    data.append('--%s' % boundary)
    if hasattr(v, 'read'):
        filename = getattr(v, 'name', '')
        content = v.read()
        decoded_content = content.decode('ISO-8859-1')
        data.append('Content-Disposition: form-data; name="%s"; filename="hidden"' % k)
        data.append('Content-Type: application/octet-stream\r\n')
        data.append(decoded_content)
    else:
        data.append('Content-Disposition: form-data; name="%s"\r\n' % k)
        data.append(v if isinstance(v, str) else v.decode('utf-8'))
    data.append('--%s--\r\n' % boundary)
    return '\r\n'.join(data), boundary

#############################################################
url = 'https://upload.api.weibo.com/2/statuses/upload.json'
access_token = 'xxx'
file_name = 'big.png'
path = '/home/xxx/Downloads/' + file_name
status = '1234567'

params = {
    'access_token': access_token,
    'status': urllib.parse.quote(status),
    'pic': open(path, 'rb')
}

coded_params, boundary = _encode_multipart(params)

#############################################################
req = urllib.request.Request(url, coded_params.encode('ISO-8859-1'))
req.add_header('Content-Type', 'multipart/form-data; boundary=%s' % boundary)
try:
    resp = urllib.request.urlopen(req)
    body = resp.read().decode('utf-8')
    print(body)
except urllib.error.HTTPError as e:
    print(e.fp.read())

其中尤其要注意的是,POST上去的data部分要encode成ISO-8859-1。一开始一直encode成UTF-8,死活报的都是格式错误。

nikola+gitpage搭建博客

本来博客是在CSDN上的http://blog.csdn.net/digimon,但最近CSDN在我这一直无法登录,已经在Evernote上积压了好几篇博客,搞烦了,决定自己搭个博客。
由于目前是没有收入来源的屌丝,没钱去买个域名、弄个VPS,只能想免费的招了。WordPress这货屏蔽GAE的UA,导致没法申请博客,最后想到了gitpage。虽然gitpage也有随时被墙的风险,但是我的博客主要记录技术内容,作为程序猿翻个伟大的防火墙还是没问题的吧;-)

gitpage只支持静态页面,网上搜了一下,生成静态页面的工具还真不少,好像专门为此设计的一样,套餐呐有木有。
Python的就有不少: What's the best available static blog/website generator in Python?
还有更多别的语言支持的工具: 32 Static Website Generators For Your Site, Blog Or Wiki

最终选择了nikola,也是因为Quora上那篇文章的推荐。
nikola官网:http://nikola.ralsina.com.ar/

详细安装和配置的教程就不赘述了,可以参考这两篇文章:
+ The Nikola Handbook(官网教程)
+ 用 nikola 写静态博客

下面说一下安装和配置nikola时要注意的问题。
1. 官网上的安装指导中,如果你是Ubuntu用户的话,Mako一定要用pip安装或自己去下,Ubuntu官方源上的版本太旧,运行会出问题。
2. 喜欢用markdown的童鞋除了更改nikola生成的站点根目录下的从conf.py之外,新建博文的时候要注意加上-f markdown参数:nikola new_post -f markdown
3. 喜欢用markdown的童鞋还得注意一下(==!),官方0.5.4有个bug。在/usr/local/lib/python2.7/dist-packages/nikola/plugins/compile_markdown/__init__.py文件中,在73~81行的字符串前加个字母u。

    with codecs.open(path, "wb+", "utf8") as fd:
        if onefile:
            fd.write('<!-- \n')
            fd.write('.. title: {0}\n'.format(title))
            fd.write('.. slug: {0}\n'.format(slug))
            fd.write('.. date: {0}\n'.format(date))
            fd.write('.. tags: {0}\n'.format(tags))
            fd.write('.. link: \n')
            fd.write('.. description: \n')
            fd.write('-->\n\n')
        fd.write("\nWrite your post here.")

改成

    with codecs.open(path, "wb+", "utf8") as fd:
        if onefile:
            fd.write(u'<!-- \n')
            fd.write(u'.. title: {0}\n'.format(title))
            fd.write(u'.. slug: {0}\n'.format(slug))
            fd.write(u'.. date: {0}\n'.format(date))
            fd.write(u'.. tags: {0}\n'.format(tags))
            fd.write(u'.. link: \n')
            fd.write(u'.. description: \n')
            fd.write(u'-->\n\n')
        fd.write(u"\nWrite your post here.")

因为不加u就是str对象,写入的是utf-8编码的文件,当title等参数里出现非英文字母的时候会出先解码异常。(马上提交个pull request去)
4. 要快速部署到gitpage,在站点conf.py里添加:

DEPLOY_COMMANDS = [
'git --git-dir=output/.git --work-tree=output add -A ',
'git --git-dir=output/.git --work-tree=output commit -m "latest auto deploy build"',
'git --git-dir=output/.git --work-tree=output push origin master'
]

python的import机制

同一个模块以相同的模块名被导入时,模块内的代码只执行一遍(模块名必须相同)。
例:

import/
    test.py
    mo/
        A.py


# A.py
a = 1
print(a)
a += 1

# test.py
#!/usr/bin/env python3
import os
import sys
import mo.A
import mo.A
path = os.path.abspath('./mo')
print(path)
sys.path.append(path)
import A

test.py中,第4行执行后输出1。第5行不输出,因为mo.A已经被导入当前namespace。

但是第9行,虽然都是同一个物理文件A.py,但是被导入时的名字不同(mo.A和A),所以还是会输出1。mo.A和A作为两个独立的module对象存在当前namespace中。

如果要把模块中的变量当全局变量来使用的话,一定要从项目顶部通过“.”一层一层import。

实现简单线程池

前段时间在写代码的时候(用了Qt)出现了似乎跟线程池有关的bug,在不确定是否是Qt线程池库QThreadPool的bug的情况下,自己实现了一个简单的线程池以确定到底是我的问题还是QThreadPool是否真有bug。(剧透下,最后证明不是QThreadPool有问题,可能是信号在线程之间传递的时候有问题,这个bug至今未修复= =)

下面记录下我这个线程池的实现思路。
主要有两个类,Thread、Manager。ThreadPool类是整体的包装。

Thread,继承自QThread,用来执行线程代码,并且作为线程对象存在。
Manager,当前线程活动情况的管理类,检查线程池内空闲线程的情况,并管理新添加的任务。

Manager

Manager内部有一个维护空闲线程对象的集合idle_thread,考虑到需要在O(1)的时间内添加或删除指定元素,用了python内置的set。set内部使用哈希实现的,所以时间效率基本能控制在O(1)左右。
还有一个已添加任务的队列queue。时间效率上,入队和出队都要求O(1)的时间,但是最先想到的python内置的list对象是数组和链表的结合,入队时间是O(1),出队时间却是O(n)(参见这个链接),所以用了collections.deque,一个双向链表,能实现入队和出队都是O(1)的时间。另外,由于我不需要优先级的概念,所以线性表足矣。以后如果要考虑优先级的话会改成堆。
另外就是一个idle_thread的互斥量mutex。因为set对象是线程不安全的,所以在添加和删除元素的时候必须有互斥量保护。而collections.deque文档上说是线程安全的,所以就不需要互斥量之类的机制了。

Manager的接口有:
hasIdleThread,返回线程池内是否还有空闲线程。
setThreadIdle,将某个线程加入到空闲线程池中。
startTask,先将task入队,然后看是否有空闲线程,如果有则在这个空闲线程上执行,没有的话就留在队列里等待下次调度。

Thread

在run方法内,通过Manager取出一个task执行,循环直到再没有新的task为止,之后跳出循环,将自己加入到空闲线程集合内。
其实这样并不能保证线程一直存活,还是会有销毁和重建线程的动作,而且某些极端情况下还会很频繁。但是我当时的情况是要执行的任务会一次性全部加入到队列里,而下一次同样的添加动作会相隔比较长的时间,所以问题不大。更重要的是,当时只是为了确定QThreadPool是否有bug,这方面没有考虑地太多。

下面是具体代码(遵循GPLv3协议)

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#!/usr/bin/env python3

import collections
from PyQt4.QtCore import *
from app import logger

log = logger.getLogger(__name__)

class Thread(QThread):
    def __init__(self, manager, name):
    super(Thread, self).__init__()
    self.manager = manager
    self.name = name

    def __str__(self):
    return self.name

    def run(self):
    while True:
        try:
        log.debug(self.name + str(self.manager.queue))
        task = self.manager.dequeueTask()
        task.run()
        if task.autoDelete():
            del task
        except IndexError:
        # There is no task
        log.debug(self.name + 'No task, %s quiting' % self)
        break
        except Exception as e:
        print(e)

    self.manager.setThreadIdle(self)

class Manager:
    def __init__(self, max_thread_count):
    self.max_thread_count = max_thread_count

    self.threads = [Thread(self, 'thread_%d' % i) for i in range(max_thread_count)]

    self.idle_threads = set(self.threads)
    self.idle_threads_mutex = QMutex()

    self.queue = collections.deque()

    def hasIdleThread(self):
    return len(self.idle_threads) != 0

    def setThreadIdle(self, thread):
    self.idle_threads_mutex.lock()
    self.idle_threads.add(thread)
    log.debug('%s becomes idle' % thread)
    self.idle_threads_mutex.unlock()

    def startTask(self, task):
    self.enqueueTask(task)
    log.debug('%s enqueued' % task)

    self.idle_threads_mutex.lock()
    try:
        thread = self.idle_threads.pop()
        thread.start()
        log.debug('%s started' % task)
    except KeyError:
        # No idle thread
        log.debug('No idle thread')
        pass
    except Exception as e:
        print(e)
    self.idle_threads_mutex.unlock()

    def enqueueTask(self, task):
    self.queue.append(task)

    def dequeueTask(self):
    return self.queue.popleft()

class ThreadPool:
    def __init__(self, max_thread_count=2):
    self.manager = Manager(max_thread_count)

    def start(self, task):
    if not isinstance(task, QRunnable):
        raise TypeError('Task must be QRunnable object.')
    self.manager.startTask(task)