Tallate

Git

发表于 2018-07-29 更新于 2025-07-07 分类于其他

概念

Git 中有 4 个区域：

工作区( Working Area )
暂存区( Stage )
本地仓库( Local Repository )
远程仓库( Remote Repository )

文件有 5 种状态：

未修改( Origin )
已修改( Modified )
已暂存( Staged )
已提交( Committed )
已推送( Pushed )
文件刚开始处于工作区，编辑文件后可以使用git diff查看文件进行了哪些修改
add 命令可以添加到暂存区，可以使用git diff --cached查看文件在暂存区和本地仓库之间的区别
commit 提交到本地仓库，可以使用git diff master origin/master查看本地仓库分支和远程仓库分支之间的区别
注意，Git 保存的不是文件差异或者变化量，而只是一系列文件快照，并使用一个 commit 来指向它们。
push 将本地仓库的代码提交到远程仓库

索引

分支

命令

status

1	$ git status -s # 短版status

diff（比较文件）

git diff --cached # ，同--staged
git diff branch1 branch2 --stat //显示出所有有差异的文件列表
git diff branch1 branch2 文件名(带路径) //显示指定文件的详细差异
git diff branch1 branch2 //显示出所有有差异的文件的详细差异

log（显示提交历史）

对比分支差异
列出最近两次提交引入的更改（-p 相当于 diff 命令）

1	$ git log -p -2

其他选项

$ git log --stat # 列出每次提交的state（相当于加state命令）
$ git log --pretty=？？？ # 以某种格式化输出log
$ git log --since=2.weeks # 打印最近2周的log
$ git log -S function_name # 过滤出对function_name字符串有修改的commit，另外在log最后加--file，可以限制只打印对file有修改的commit
--decorate：在结果中显示当前所处的branch
--graph：以更直观的方式区别不同的branch

打印出炫酷的效果：

1	$ git log --graph --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Creset %s %Cgreen(%cr) %C(bold blue)<%an>%Creset' --abbrev-commit --date=relative

ignore

.gitignore 文件中的规则匹配的文件会被 git 忽略，但是文件事先要从索引中删除。

config

1
2
3

$ git config --global credential.helper cache # 设置凭证缓存，以后就不用每次都输入密码了，但默认只保存15分钟
$ git config credential.helper 'cache --timeout=3600' # 设置凭证保存一个小时
$ git config --global credential.helper store # 长期存储

add（建立索引）

git add .

unmodifying（已修改->未修改）

1
2
3

git checkout .
$ git checkout -- <file>... # 若已tracked的文件被修改，可以使用这条命令恢复到未修改时的情况
git reset --hard

commit（提交）

1
2

$ git commit -a # 自动add并提交追踪过的所有文件
$ git commit --amend # 覆盖上一次的commit，比如可以修改commit message，也可以删除一些文件的索引后再次进行提交，在误提交一些配置文件后可以这样挽救

unstage（撤销 add，已暂存->已修改）

1
2
3

$ git reset HEAD <file>... # 撤销上一次的add
$ git rm -rf --cached [文件] # 仅删除索引，不删除，-r递归，-f强行移除
$ git rm -rf [文件] # 从工作目录和跟踪列表中删除

tag

$ git tag # 显示所有标签
$ git tag -a v1.4 -m "my version 1.4" # 给最近一次的commit加一个注释标签（相当于一个节点）
$ git show <tag-name> # 显示tag和被tag的commit的信息
$ git tag v1.0-lw # 加一个轻量标签，仅仅在文件中记录最近一次commit的checksum
$ git tag -a v1.2 <checksum> # 在后面指定某个commit的完整（或部分）checksum也可以加一个标签，checksum可以使用$ git log --pretty=oneline得到
$ git push origin [tagname] # 将某个标签推送到远程服务器中
$ git push origin --tags # 将所有标签推送到远程服务器
$ git checkout -b [branchname] [tagname] # 转换到另一branch

aliase

$ git config --global alias.co checkout
$ git config --global alias.br branch
$ git config --global alias.ci commit
$ git config --global alias.st status
$ git config --global alias.unstage 'reset HEAD --'
$ git config --global alias.last 'log -1 HEAD'

以后就可以使用 git ci 来 commit 了

1	$ git config --global alias.visual '!gitk'

为自己写的工具设置别名

push

$ git push origin serverfix:awesomebranch # 将serverfix代表的分支推到远程origin的awesomebranch分支上
$ git push origin --delete serverfix # 删除服务器上的一个分支
$ git push --set-upstream origin master # 将当前分支的提交上传到远程仓库的某个分支并与其建立跟踪
$ git push -u origin master # 同上

remote

$ git remote # 显示远程服务器名，默认赋名origin
$ git remote -v # 显示需要从该远程主机读/写时可以使用的URL
$ git remote add <shortname> <url> # 添加一个可用的远程仓库
$ git fetch [remote-name] # 获取远程仓库有而本地仓库没有的信息，但不merge
$ git pull # fetch并merge
$ git push [remote-name] [branch-name] # 向有写权限的主机push数据
$ git remote show [remote-name] # 显示远程仓库的详细信息
$ git remote rename [old] [new] # 重命名仓库的shortname
$ git remote rm [shortname] # 移除远程仓库

branch

$ git branch -v # 显示每个branch的最后一个commit
$ git branch --merged # 过滤branch，只显示并入到当前branch的branches，同样的还有--no-merged
$ git branch -u origin/serverfix # 改变当前分支track的上流分支
$ git branch -vv # 查看每个本地分支track的服务器分支（只和最近一次fetch比较）
$ git branch -r # 查看远程分支列表
$ git branch -D [branch] # 强行删除分支，不管分支有没有被并进来

checkout

$ git checkout -b [branch] [remotename]/[branch] # 在本地创建一个新分支，与远程的一个分支同步
$ git checkout --track origin/serverfix # 上面的缩写
$ git checkout serverfix # 上面的缩写
$ git checkout -b sf origin/serverfix # 如果将要创建的本地分支与所要track的远程分支不同名
撤销文件的修改（还未add的文件）

rebase（衍合）和 merge（合并）

实现方式：rebase 和 merge 都是用来在推送之前整合提交历史的，但是实现的方式却不同，rebase 先找出两个分支的公共祖先，然后将一个分支的从该节点之后的所有提交都当成补丁应用到另一个分支上；merge 同样是先找到分支的公共祖先，然后对两个分支的最新提交进行合并？？？，将合并中修改的内容生成一个新的 commit。
冲突解决：rebase 和 merge 在实施过程中都有可能会出现冲突的情况，merge 遇见冲突后会直接停止，等待手动解决冲突并重新提交 commit 后，才能再次 merge；而 rebase 遇见冲突后会暂停当前操作，开发者可以选择手动解决冲突、add 更新索引，然后 git rebase –continue 继续，或者 –skip 跳过（注意此操作中当前分支的修改会直接覆盖目标分支的冲突部分），亦或者 –abort 直接停止该次 rebase 操作。
pull 命令其实相当于 fetch+merge，可以通过在后面加上 --rebase 选项来指定为 rebase 操作，或者先 fetch，之后再考虑使用 merge 还是 rebase。
不要 rebase 已经公开的提交对象，因为它会舍弃当前分支已经提交的 commit，对别人来说就像该分支被回滚了一样，如果 pull 了可能就会出问题。
https://git-scm.com/book/en/v2/Git-Branching-Basic-Branching-and-Merging#Basic-Merge-Conflicts

当有修改未 commit 时，不能进行 rebase 操作，此时可以考虑先用 git stash 命令暂存；但是 merge 可能会直接将未 commit 的内容覆盖掉。

$ git rebase b # 嫁接过去，将当前分支里的补丁应用到目标分支的最后一个提交对象上，也就是在目标分支的最后一个commit的基础上重演一遍修改，最后将当前分支的？？？指过去
$ git rebase --onto master server client # 将分支server上的另一分支client衍合到master上
$ git rebase master server # 将server分支衍合到master中来
$ git rebase -i b # 显示详细信息，包括各commit会被连接到目标分支的哪个commit后面，并且可以指定命令（策略pick、reword、edit、squash、fixup、exec）？？？？？？？，默认为pick
$ git merge b # 将目标分支合并进来
$ git merge --ff-only # ff的意思是fast-forward，这种情况下要么当前分支已经是最新的了、要么合并是可以fast-forward的（只移动分支指针），默认情况下是--no-ff，也就是普通的合并

stash

1 2	$ git stash apply # 使用最近一次的stash记录来还原当前分支 $ git stash clear # 清空stash表

reset

统计代码量

统计每个人的代码量：

git log --format='%aN' | sort -u | while read name; do echo -en "$name\t"; git log --author="$name" --pretty=tformat: --numstat | awk '{ add += $1; subs += $2; loc += $1 - $2 } END { printf "added lines: %s, removed lines: %s, total lines: %s\n", add, subs, loc }' -; done

统计某个人某段时间内的代码量：

git log --since='2019-01-15' --until='2019-12-31' --format='%aN' | sort -u |
while read name; do echo -en "$name,";
git log --since='2019-01-15' --until='2019-12-31' --author="$name" --numstat
--pretty=tformat: --no-merges | awk '{ add += $1; subs += $2; loc += $1 - $2 }
END { printf "added lines, %s, removed lines, %s, total lines, %s\n", add, subs,
loc }' -; done >> XXX_19_12_31_code.csv;

回滚

Git 支持对本地代码库或远程代码库回滚。
参考：git 远程分支回滚

工作流

首先 master 分支即发布的版本，在此上分出一个 develop（huang）版本，每次发布任务时，在 develop 的基础上分出 liu、du、zhou、shen，完成各自的任务，完成后合并到 develop 上。
若 master 上出 bug 了就直接分出一个 hotfix 分支，修复后马上合并到 master 和 develop 上。
开发完成后（即 liu、du、zhou、shen 等的分支都已合并进 develop）在 develop 上分出一个 release，进行测试，最后合并到 master 上。

参考

Java-集合框架

发表于 2018-07-11 更新于 2025-07-07 分类于 Java

Java-集合框架

阅读全文 »

博客搭建

发表于 2018-07-04 更新于 2025-07-07 分类于其他

一、参考

搭建博客

hexo 使用

在 GitHub 上写博客

添加持久链接功能

hexo 链接持久化终极解决之道

添加评论功能

Hexo NexT 主题中集成 gitalk 评论系统

添加网站统计功能

添加看板动画

hexo 添加 live2d 看板动画

添加复选框样式

数学公式

markdown 格式化

hustcc/lint-md

二、博客搭建

流程

创建 GitHub Pages 仓库
安装 hexo 博客框架
初始化 hexo 项目
提交 hexo
配置 hexo

创建 GitHub Pages 仓库

在 GitHub 上创建username.github.io 的一个项目，username 为 github 上的用户名，该仓库将成为 hexo 打包后的发布地址。

安装 hexo

# 更新node版本，需要在root下运行
npm install -g n
n stable
# 使用cnpm安装hexo
alias cnpm="npm --registry=https://registry.npm.taobao.org \
--cache=$HOME/.npm/.cache/cnpm \
--disturl=https://npm.taobao.org/dist \
--userconfig=$HOME/.cnpmrc"
cnpm install -g hexo-cli
# 遇到“Node Sass does not yet support your current environment:”的问题，需要重装node-sass模块
npm uninstall --save node-sass
npm install --save node-sass

初始化 hexo 项目

hexo init

创建测试页面。

1	hexo new test

本地测试。

1
2
3

hexo clean
hexo generate
hexo server

打包提交

1
2
3

hexo clean
hexo generate
hexo deploy

hexo升级

https://theme-next.js.org/docs/getting-started/upgrade.html

配置 hexo

主要是对项目下名为_config.yml的配置文件的修改。

博客中的图片显示

刚开始希望把图片直接放到 hexo 项目里，但hexo g时总是出现莫名其妙的错误，图片也没有被拷贝到 public 目录下面，部署后当然看不到。
后来希望使用图床来解决问题，需要有一个图床的客户端，比如极简图床，还需要一个存储后端，常用的如微博图床或七牛，申请七牛还需要验证身份这个过程有些麻烦，微博图床据说也不稳定，有一种图床是专业的图床既提供了前端又自带了后台存储，如sm.ms，但是怎么可能永远免费，想来想去还不如自己搭建一个简单的图片服务器。

先租一台服务器

将图片拷贝到服务器上

1	scp -r local_path user@address:/server_path

部署 web 服务器
如果像我一样懒，可以直接跑一个容器当 web 服务器，nginx 作为静态 web 服务器有很高的性能，以后也可以根据需要做一些其他配置，在服务器上执行下面命令运行一个 nginx 服务器：
1
docker run -p 80:80 -v /path/to/resources:/usr/share/nginx/html -v /path/to/logs:/var/log/nginx nginx
备份
以防万一，最后在 github 留了一份备份，这样一份图片就有三份备份了。
注意
如果图片访问403了，很有可能是权限不够，因为默认ng配置里是通过nginx用户来读取本地路径下的图片的，

默认ng配置可以通过docker exec <container ID> -it /bin/sh连到容器里查看/etc/nginx/nginx.conf，第一行可以看到配置user nginx;。

上边的工作不需要太多时间，以后需要同步的话也比较方便。

HTTPS

https://tallate.github.io/73d751b6.html

三、博客内容构建

categories 和 tags
hexo 里一篇博客有 categories 和 tags 这两个属性用于对博客进行归档，有时候这两个东西的作用容易搞混，按我的理解， categories 更像是书前面目录的章节， tags 像是书后面对关键词的索引，比如目录中有一章专门讲 Java 技术栈的内容， category 就是《 Java 》，同理可能还有《 Linux 》，这两章都讲了叫作 Semphore 的东西，所以他们都包含一个叫 Semphore 的 tag ，当然如何划分总归还是要靠个人意愿。
文章频率
博客并不是新闻那样的实时内容平台，而是重在积累，两篇相邻的文章之间横跨好几个星期甚至几个月也很正常，如果非常频繁的发博客反而应该怀疑内容的可靠性。

Linux 环境实用工具

发表于 2018-04-30 更新于 2025-07-07 分类于 Linux

Linux 下工作常用工具，用于提升效率。

阅读全文 »

内存池介绍

发表于 2017-11-06 更新于 2025-07-07 分类于设计

内存池

buffer/cache/pool

cache（高速缓存）是一种介于寄存器和内存之间的存储器，访问速度也在他们二者之间，当用户程序请求存储空间时，会先尝试从 cache 获取，当找不到时再到内存中找，并且找到的页及其临近的几页都会被拿到 cache 中去以备下次访问。
而 buffer 出现的地方比较多，比如 java4 引入的 NIO 中就有一个 Buffer，它的主要作用是缓冲从 Channel 中取到的数据，服务器接收到网络请求时从准备到开始接收数据是有一定的时延的，当出现大量的小请求时，很容易造成资源的浪费，所以引入了缓冲区。
pool 常出现在一些框架中，常见的有数据库连接池、内存池，它和 buffer 有些区别，pool 中的对象往往可以重复利用。

malloc/free

通过调用 malloc 和 free 函数可以实现在堆上的对象分配，这是 C 语言标准库提供的最基本的手动管理内存分配的方法，但是 malloc/free 实现的其实是最基本的 指针碰撞（Bump the Pointer） 内存分配方式，每次分配时都会从空闲块链表表头开始搜索，找到足够大的一块就返回，释放时同样是在空闲块链表中遍历，找到它的分配位置，再和前后两块合并。

显然，这种方式存在一些缺陷：

大量分配后空闲块链表变得很长（时间开销）
产生大量内存碎片（空间开销）
使用麻烦，容易造成内存泄露（申请后忘了释放）

下面是一种 malloc/free 的实现：

折叠/展开代码

typedef long Align; //最受限类型

union header{ //块头部
    struct{
        union header *ptr; //空闲块链表的下一块
        unsigned size; //本块的大小
    }s;
    Align x; //强制块对齐，即强制header最小不小于Align
};
typedef union header Header;
/******************************************/
#define MAXBYTES (unsigned)10240

static Header base;//链表
static Header *freep = NULL;//空闲链表的初始指针

/* malloc函数：存储分配 */
void *malloc(unsigned nbytes){
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;
    
    //超出可分配字节数上限
    if(nbytes > MAXBYTES){
        fprintf(stderr, "alloc: can't allocate more than %u bytes\n", MAXBYTES);
        return NULL;
    }

    //需要分配的块数
    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    //空闲链表不存在
    if((prevp = freep) == NULL){
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        //足够分配
        if(p->s.size >= nunits){
            if(p->s.size == nunits){
                prevp->s.ptr = p->s.ptr;
            }
            else{
                //如果找到的块太大，则分配其末尾部分
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void*)(p + 1);
        }
        //闭环的空闲链表
        if(p == freep){
            if((p = morecore(nunits)) == NULL){
                return NULL;//系统无剩余存储空间
            }
        }
    }
}

#define NALLOC 1024 //最小申请单元数
static unsigned maxalloc; //当前已分配的最大内存块的长度
/* morecore函数：向系统申请更多的存储空间 */
Header *morecore(unsigned nu){
    char *cp, *sbrk(int);
    Header *up;
    
    if(nu < NALLOC){
        nu = NALLOC;
    }
    cp = sbrk(nu * sizeof(Header));
    if(cp == (char*) - 1){ //没有空间
        return NULL;
    }
    up = (Header*)cp;
    up->s.size = nu;
    maxalloc = (up->s.size > maxalloc) ? up->s.size : maxalloc;
    //把多余的存储空间插入到空闲区域
    free((void*)(up + 1));
    return freep;
}

/* free函数：将块ap放入空闲块链表中 */
void free(void *ap){
    Header *bp, *p;
    
    bp = (Header*)ap - 1; //块头
    //欲free的内存块长度不能等于0或者大于当前已分配的最大内存块长度
    if(bp->s.size == 0 || bp->s.size > maxalloc){
        fprintf(stderr, "free: can't free %u units\n", bp->s.size);
        return ;
    }
    //扫描空闲块链表，找到bp所处位置，它可能在两个空闲块之间，也可能在链表末尾
    for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr){
        //被释放的块在链表的开头或末尾
        if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)){
            break;
        }
    }
    //与上一相邻（空闲）块合并
    if(bp + bp->s.size == p->s.ptr){
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    }
    else{//说明中间有已经分配的块
        bp->s.ptr = p->s.ptr;
    }
    //与下一相邻（空闲）块合并
    if(p + p->s.size == bp){
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    }
    else{//说明中间有已经分配的块
        p->s.ptr = bp;
    }
}

简单的测试：

折叠/展开代码

typedef struct MyList {
    int val;
    struct MyList *next;
} MyList;

int main(int argc, char *argv[]) {
    int n = 1000000;
    while(n--) {
        MyList *list = malloc(sizeof(MyList));
        free(list);
    }
    return 0;
}

设计简单内存池

内存池和线程池或数据库连接池（各种池）的实现机制类似，都是事先申请一大块资源，当实际使用时，不必再去申请内存，而是直接从内存池中“拿”，如果内存池设计得好，完全可以避免直接使用 malloc/free 进行内存管理的问题。

下面的代码很大程度上参考了这里的实现

折叠/展开代码

mem_pool.h
#ifndef _MEM_POOL_H
#define _MEM_POOL_H

#define BLOCKHEAD_SIZE 24 // 两个地址值合为16位，再加上8位验证码
#define MAGIC_CODE 0x123456 // 验证码（用于free内存块的时候判断是否是合法的内存块）

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

/**
 * 内存块
 * 1.data包含head和body两部分
 * head包括指向对应block的指针、对应list的指针及验证码（MAGIC_CODE）
 * 2.双向链表
 * 为了free时方便从used中拿出插入到free中
 */
typedef struct MemBlock {
    void *data;
    struct MemBlock *prev, *next;
} MemBlock;
static MemBlock *newMemBlock(int size) {
    MemBlock *block = malloc(sizeof(MemBlock));
    if(! block) {
        perror("malloc MemBlock failed");
        return NULL;
    }
    block->data = malloc(BLOCKHEAD_SIZE + size);
    return block;
}
/**
 * 内存表
 * 1.每个list保存一种size的内存块
 */
typedef struct MemList {
    MemBlock *free, *used;
    int size;
    struct MemList *next;
} MemList;
static MemList *newMemList(int size) {
    MemList *list = malloc(sizeof(MemList));
    if(! list) {
        perror("malloc MemList failed");
        return NULL;
    }
    list->size = size;
    return list;
}
/**
 * 内存池
 * 1.单例（因为是C语言，所以还未实现）
 * 1.蝇量
 */
typedef struct MemPool {
    MemList *head;
    MemList *last;
} MemPool;
static MemPool *newMemPool() {
    MemPool *pool = malloc(sizeof(MemPool));
    if(! pool) {
        perror("malloc MemPool failed");
        return NULL;
    }
    return pool;
}

void* getBuf(MemPool *pool, size_t bufSize);
int freeBuf(void *buf);

#endif // _MEM_POOL_H

#include "mem_pool.h"

/**
 * 把内存块想象成一个int64的数组，头三个元素（head）为元数据，
 * 之后的部分为分配给用户实际可用的内存
 */
void setMemoryHead(void *buf, MemList *list, MemBlock *block) {
    if(buf == NULL) {return ;}
    int64_t *data = (int64_t *)buf;
    // 设置头部，注意指针有64位
    data[0] = (int64_t)list;
    data[1] = (int64_t)block;
    data[2] = (int64_t)MAGIC_CODE;
}
void* getMemoryBody(void *buf) {
    if(buf == NULL) {return NULL;}
    int64_t *data = (int64_t *)buf;
    return &data[3];
}
/**
 * 从释放的内存块中可以找到它所属的list和block节点位置
 * @return 0表示失败，其他表示成功
 */
int getFromBuf(void *buf, MemList** list, MemBlock** block) {
    // 先转换为字节数组再计算到头部的偏移量，因为
    char* cbuf = buf;
    int64_t *data = (int64_t *)(buf - BLOCKHEAD_SIZE);
    if(data[2] != MAGIC_CODE) {
        perror("error: not a valid block");
        return 0;
    }
    // 还原
    *list = data[0];
    *block = data[1];
    return 1;
}

/**
 * 从内存池中获取一块内存
 * 内存块的大小是固定的，链表的每个节点代表一种大小的内存块
 */
void* getBuf(MemPool *pool, size_t bufSize) {
    if(! pool) {return NULL;}
    // list为空，表示还未分配过，尝试分配并初始化
    if(! pool->head) {
        pool->head = newMemList(bufSize);
    }
    MemList *list = pool->head;

    // 查找匹配大小的list
    while(list && list->size != bufSize) {
        list = list->next;
    }

    // 没有匹配的list，分配一个，插入到表头处
    if(! list) {
        MemList *tmp = newMemList(bufSize);
        tmp->next = pool->head;
        pool->head = tmp;
        list = tmp;
    }

    // 查找已有list中是否存在空余内存块，若没有则新建
    if(! list->free) {
        list->free = newMemBlock(list->size);
    }

    // 取一块
    MemBlock *block = list->free;
    list->free = block->next;
    if(list->free) {
        list->free->prev = NULL;
    }
    // 压回已使用块表
    if(list->used) {
        list->used->prev = block;
    }
    block->next = list->used;
    list->used = block;

    // 设置块头部
    setMemoryHead(block->data, list, block);
    return getMemoryBody(block->data);
}

/**
 * 释放一块内存
 * @return 0表示释放失败，其他数字表示成功
 */
int freeBuf(void *buf) {
    MemList *list = NULL;
    MemBlock *block = NULL;
    if(! getFromBuf(buf, &list, &block)) {
        return 0;
    }

    // 从used块中取出
    if(block->prev) {
        block->prev->next = block->next;
    }
    if(block->next) {
        block->next->prev = block->prev;
    }
    // 放到free块中
    if(list->free) {
        list->free->prev = block;
    }
    block->next = list->free;
    block->prev = NULL;
    list->free = block;

    // 操作成功
    return 1;
}

简单的测试：

折叠/展开代码

typedef struct List {
    int val;
    struct List *next;
} List;

int main() {
    MemPool *pool = newMemPool();
    time_t begin, end;
    time(&begin);
    srand(time(0));
    List *list = NULL;
    int n = 100000000;
    while(n--) {
        if(random() % 10 < 7) {
            List *node = getBuf(pool, sizeof(List));
            node->next = list;
            list = node;
        } else if(list) {
            List *node = list;
            list = list->next;
            freeBuf(node);
        }
    }
    time(&end);
    printf("OK\n");
    printf("costs %lf\n", difftime(end, begin));
    return 0;
}

可改进的地方：

线程安全，这里有个问题，是把整个池锁住还是把其中的某个表锁住？因为内存池是使用很频繁的，我更倾向于后者（锁住某个表的实现可以参考 Java 的分段锁机制）
一种 size 一个 list，各 list 之间用链表串联起来，如果申请的内存块大小不固定也可能出现这个链表特别长的情况，那样就退化成了 malloc/free，我觉得解决办法是将分配的内存块大小固定成 1024B、2048B 这些量级，但这样又会多出很多内存碎片，又退化成了 malloc/free
引入引用计数或可达性分析算法来管理内存，但是那样的话需要给所有类做一个公共基类，然后重载基类的’=’操作符用于修改引用数，非常麻烦，但是不这么做就退化成了 malloc/free
老实说这个内存池并没有实用价值

一些框架中的内存管理

Doug Lee 的 malloc/free
？？？
Apache 内存池
Apache 内存池的实现相对上面的来说有很多改进

使用一个free数组来表示上面的MemList，下标每增加 1，内存节点大小增加 4K，这样可以很快定位到要分配的那个内存块链表，如果要分配的内存大小超出数组范围就直接分配到下标 0 处，所以不会有溢出的问题
节点大小和下标间的转换用到了一个宏APR_ALIGN，使用该宏要求size为整数，boundary为 2 的幂，具体执行过程还是自己代入一组值算一算
1
2
#define APR_ALIGN(size, boundary) \
(((size)+ ((boundary) - 1)) &~((boundary) - 1))
没有 used 表，分配时就从 free 中取出来返回给用户，找不到就 malloc 一个，释放时插回到 free 表中
用 current_free_index 和 max_free_index 配合限制内存分配器总共能够分配的内存大小

cocos2d-x 内存管理
对 cocos2d-x 的使用经历比较短，不能很好体会它的设计理念，只列出我记得的一些点：

C++11 下本地存储（栈）比堆存储好，最好不要 new 对象
cocos2d-x 使用引用计数算法管理内存，大部分内置对象都继承自 cocos2d::Object 类

MySQL 内存池
MySQL 使用二级缓存机制管理分配的对象，第一级为缓冲池和通用内存池，他们都通过调用 malloc/free 来从操作系统分配/释放内存块，他们的区别下面再讲；第二级为内存堆，它为其他模块提供内存块分配功能

缓冲池（innobase/buf/buf0buf.c、innobase/include/buf0buf.h）
缓冲池的定义如下

通用内存池（innobase/mem/mem0pool.c、innobase/include/mem0pool.h）
内存池的定义如下

折叠/展开代码

struct mem_pool_struct{
	byte*		buf;		/* memory pool */
	ulint		size;		/* memory common pool size */
	ulint		reserved;	/* amount of currently allocated
					memory */
	mutex_t		mutex;		/* mutex protecting this struct */
	UT_LIST_BASE_NODE_T(mem_area_t)
			free_list[64];	/* lists of free memory areas: an
					area is put to the list whose number
					is the 2-logarithm of the area size */
};

内存池的创建函数如下所示

折叠/展开代码

mem_pool_t*
mem_pool_create(
/*============*/
			/* out: memory pool */
	ulint	size)	/* in: pool size in bytes */
{
	mem_pool_t*	pool;
	mem_area_t*	area;
	ulint		i;
	ulint		used;

	ut_a(size > 10000);
	
	pool = ut_malloc(sizeof(mem_pool_t));

	/* We do not set the memory to zero (FALSE) in the pool,
	but only when allocated at a higher level in mem0mem.c.
	This is to avoid masking useful Purify warnings. */

	pool->buf = ut_malloc_low(size, FALSE);
	pool->size = size;

	mutex_create(&(pool->mutex));
	mutex_set_level(&(pool->mutex), SYNC_MEM_POOL);

	/* Initialize the free lists */

	for (i = 0; i < 64; i++) {

		UT_LIST_INIT(pool->free_list[i]);
	}

	used = 0;

	while (size - used >= MEM_AREA_MIN_SIZE) {

		i = ut_2_log(size - used);

		if (ut_2_exp(i) > size - used) {

			/* ut_2_log rounds upward */
		
			i--;
		}

		area = (mem_area_t*)(pool->buf + used);

		mem_area_set_size(area, ut_2_exp(i));
		mem_area_set_free(area, TRUE);

		UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area);

		used = used + ut_2_exp(i);
	}

	ut_ad(size >= used);

	pool->reserved = 0;
	
	return(pool);
}

由此可以得出通用内存池和缓冲池之间的差别

内存堆（innobase/mem/mem0mem.c、innobase/include/mem0mem.h、innobase/include/mem0mem.ic）
内存堆的定义如下
折叠/展开代码
1
2
/* A memory heap is a nonempty linear list of memory blocks */
typedef mem_block_t mem_heap_t;
可见内存堆就是内存块的链表。

内存块（memory block）的定义如下

折叠/展开代码

struct mem_block_info_struct {
	ulint   magic_n;/* 魔数用于debug（标志该块内存是从我这分出去的） *//* magic number for debugging */
	char	file_name[8];/* 创建内存堆的代码文件名 *//* file name where the mem heap was created */
	ulint	line;	/* 创建内存堆的代码行 *//* line number where the mem heap was created */
	UT_LIST_BASE_NODE_T(mem_block_t) base; /* 在第一块（表头）中定义，保存内存块链表的一些元信息，
                        包括长度、表头指针、表尾指针 */
                        /* In the first block in the
			the list this is the base node of the list of blocks;
			in subsequent blocks this is undefined */
	UT_LIST_NODE_T(mem_block_t) list; /* 内存块的链表（双向链表） *//* This contains pointers to next
			and prev in the list. The first block allocated
			to the heap is also the first block in this list,
			though it also contains the base node of the list. */
	ulint   len;    /* 当前内存块大小，以字节为单位 *//* physical length of this block in bytes */
	ulint 	type; 	/* 该内存堆的类型，内存堆的主要分类依据是：从通用内存池还是缓冲池分配 */
                        /* type of heap: MEM_HEAP_DYNAMIC, or
			MEM_HEAP_BUF possibly ORed to MEM_HEAP_BTR_SEARCH */
	ibool	init_block; /* TRUE if this is the first block used in fast
			creation of a heap: the memory will be freed
			by the creator, not by mem_heap_free */
	ulint   free;   /* 当前空闲空间位置 */
                        /* offset in bytes of the first free position for
			user data in the block */
	ulint   start;  /* the value of the struct field 'free' at the 
			creation of the block */
	byte* 	free_block;
			/* if the MEM_HEAP_BTR_SEARCH bit is set in type,
			and this is the heap root, this can contain an
			allocated buffer frame, which can be appended as a
			free block to the heap, if we need more space;
			otherwise, this is NULL */
#ifdef MEM_PERIODIC_CHECK	
	UT_LIST_NODE_T(mem_block_t) mem_block_list;
			/* List of all mem blocks allocated; protected
			by the mem_comm_pool mutex */
#endif
};

内存块的创建函数如下所示

折叠/展开代码

UNIV_INLINE
mem_heap_t*
mem_heap_create_func(
/*=================*/
				/* out, own: memory heap */
	ulint	n,		/* in: desired start block size,
				this means that a single user buffer
				of size n will fit in the block, 
				0 creates a default size block;
				if init_block is not NULL, n tells
				its size in bytes */
	void*	init_block,	/* in: if very fast creation is
				wanted, the caller can reserve some
				memory from its stack, for example,
				and pass it as the the initial block
				to the heap: then no OS call of malloc
				is needed at the creation. CAUTION:
				the caller must make sure the initial
				block is not unintentionally erased
				(if allocated in the stack), before
				the memory heap is explicitly freed. */
	ulint	type,		/* in: MEM_HEAP_DYNAMIC, or MEM_HEAP_BUFFER
				possibly ORed to MEM_HEAP_BTR_SEARCH */
	char*  	file_name,	/* in: file name where created */
	ulint	line		/* in: line where created */
	)
{
	mem_block_t*   block; 

	if (n > 0) {
                // 创建指定大小的内存块
		block = mem_heap_create_block(NULL, n, init_block, type,
							file_name, line);
	} else {
		// 以默认的大小创建，MEM_BLOCK_START_SIZE的值为64B
		block = mem_heap_create_block(NULL, MEM_BLOCK_START_SIZE, 
					init_block, type, file_name, line);
	}

	ut_ad(block);

	UT_LIST_INIT(block->base);

	/* Add the created block itself as the first block in the list */
	UT_LIST_ADD_FIRST(list, block->base, block);

	#ifdef UNIV_MEM_DEBUG

	if (block == NULL) {

		return(block);
	}

	mem_hash_insert(block, file_name, line);

	#endif
	
	return(block);
}

当想要扩增内存堆时调用，它会将扩增的内存块插入内存堆的末尾（mem_block_info_struct 结构中的 base 成员变量包含了表尾指针），而且每次扩增的内存块大小为前一次的两倍大

内存池和 GC 的关系
在阅读《垃圾回收的算法与实现》时，除了某人用 GC 交到了女朋友外，使我最印象深刻的应该是前言中一位教授对 GC 和虚拟内存关系的看法：

既然话说到这里了,我就再介绍一下我的个人看法吧。实际上,GC 相当于虚拟内存。一般的虚拟内存技术是在较小的物理内存的基础上,利用辅助存储创造一片看上去很大的“虚拟”地址空间。也就是说,GC 是扩大内存空间的技术,因此我称其为空间性虚拟存储。这样一来,GC 就成了永久提供一次性存储空间的时间轴方向的时间性虚拟存储。神奇的是,比起称为“垃圾回收”,把 GC 称为“虚拟内存”令人感觉其重要了许多。当初人们根据计算机体系结构开发了许多关于空间性虚拟存储的支持,所以大部分的计算机都标配了空间性虚拟存储。只要硬件支持,GC 性能就能稳步提升,然而现实情况是几乎没有支持 GC 的硬件,这不能不令人感到遗憾。

什么时候使用内存池及一些要点

小心内存泄露
如果应用从内存池中获取对象后没有释放回去就很有可能会发生内存泄露的情况，和 C 语言中 malloc 后忘了 free 的情况类似。一般内存池都是单例的，这意味着内存池和整个应用的生命周期是相同的，这块没被释放的内存将一直占用内存空间，而且因为内存池中总是有对这个对象的引用，所以就算有 GC 也没有办法进行回收。
水平有限我仅谈谈在 Web 应用中的几个解决办法：
- 缩短内存池的生命周期，比如在一次会话期间占用一个内存池，这个内存池将会被保存在一个 SessionContext 对象中，当会话结束时就释放它
- 在一些对象价值不是特别高的情形下（比如），可以使用 弱引用对象池 来管理对象？？？

参考

《C 程序设计语言》
内存池的实现 http://www.cnblogs.com/bangerlee/archive/2011/08/31/2161421.html
A memory pool written with C++ https://github.com/bangerlee/mempool
MySQL 内核 InnoDB 存储引擎
https://www.zhihu.com/question/26190832/answer/32387918
《垃圾回收的算法与实现》

姓名排序

发表于 2017-11-06 更新于 2025-07-07 分类于算法

姓名排序

题目描述：给定 30,000 个中国人的名字，选用一种线性排序方法有效排序，要求使用内存不超过 1G。
想法 1：计数排序，汉字组合显然是无穷多的，无法确定元素的范围，而且可能有重名的情况，所以不能使用；
想法 2：使用桶排序，不好确定每个桶的元素范围，一般情况下都是假定元素限制在(0,1]；
想法 3：使用基数排序可以一次按名字的第 i 位的排序，如果每个桶的标志为一个汉字，那桶就太多了，如果每个桶的标志为汉字的首字母，桶够少了，但是每个桶都需要大量时间，既然是汉字，我们完全可以用汉字拼音；

获得测试组

一组有 3w 行，每一行随机 2-10 个 utf-8 中文字符

从这里[1]了解到 unicode 字符的基本汉字编码范围为 4E00-9FA5，我的想法是随机生成一个 19968-40869 的 unsigned int 型数，然后编码成 utf-8 字符；

utf-8 字符可以由 unicode 字符转换而来，转换算法[2]为：

×××××××× ×××××××× -> 1110×××× 10×××××× 10××××××
1110拼上前4位
10拼上中间6位
10拼上后6位

输入到文件中

源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//中文字为3字节，第一步
void randomname(unsigned char *name){
    int length = random() % 8 + 2;
    int pos;
    for(pos = 0; pos < length; pos++){
        unsigned int a = (random() % 20902) + 19968;
	       name[3 * pos] = (a >> 12) + 224;
	       name[3 * pos + 1] = ((a >> 6) % 64) + 128;
	       name[3 * pos + 2] = (a % 64) + 128;
    }
    name[3 * pos] = '\0';
    printf("%s", name);
}
void makefile(FILE *f){
    if(f == NULL){
        fprintf(stderr, "error1");
        exit(1);
    }
    unsigned char name[35];
    int count = 30000;
    srand(time(0));
    while(count--){
        randomname(name);
        if(fprintf(f, "%s%c", name, '\r') == 0){
            fprintf(stderr, "error");
	           break;
        }
    }
    fclose(f);
}
int main(void){
    FILE *f = fopen("a.txt", "w");
    makefile(f);
    return 0;
}

转码

我们希望按照拼音顺序排序，所以得先将 UTF-8 字符转换为 GB2312 编码

这里遇到了难题，我打算使用 linux 下的 iconv 进行转码，但是转出来的都是乱码，可能是对转码的工作原理还不明白。

刚开始我打算编写 C 语言代码转换 utf-8 -> gb2312，但是失败了，一是因为有些字符在 gb2312 中不存在，报错：

1 2	C语言中出现 iconv(pattern, pin, &inlen, pout, &outlen) 返回-1 命令行下出现 iconv: 未知 0 处的非法输入序列

二是我直接输出到了终端，结果出现了乱码：

你好 -> ����

是因为终端默认使用 utf-8，这样就无法显示了。

后来使用 GBK，因为 GBK 包括 gb2312，将编码后的字符直接输出到了文件中，这样就能看到编码后的结果了

代码：

#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <stdlib.h>
int code_convert(char *from_charset, char *to_charset, char *inbuf, size_t inlen, char *outbuf, size_t outlen){
    iconv_t pattern;
    char **pin = &inbuf;
    char **pout = &outbuf;
    pattern = iconv_open(to_charset, from_charset);
    if(pattern == 0){
        return -1;
    }
    memset(outbuf, 0, outlen);
    if(iconv(pattern, pin, &inlen, pout, &outlen) == -1){
        return -1;
    }
    iconv_close(pattern);
    return 0;
}
#define MAXNUM 30000
#define MAXNAME 31
char names_utf8[MAXNUM][MAXNAME];
char names_gb2312[MAXNUM][MAXNAME];
void readFile(char *fileName){
    FILE *f;
    if((f = fopen(fileName, "r")) == NULL){
        fprintf(stderr, "cant open file %s\n", fileName);
        exit(1);
    }
    
    int pos;
    for(pos = 0; pos < MAXNUM; pos++){
        //fgets(names_utf8[pos], MAXNAME, f);fgets会保留行末尾的\r\n
        fscanf(f, "%s", names_utf8[pos]);
    }
}
void convert(){
    FILE *f = fopen("b.txt", "w");
    int pos;
    for(pos = 0; pos < MAXNUM; pos++){
        if(code_convert("utf-8", "GBK", names_utf8[pos], strlen(names_utf8[pos]), names_gb2312[pos], MAXNAME) == -1){
	           fprintf(stderr, "iconv error");
	           exit(2);
        }
       fprintf(f, "%s\r\n", names_gb2312[pos]);
    }
    fclose(f);
}

这部分代码等价于以下命令：

1	sudo iconv -f utf-8 -t GBK a.txt -o b.txt

起初认为像 GBK 这样的汉字编码标准会很地道地按拼音顺序来编码，但是还是太天真了，因为有多音字存在等原因，要按拼音编码是不大可能的；

最终上网找了一个汉字转拼音的程序[4]，找拼音的大致思路是预先准备好拼音及该拼音的汉字，要找一个汉字的拼音就遍历一遍找，方法比较简单只覆盖了一部分汉字，而且是线性遍历效率不高，还有个缺点就是多音字只能找到第一个；

对姓名进行排序

最后就是使用基数排序了，因为使用 utf-8 编码，所以数组中 27-29 为第 10 个汉字，24-26 为第 9 个汉字，以此类推，姓名有长有短，比如“张三”的后 8 位都不存在，默认放入 0 号桶，其他情况如果能找到该位汉字的拼音，将姓名放到对应的桶中，如果找不到，默认该汉字未编码，放入 0 号桶，这里桶其实代表 a/an/ang…，最后为了保证排序的稳定性，桶使用了队列实现；

代码如下所示：
其中pinyin.h是，代码如这里所示。

#include "pinyin.h" //汉字-拼音
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define P2HSIZE (sizeof(p2h) / sizeof(p2h[0]))
int getP2Hpos(char word[]){
    if(word == NULL || word[0] == '\0'){ return -1; }
    int pos;
    char *curHzString;
    for(pos = 0; pos < P2HSIZE; pos++){
        curHzString = p2h[pos].hz;
        if(strstr(curHzString, word)){
            return pos;
        }
    }
    return -1;
}
#define MAXNUM 30000 //文件中姓名的数量
#define MAXNAME 31 //姓名最多为10个汉字
char *names_utf8[MAXNUM];
/*******************************************/
void readFile(char *fileName){
    FILE *f;
    if((f = fopen(fileName, "r")) == NULL){
        fprintf(stderr, "cant open file %s\n", fileName);
        exit(1);
    }
    
    int pos;
    for(pos = 0; pos < MAXNUM; pos++){
        names_utf8[pos] = (char*)malloc(MAXNAME * sizeof(char));
        fscanf(f, "%s", names_utf8[pos]);
    }
}
void clearNames(){
    int pos;
    for(pos = 0; pos < MAXNUM; pos++){
        free(names_utf8[pos]);
    }
}
/****************************************/
typedef struct cell{
    int pos;
    struct cell *next;
}cell;
typedef struct bucket{
    cell *front;
    cell *rear;
}bucket;
int isEmpty(bucket *b){
    return b->rear == NULL;
}
cell *makeCell(int pos){
    cell *c = (cell*)malloc(sizeof(cell));
    if(c == NULL){ fprintf(stderr, "error"); }
    c->pos = pos, c->next = NULL;
    return c;
}
bucket *makeBucket(){
    bucket *b = (bucket*)malloc(sizeof(bucket));
    b->front = b->rear = NULL;
    return b;
}
int push(bucket *b, int pos){
    if(b == NULL){printf("error");
        return -1;
    }
    cell *c = makeCell(pos);
    if(isEmpty(b)){
        b->rear = b->front = c;
    }
    else{
        b->front->next = c;
        b->front = c;
    }
    return 0;
}
int pop(bucket *b){
    if(isEmpty(b)){
        return -1;
    }
    else{
        cell *rear = b->rear;
        int pos = rear->pos;
        b->rear = rear->next;
        free(rear);
        return pos;
    }
}
//桶的数量就是拼音的数量，0号桶用于装找不到拼音的汉字
#define BUCKETSNUM (P2HSIZE + 1)
bucket *buckets[BUCKETSNUM];
char tmp[4];
void pushBuckets(int radix){//1 <= radix <= 10，表示第几个字
    int pos, bucketId;
    for(pos = 0; pos < MAXNUM; pos++){//如果改成while(pos++ < MAXNUM)会出现段错误，为什么？？
        strncpy(tmp, names_utf8[pos] + 3 * (radix - 1), 3);
        bucketId = getP2Hpos(tmp) + 1;
        push(buckets[bucketId], pos);
    }
}
//桶中保存的是对应姓名数组的下标
void popBuckets(){
    char *names_tmp[MAXNUM];
    int npos;
    for(npos = 0; npos < MAXNUM; npos++){
        names_tmp[npos] = names_utf8[npos];
    }
    npos = 0;
    int bpos;
    for(bpos = 0; bpos < BUCKETSNUM; bpos++){
        while(!isEmpty(buckets[bpos])){
            int pos = pop(buckets[bpos]);
            names_utf8[npos++] = names_tmp[pos];
        }
    }
}
void initBuckets(){
    int pos;
    for(pos = 0; pos < BUCKETSNUM; pos++){
        buckets[pos] = makeBucket();
    }
}
void clearBuckets(){
    int pos;
    for(pos = 0; pos < BUCKETSNUM; pos++){
        while(pop(buckets[pos]) != -1);
    }
}
void radixSort(){
    int radix;
    for(radix = 10; radix >= 1; radix--){
        pushBuckets(radix);
        popBuckets();
    }
}
void writeResult(){
    FILE *f = fopen("result.dat", "w");
    if(f == NULL){ fprintf(stderr, "open file failed"); exit(1);}
    
    int pos;
    for(pos = 0; pos < MAXNUM; pos++){
        fprintf(f, "%s\r\n", names_utf8[pos]);
    }
    fclose(f);
}
void func(){
    readFile("a.txt");
    initBuckets();
    radixSort();
    writeResult();
    clearNames();
}
int main(void){
    func();
    return 0;
}

拓展

当需要排序的数据量很大，例如 100G 个人按照年龄排序，如何基于外存对这些数据排序？使用 mapreduce 等工具？

参考

2017 沈阳马拉松

发表于 2017-09-08 更新于 2025-07-07 分类于其他

马拉松计划

训练

周	一	二	三	四	五	六	日
4-10	10	11	20	13	休息	30	休息
11-17	8	13	20	13	休息	20	休息
18-24	5	10	13	8	休息	休息	马拉松

PS1：后程如果跑不动，可以尝试跑 5 分钟走 1 分钟调整，喝水时也可以走一会。
PS2：目标是 400，平常用 11 的速度跑，马拉松用 10 的速度。

饮食

平时多喝牛奶。
马拉松时带点巧克力，不知道场地里的粮食多不。

装备

跑前似乎有发衣服，所以就不买专门的速干衣了，但是跑鞋和毛巾袜是必须的。