C++学习之 virtual 关键字

观看一个例子：

 
  1. #include <iostream>
  2. using namespace std;
  4. class A{
  5.     public:
  6.         virtual void say() {
  7.             cout<<"A say: "<<endl;
  8.         }
  9. };
  11. class B :public A{
  12.     public:
  13.         void say() {
  14.             cout<<"B say: "<<endl;
  15.         }
  16. };
  18. void testVirtual(A& a) {
  19.     a.say();
  20. }
  22. int main(void) {
  23.     B b;
  24.     //b.say("hello B");
  26.     testVirtual(b);
  27.     return 0;
  28. }

1. 注意 第6行的virtual关键字和第18行的引用传参
2. 现在的结果是 "B say:";
3. 如果去掉virtual关键字，或者传参的时候不使用引用传参，则，输出的结果都将是： "A say:"
4. 这种语法现象叫 upcast
5. c++ 中class声明类，要以分号结束
6. 参考资料： 《C++编程思想》之 第15章 多态性和虚函数

启动gvim时自动最大化窗口的方法

根据帮助文档，gvim在windows下的最大化是通过模拟打开窗口菜单并点击最大化菜单项实现的，而在Linux下的方法较为灵活。

下面的方法是在vim中通过调用wmctrl实现最大化的方法：

好久没看c++了

好久没看c++了，以为自己还能看明白，今天看了kyototycoon中的一个类，遇到了好几个知识点：

 
  1. // plug-in server driver
  2. class PlugInDriver : public kc::Thread {
  3.  public:
  4.   // constructor
  5.   explicit PlugInDriver(kt::PluggableServer* serv) : serv_(serv), error_(false) {}
  6.   // get the error flag
  7.   bool error() {
  8.     return error_;
  9.   }
  10.  private:
  11.   // perform service
  12.   void run(void) {
  13.     kc::Thread::sleep(0.4);
  14.     if (serv_->start()) {
  15.       if (!serv_->finish()) error_ = true;
  16.     } else {
  17.       error_ = true;
  18.     }
  19.   }
  20.   kt::PluggableServer* serv_;
  21.   bool error_;
  22. };

且只看：
explicit PlugInDriver(kt::PluggableServer* serv) : serv_(serv), error_(false) {}
1. explicit  参看： http://wenku.baidu.com/view/3a02f28fcc22bcd126ff0ced.html
  explicit 用来修饰构造函数的， 表明构造函数是显示的,而且，由explicit修饰的构造函数为默认构造函数；
  因为使用了explicit，则可以：
  PlugInDriver p(serv);  // 而不能：
  PlugInDriver p = serv； // 如果没有explicit ，则这样是可以的， 如：
  string s = "abcd"; // 等价于
  string s("abcd")

2. serv_(serv), error_(false)
  这个是给两个私有成员赋值，至于为什么不卸载构造函数的函数体内，参看《c++编程思想》p329

3. 基类kt::Thread 使用了public来修饰
  如果没有public来修饰的话，则子类的所有的public成员和方法在子类上都将体现为private的，这显然不是我们想看到的； 那样则可以只用组合而不用继承了

linux file命令是如何识别文件的类型的

man file、 strace file /bin/ls , 发现：

file命令参考magic文件/usr/share/file/magic.mgc， 如果/usr/share/file/magic.mgc不存在，会参考 /usr/share/file/magic ； 二者的关系为： magic.mgc 是magic 编译后的文件；编译方法为：
file -C /usr/share/file/magic.mgc -m /usr/share/file/magic

tokyocabinet 与 kyotocabinet

tokyocabinet（简称tc） 与 kyotocabinet（简称kc） 有如下主要区别：
1. tc是用c写的，kc使用c++写的
2. kc抛弃了fixedlength database, table database
3. tc只能在类unix系统中编译，kc也支持windows

Tokyo Tyrant（简称tt） 与 Kyoto Tycoon（简称kt）的区别：
1. tt是用c写的，kt使用c++写的
2. tt不支持自动过期，kt支持自动过期
3. kt有几乎tt的所有的优点
4. kt抛弃了fixedlength database, table database

参考文档： http://fallabs.com/kyotocabinet/kyotoproducts.pdf

关于树的知识

首先，数据结构分为逻辑结构和存储结构，这里我们也要把树的逻辑结构和存储结构分开来讲。

树的最基本的定义：
树是n（n>=0）个结点的有限集合。当n==0时，称为空树；任意一棵非空树满足以下两个条件：

  1. 有且只有一个特定的称为根（root）的结点；
  2. 当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树（Subtree）。

显然，树的定义是递归的。

其它所有的树都是在树的基本定义的基础上添加限制条件而得到的，他们都具有不同的特点，也因此有不同的用途；

树的表示形式：

  1. 树形图
  2. 嵌套图
  3. 凹凸表
  4. 广义表

树的几种基本存储方法：

  1. 双亲表示法
  2. 孩子表示法
  3. 双亲孩子表示法
  4. 孩子兄弟表示法

二叉树：

  1. 二叉树区分左子树、右子树，但是左右不分大小

二叉排序树：
它或者是一个空树，或者是具有如下性质的二叉树：

  1. 如果它的左子树不为空，则它的左子树的所有结点的值均小于其根结点的值
  2. 如果它的右子树不为空，则它的左子树的所有结点的值均大于其根结点的值
  3. 它的左右子树也分别为二叉排序树

用途： 二叉排序树的中序遍历是一个有序序列

二叉搜索树（也叫二叉查找树）：
很多地方把二叉搜索树与二叉排序树当成一个概念； 我觉得二叉搜索树应该是一个平衡二叉树，因为只有平衡才能保证搜索的最大时间复杂度为O(logn);
对于二叉排序树，在极端情况下（如斜树），查找的最坏的时间复杂度为O(n);

B-树：
B-树是一种平衡的多路查找树； 一棵m阶的B-树或为空树，或为满足下列特性的m叉树：

  1. 树中每个节点至多有m棵子树
  2. 若根结点不是叶子结点，则至少有两棵子树
  3. 除根结点之外的所有非终端结点至少有[m/2]棵子树
  4. 所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)其中Ki(i=1,…,n)为关键字，且Ki<Ki+1,(i=1,…,n-1); Ai(i=0,…,n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki(i=1,…,n),An所指子树中所有节点的关键字均大于Kn,n([m/2]-1)≤n≤m-1)为关键字的个数（或n+1为子树个数）。
  5. 所有的叶子结点都出现在同一层次上，并且不带信息（空指针）。

B+ 树：
B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是：

  1. 关键字个数和子树个数一样多
  2. 所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
  3. 所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字

键树：
键树（数字查找树）：是一棵度≥2的树，树中每个结点不是包含一个或几个关键字，而是只含有组成关键字的符号。如数值中的每一位，单词中的每个字母。

还需要了解的：
    红黑树、AVL(平衡二叉树）、Treap、伸展树 等。

本次学习从百度百科、百度文库中学到不少东西。

参考资料：
http://baike.baidu.com/view/593144.htm

数据结构基础知识

数据结构从某种角度（我也没想明白什么角度）可以分为：逻辑结构和存储结构。
逻辑结构基本分4类：

  1. 集合（Set）
  2. 线性结构， 如：数组、链表
  3. 树结构，如：B树、B-数、B+树
  4. 图结构，如： 有向图、无向图

存储结构基本分为4类：

  1. 顺序存储
  2. 链式存储
  3. 索引存储
  4. 哈希存储

关于稠密索引与稀疏索引：
如果一组数据元素在索引表中只对应一个索引项，则该索引称为稀疏索引；
如果每个数据元素在索引表中都有一个索引项，则该索引称为稠密索引；

参考资料：

http://www.2cto.com/database/201301/184440.html

http://blog.csdn.net/xymyeah/article/details/6407118

 

关于tokyocabinet的list操作

如果有多个进程同时对一个mdb(其它的没看，不敢随便乱说)执行list操作，结果会怎样； 或许你会显得当然地认为相互没有太大关系，至少我开始时这么认为的，但是在看源码的时候，发现有些不太对劲儿，我们先看一下源码：

tcutil.c

  1. /* Initialize the iterator of an on-memory hash database. */
  2. void tcmdbiterinit(TCMDB *mdb){
  3.   assert(mdb);
  4.   if(pthread_mutex_lock(mdb->imtx) != 0) return;
  5.   for(int i = 0; i < TCMDBMNUM; i++){
  6.     tcmapiterinit(mdb->maps);
  7.   }
  8.   mdb->iter = 0;
  9.   pthread_mutex_unlock(mdb->imtx);
  10. }

说明：
1. 在操作mdb的时候，需要给这个mdb加锁，显然这个mdb是一个全局的对象，而不是当前线程私有的，如果另有一个list请求，显然还是用同一个mdb对象，list时使用到了mdb的iter属性；由此看来，多个list请求应该是相互干扰的。下面做一个测试

1. 初始化一个mdb，不需要太多记录，假设200条记录吧
2. 先启动一个list进程，每取出一条记录sleep 100ms；
3. 1s后启动另一个list进程（前一个进程还没有list完成）
4. 这时，我们会发现进程1又重新获取了已经获取的记录，但不是全部，因为有部分被进程2读取了

下面是第一个进程或取的部分key:value
a4:a
a13:a
a22:a
a31:a
a39:a
a40:a
a48:a
a57:a
a66:a
a75:a
a13:a
a31:a
a40:a
a57:a
a75:a
a93:a
a112:a
a129:a
a138:a
a156:a

我们发现a13读取了两次； 第二次没有读取到a22， 是被第二个进程读取走了，然后就直接读取到了a31

————————
还有一个问题，我写入的时候是挨个按照顺序写入的，为什么list的时候有漏洞呢？或许你还发现一点，至少在一段内是从小到大的。

说明：
写入的时候，是按照不同的hash值写入到了8个map中的，而list的时候，是通过for循环8个map来list的，明白了？哦，好吧，that’s over。

tt的遍历时获取的条目数的计数器会记录到cnt_get 上面的。

关于tokyocabinet的memory db 的filesize与使用内存的关系

我使用tokyotyrant的方式如下：
/data1/tokyotyrant/bin/ttserver -host 10.10.10.111 -port 6789 -dmn -pid /data1/tokyotyrant_data/6789/6789.pid -le -uas -thnum 16 -log /data1/tokyotyrant_data/6789/6789.log -ulog /data1/tokyotyrant_data/6789/6789.ulog -sid 6789 -mhost 10.10.10.112 -mport 7890 -rts /data1/tokyotyrant_data/6789/6789.rts *

两项统计数据如下：
[root@localhost ~]# tcrmgr inform -port 6789 10.10.10.111
record number: 10470754
file size: 2014949218
[root@localhost ~]# tcrmgr inform -port 6789 -st 10.10.10.111 | grep rss
memrss  3826147328
[root@localhost ~]#

疑问：
存储的数据占用的内存大小file size为2G； 但是物理内存占用为3.8G； 我承认程序本身会占用一部分内存，100MB了不得了吧，那么其余的1.7G都做什么用了呢？

首先，通过看源码，得知，file size是通过存储的数据计算出来的，其中包括存储数据的数据结构占用的空间和key+value占用的空间。计算方式如下：

tcutil.c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/* Get the total size of memory used in a map object. */
uint64_t tcmapmsiz(const TCMAP *map){
assert(map);
return map->msiz + map->rnum * (sizeof(*map->first) + sizeof(tcgeneric_t)) +
map->bnum * sizeof(void *);
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
所以，即使没有一条记录，filesize也不会是0的； 默认的bnum为65672； 如果你的机器是32位的，则，0条记录时的filesize为： 65672 * 4 = 262688； 所以，如果你执行了vanish，发现filesize不为0 ，就不用奇怪了。

什么？ 在源码中没有找到 65672 ？ 哦，这个数字是这么来的：

tcutil.c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#define TCMDBMNUM      8                 // number of internal maps
#define TCMDBDEFBNUM   65536             // default bucket number
…
/* Create an on-memory hash database object. */
TCMDB *tcmdbnew(void){
  return tcmdbnew2(TCMDBDEFBNUM);
}

/* Create an on-memory hash database with specifying the number of the buckets. */
TCMDB *tcmdbnew2(uint32_t bnum){
  TCMDB *mdb;
  if(bnum < 1) bnum = TCMDBDEFBNUM;
  bnum = bnum / TCMDBMNUM + 17;
  TCMALLOC(mdb, sizeof(*mdb));
  TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);
  TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));
  TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);
  if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");
  for(int i = 0; i < TCMDBMNUM; i++){
    if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)
      tcmyfatal("rwlock error");
    mdb->maps = tcmapnew2(bnum);
  }
  mdb->iter = -1;
  return mdb;
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
说明:
 (65536 / 8 + 17 ) * 8 = 65672

关于tcmdb的实现基本都是在 tcutil.c 中的，难道说tcmdb原来是作为一个cache工具来实现的？

其它tcbdb tchdb都是定义在单独的文件中的，而tcmdb则是定义在 tcutil.h中的，而且tcmdb也完全是通过map来实现的。