a database library 我会说明天上午十点考数据库,我现在还在写博客... 什么心态 qaq 我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想) --------------------------------------------------------------------------------------------
 a database library
我会说明天上午十点考数据库,我现在还在写博客... 什么心态 qaq
我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想)
----------------------------------------------------------------------------------------------------------------
正题... 之前一直搁置了 apue的后面几章, 明天考数据库, 今天心血来潮, 反正apue提供了实现一个数据的思路,
不妨我们自己写一个数据库. 哼╭(╯^╰)╮ 就是这么傲娇~
名字我的都想好了, 数据库的名字就叫 ..... jasper.
声明: 这个数据库不是我原创的(k神作品, 我完全... 不是一个数量级的),我会对其进行稍稍的改动...
先摆结果吧，有兴趣就看下去，也可以和我一起讨论，jasonleaster@gmail.com，没兴趣，浏览器点击x.
本来是想像很正规的成熟数据库那样，搭个shell出来的，感觉交互界面的字符串语法命令的分析有点＊＊
于是，就这样凑合着先表示概念吧～　想测试或者使用这个＂玩具＂数据库，需要一定的ｃ语言基础，然后调用提供好的api即可．
为了能够操作数据库，我们必须写个简单的调用程序～
#include apue_db.h#include #include #define string_sz 100#define data_set 3int main(){ char str_key[data_set][string_sz] = { {alpha}, {belta}, {gama} }; char str_dat[data_set][string_sz] = { {data1}, {data2}, {data3} }; dbhandle handler = db_open(./database, o_creat | o_trunc | o_rdwr, file_mode); if(db_store(handler,str_key[0],str_dat[0],db_insert) != 0) { printf(error! db_store failed in function %s\n, __function__); printf(trying to store key:%s\t data:%s\n, str_key[0],str_dat[0]); goto failed; } if(db_store(handler,str_key[1],str_dat[1],db_insert) != 0) { printf(error! db_store failed in function %s\n, __function__); printf(trying to store key:%s\t data:%s\n, str_key[1],str_dat[1]); goto failed; } if(db_store(handler,str_key[2],str_dat[2],db_insert) != 0) { printf(error! db_store failed in function %s\n, __function__); printf(trying to store key:%s\t data:%s\n, str_key[2],str_dat[2]); goto failed; }failed: db_close(handler); return 0;}
显然,我们想利用db_store来根据str_key来储存str_dat里面的数据
就这样把数据储存在了database.dat中，并且利用database.idx　进行索引
当然，我想看我啰啰嗦嗦写到这里的人是想看怎么实现的．．．
特地用分割线划开了．下面主要是个人的想法，或者遇到的个人觉得可能是难点的地方．
并不是＂介绍如何搞定这个数据库＂．　rtfsc ：）
有任何对这个数据有兴趣的viewer，　希望能通过邮箱交流jasonleaster@gmail.com
don't panic 
-------------------------------------------------------------------------------------------------------------------
如果觉得书上的代码风格不和口味，可以试试，去github拿我自己重新写的源代码
不懂的地方再对照书上的注释看就是了
https://github.com/jasonleaster/apue_study_source_code/tree/liu/chapter_20
数据库的设计:
这个简易的数据库由两个文件构成---- index file & data file.
一个索引文件,一个数据文件. 实现索引和储存的数据进行分离. 在我个人看来, 这样做无非是让构架看得清晰.
试想,用一个文件来表述数据库的话,会很乱, 冗长, 杂. do you think so ? : ) 不得不佩服这些设计者的思想.
图1
最最值得强调的就是, 我们在储存地址指针的时候, 即图中你所看到所有有关ptr的标识符.
 他们的储存形式都是ascii码! 再三强调, 不然看代码会看哭的.
这是数据库设计的一大亮点,由于数据库的数据可能会被用在不同的系统,不同的硬件平台上面, 会由于系统表示数据的方式不同(大小端, 指针长度,等), 而导致数据可能不一致. 这时候有个办法,直接用ascii码表示,以字符串的形式存在.
比方说地址 0x0010 就直接用 16来表示和储存.简直酷帅....
设计者假设了指针的最大长度为十进制的6位数.
图2
那个999999 == 10^(ptr_sz) - 1
对于数据库可以进行的哪些操作,定义了以下api. (之后我会写一个类似于shell的东东, 使得控制这个数据库的语法像mysql的语法,肯定不会是完全实现mysql的语法,但是会很naive 很有意思, 这样以来, 最起码简单数据库的实现原理就明白了, 专杀纸老虎).
图3
用结构体db , 对整个数据库进行抽象. 我们所有的api,不过是围绕这个对象打转转而已, 变着花样操作这个database.
我们把所有能用来描述一个数据库的东东,都写到这个结构体里面了, 这种思想的本质就是oo.
/* * library's private representation of the database. */typedef struct { int idxfd; /* fd for index file */ int datfd; /* fd for data file */ char *idxbuf; /* malloc'ed buffer for index record */ char *datbuf; /* malloc'ed buffer for data record*/ char *name; /* name db was opened under */ off_t idxoff; /* offset in index file of index record */ /* key is at (idxoff + ptr_sz + idxlen_sz) */ size_t idxlen; /* length of index record */ /* excludes idxlen_sz bytes at front of record */ /* includes newline at end of index record */ off_t datoff; /* offset in data file of data record */ size_t datlen; /* length of data record */ /* includes newline at end */ off_t ptrval; /* contents of chain ptr in index record */ off_t ptroff; /* chain ptr offset pointing to this idx record */ off_t chainoff; /* offset of hash chain for this index record */ off_t hashoff; /* offset in index file of hash table */ dbhash nhash; /* current hash table size */ count cnt_delok; /* delete ok */ count cnt_delerr; /* delete error */ count cnt_fetchok; /* fetch ok */ count cnt_fetcherr; /* fetch error */ count cnt_nextrec; /* nextrec */ count cnt_stor1; /* store: db_insert, no empty, appended */ count cnt_stor2; /* store: db_insert, found empty, reused */ count cnt_stor3; /* store: db_replace, diff len, appended */ count cnt_stor4; /* store: db_replace, same len, overwrote */ count cnt_storerr; /* store error */} db;
之前图3定义了很多操作db的api,那么我们来一个个看这些api的实现.
上面的图3的api实现以来下面这些函数. 提一次深刻的体会到什么叫做接口与实现的分离...以后我也要这么干
图4
代码接近10^3 所以不一一拿出来扯了. 记录我觉得关键的部分吧
db_open(const char *pathname, int oflag, ...)
图5
根据pathname提供的文件名, 计算文件名的字符串长度(不包括nul)
然后传递给_db_alloc(len), 这个_db_alloc会真正的返回一个db结构体和我们的文件名pathname所指字符相关联.
图6
这里我们得到了初始的数据库之后,就开始初始化它, 确定好hash table在index file中的起始位置(hash_off 6)以及hash table总的大小(nhash_def 137), 这里的6 就是前面的ptr_sz, 也就是说 index file的前6 byte是空出来的.
,每个hash 单元是ptr_sz大小,一共有 nhash_def个. 前面空出来的6bybe是故意的, 用来记录一个指针(用字符串表示的). 这个指针用法很特别, 后面会讲明白的, 叫free list pointer(这家伙折腾我好久).
_db_alloc会注意到这里 malloc有分别的+ 5 , 2, 2. 这是因为db->name的时候要考虑 我们的数据库文件命名方式,要添加.dat
于是这里.dat 就是5个char. 然后后面两个+2 是考虑到字符串输入的时候我们会带有 \n 和 nul.
这确保了我们定义idxlen_max 和 datlen_max的严谨性!
图7
db_close 和_db_free() 感觉都很简单,只是apue作者实现的时候有点略微..稍微.. 不安全.
api参数的指针没有进行null检测.
图8
万一db 是null 就跪的稳稳的了
db_fetch() 该函数用来根据key查找数据库中是否已经有了该项数据.
没什么值得强调的,这就是个接口, 成功找到了对应数据, ok.那返回一个指针ptr,
这个指针指向要查找的数据(指向data file)
接口的核心在于_find_and_lock()
_find_and_lock()根据key指向的字符串,计算hash值, 然后确定hash表的入口,尝试找到对应项.
第三个参数,writelock, 旨在提供防止并发是带来的抢占问题.
read_lock 保证仅可读不可写, write_lock 既不可读也不可写.
图9
上面也看到了, db->chainoff 通过hash加上初始的hash table的起始偏置得到.
根据chianoff通过_db_readptr去找hash table 对应位置的数据,这个数据就是index的地址标记.
如果这个地址为0, while循环进不去, 最后返回-1, 提示_find_and_lock失败,就是说, 根据参数key,没有对应的数据.
如果offset非零,说明我们有可能找到了对应的数据.
只有真正一个个比对key ,而不是简单的hash值相同. 才可以判定找到了对应数据.
如果找到了,那么break 跳出while循环, 返回0. 提示我们找到这家伙了.
如果沿着hash chian的单向链表一直没找到,我们就会遇到_db_readidx返回0, 提示_find_and_lock失败.
图10
值得注意的是图10会有调用_db_readidx()
这个函数会更新data file的文件偏置,即db->datoff.
后记:
          本来以为一天可以搞定的，磨磨蹭蹭搞了两天这东西......
摄于某教室　极力的试图通过空旷的场景和黑白的沉闷，表现当代高校学生的迷茫，无从与困惑