APUE-数据库函数库

一、函数库

1、创建、关闭

1 DBHANDLE  db_open(const char *pathname, int oflag, .../* int mode */);/*成功返回数据库句柄，出错返回NULL*/
2 void      db_close(DBHANDLE);

　　若db_open成功返回，则建立两个文件：pathname.idx(索引文件)和pathname.dat(数据文件)。第二个参数指定文件的打开模式。若建立新数据库文件，mode将作为第三个参数传递给open。

　　若不再使用数据库时，调用db_close来关闭数据库。db_close将关闭索引文件和数据文件，并释放数据库使用过程中分配的所用于内部缓冲的存储空间。

2、存储

1 int db_store(DBHANDLE db, const char *key, const char *data, int flah);/*成功返回0，出错返回非0值*/

　　key和data是由null结束的字符串。可包含除null外的任何字符，如换行符。

　　flag参数取DB_INSERT(添加一条新记录)、DB_REPLACE（替换一条已有记录）或DB_STORE（加一条新记录或替换一条已有的记录，只要合适无论哪一种都可以）。

3、单条查询

1 char *db_fetch(DBHANDLE h, const char *key);/*成功返回指向数据的指针，记录未找到返回NULL*/

　　通过键key取出一条记录。

　　返回键key存放数据的指针。

1 /*
2  * Delete the specified record.
3  */
4 int db_delete(DBHANDLE h, const char *key);/*成功返回0，失败返回-1*/

4、遍历查询

1 void      db_rewind(DBHANDLE db);
2 char     *db_nextrec(DBHANDLE db, char *key);

　　可逐条记录访问数据库。调用db_rewind回滚到数据库第一条记录，然后循环调用db_nexterc，顺序读每条记录。

　　若key是非空指针，则db_nextrec将当前记录的键复制到key锁指向的存储区。

　　db_nextrec无法保存访问的次序。

二、实现概述

　　下图描述了索引文件和数据文件的结构。

　　空闲链表的作用：用于管理那些已删除的记录。因为已经分配了空间，当记录被删除后，空位还在，通过管理空闲链表，后面如果需要插入链表等操作，还可利用此空间。

　　下图中第一行0 53 35 0的结构对应于上图中最上面一行的格式。

　　0 10Alpha:0:6的解析如下：

0：下一条索引记录的偏移量（指针）

10：该索引记录剩余的长度

Alpha：键值

:：分隔符

0：数据记录的偏移量

6：数据记录长度

　　由下图可分析出第一条散列记录中第一条数据为gamma，第二条数据为Alpha。第二个散列表第一条记录为beta，且只有一条记录。

三、集中式或非集中式

　　1、集中式。由一个进程作为数据库管理者，所有数据库访问由此进程完成。其他进程通过IPC与此中心继承进行联系。

　　2、非集中式。每个库函数独立申请并发控制（加锁），然后自己调用I/O函数。

　　非集中式避免了使用IPC，会比集中式快一点。

　　集中式，中心数据库管理进程是唯一对数据文件进行I/O操作的进程。

　　集中式的优点，能根据需要对需求对操作模式进行调整，如对于不同的进程赋予不同的优先级。

　　集中式的另一个优点，复原更容易。所有状态信息都存储在一处，故恢复时，只需在该处识别出需要解决的未完成事务，然后恢复。

　　用户进程是合作进程，通过使用字节范围锁实现并发控制。

四、并发

　　1、粗锁

　　最简单的加锁是将两个文件的一个作为整个数据库的锁，并要去调用者在对数据库操作前必须获得这个锁，这种方式称为粗锁。

　　2、细锁

五、构造函数库

　　使用下面的命令构造一静态函数库。

1 gcc -I../include -Wall -c db.c
2 ar rsv libapue_db.a db.o

　　添加libapue.a链接，同事构建动态共享库版本

1 gcc -I../include -Wall -fPIC -c db.c
2 gcc -shared -W1, -soname, libapue_db.so.1 -o libapue_db.so.1 -L../lib -lapue -lc db.o

　　libapue_db.so.1需放在动态链接/装入程序（dynamic linker/loader）能找到的公用目录。另一个方法：将共享库放置在私有目录，修改LD_LIBRARY_PATH环境变量，即可动态链接/装入程序的搜索路径包含此私有目录。

六、源代码

 1 /*
 2  * Library's private representation of the database.
 3  */
 4 typedef struct {
 5   int    idxfd;  /* fd for index file */
 6   int    datfd;  /* fd for data file */
 7   char  *idxbuf; /* malloc'ed buffer for index record */
 8   char  *datbuf; /* malloc'ed buffer for data record*/
 9   char  *name;   /* name db was opened under */
10   
11   /*索引文件中当前记录的偏移量*/
12   /*键的位置=idxoff + PTR_SZ + IDXLEN_SZ */
13   off_t  idxoff; /* offset in index file of index record */
14                   /* key is at (idxoff + PTR_SZ + IDXLEN_SZ) */
15                   
16   /*索引记录长度*/
17   /*不包括IDXLEN_SZ长度域的长度，包含换行符*/
18   size_t idxlen; /* length of index record */
19                   /* excludes IDXLEN_SZ bytes at front of record */
20                   /* includes newline at end of index record */
21   /*数据记录在数据文件中的偏移量*/
22   off_t  datoff; /* offset in data file of data record */
23   /*数据记录长度，包含末尾换行符*/
24   size_t datlen; /* length of data record */
25                   /* includes newline at end */
26                   
27   /*包含在散列链中下一条索引项的偏移量*/
28   off_t  ptrval; /* contents of chain ptr in index record */
29   
30   /*指向这个索引记录的链表指针偏移量*/
31   off_t  ptroff; /* chain ptr offset pointing to this idx record */
32   
33   /*索引记录中哈希链表中的位置，及散列表中的链表指针位置*/
34   /*在散列链中的起始地址*/
35   off_t  chainoff; /* offset of hash chain for this index record */
36   
37   /*索引文件中哈希表的偏移量?*/
38   off_t  hashoff;  /* offset in index file of hash table */
39 
40   /*当前哈希表大小*/
41   DBHASH nhash;    /* current hash table size */
42 
43   /*用于数据操作统计*/
44   COUNT  cnt_delok;    /* delete OK */
45   COUNT  cnt_delerr;   /* delete error */
46   COUNT  cnt_fetchok;  /* fetch OK */
47   COUNT  cnt_fetcherr; /* fetch error */
48   COUNT  cnt_nextrec;  /* nextrec */
49   COUNT  cnt_stor1;    /* store: DB_INSERT, no empty, appended */
50   COUNT  cnt_stor2;    /* store: DB_INSERT, found empty, reused */
51   COUNT  cnt_stor3;    /* store: DB_REPLACE, diff len, appended */
52   COUNT  cnt_stor4;    /* store: DB_REPLACE, same len, overwrote */
53   COUNT  cnt_storerr;  /* store error */
54 } DB;

 1 /*
 2  * Open or create a database.  Same arguments as open(2).
 3  */
 4 DBHANDLE
 5 db_open(const char *pathname, int oflag, ...)
 6 {
 7     DB            *db;
 8     int            len, mode;
 9     size_t        i;
10     char        asciiptr[PTR_SZ + 1],
11                 hash[(NHASH_DEF + 1) * PTR_SZ + 2];
12                     /* +2 for newline and null */
13     struct stat    statbuff;
14 
15     /*
16      * Allocate a DB structure, and the buffers it needs.
17      */
18     len = strlen(pathname);
19     if ((db = _db_alloc(len)) == NULL)/*分配一个db结构，初始化它的缓冲区*/
20         err_dump("db_open: _db_alloc error for DB");
21 
22     db->nhash   = NHASH_DEF;/* hash table size 137 */
23     db->hashoff = HASH_OFF;    /* offset in index file of hash table 7 */
24     strcpy(db->name, pathname);
25     strcat(db->name, ".idx");
26     if (oflag & O_CREAT) {
27         /*获取可变参数内容*/
28         va_list ap;
29 
30         va_start(ap, oflag);
31         mode = va_arg(ap, int);
32         va_end(ap);
33 
34         /*
35          * Open index file and data file.
36          */
37         db->idxfd = open(db->name, oflag, mode);
38         strcpy(db->name + len, ".dat");
39         db->datfd = open(db->name, oflag, mode);
40     } else {
41         /*
42          * Open index file and data file.
43          */
44         db->idxfd = open(db->name, oflag);
45         strcpy(db->name + len, ".dat");
46         db->datfd = open(db->name, oflag);
47     }
48 
49     if (db->idxfd < 0 || db->datfd < 0) {
50         _db_free(db);
51         return(NULL);
52     }
53     if ((oflag & (O_CREAT | O_TRUNC)) == (O_CREAT | O_TRUNC)) {
54         /*
55          * If the database was created, we have to initialize
56          * it.  Write lock the entire file so that we can stat
57          * it, check its size, and initialize it, atomically.
58          */
59         if (writew_lock(db->idxfd, 0, SEEK_SET, 0) < 0)
60             err_dump("db_open: writew_lock error");
61 
62         if (fstat(db->idxfd, &statbuff) < 0)
63             err_sys("db_open: fstat error");
64 
65         if (statbuff.st_size == 0) {
66             /*
67              * We have to build a list of (NHASH_DEF + 1) chain
68              * ptrs with a value of 0.  The +1 is for the free
69              * list pointer that precedes the hash table.
70              */
71             sprintf(asciiptr, "%*d", PTR_SZ, 0);
72             hash[0] = 0;
73             for (i = 0; i < NHASH_DEF + 1; i++)
74                 strcat(hash, asciiptr);
75             strcat(hash, "
");
76             i = strlen(hash);
77             if (write(db->idxfd, hash, i) != i)
78                 err_dump("db_open: index file init write error");
79         }
80         if (un_lock(db->idxfd, 0, SEEK_SET, 0) < 0)
81             err_dump("db_open: un_lock error");
82     }
83     db_rewind(db);
84     return(db);
85 }

 1 /*
 2  * Fetch a record.  Return a pointer to the null-terminated data.
 3  */
 4 char *
 5 db_fetch(DBHANDLE h, const char *key)
 6 {
 7     DB      *db = h;
 8     char    *ptr;
 9 
10     /*查询是否存在，存在，则置db结构中相关数据*/
11     if (_db_find_and_lock(db, key, 0) < 0) {
12         ptr = NULL;                /* error, record not found */
13         db->cnt_fetcherr++;
14     } else {
15         /*根据前面查询结果，读取查询到的记录。*/
16         ptr = _db_readdat(db);    /* return pointer to data */
17         db->cnt_fetchok++;
18     }
19 
20     /*
21      * Unlock the hash chain that _db_find_and_lock locked.
22      */
23     if (un_lock(db->idxfd, db->chainoff, SEEK_SET, 1) < 0)
24         err_dump("db_fetch: un_lock error");
25     return(ptr);
26 }

 1 /*
 2  * Find the specified record.  Called by db_delete, db_fetch,
 3  * and db_store.  Returns with the hash chain locked.
 4  */
 5 static int
 6 _db_find_and_lock(DB *db, const char *key, int writelock)
 7 {
 8     off_t    offset, nextoffset;
 9 
10     /*
11      * Calculate the hash value for this key, then calculate the
12      * byte offset of corresponding chain ptr in hash table.
13      * This is where our search starts.  First we calculate the
14      * offset in the hash table for this key.
15      */
16      /*计算此键的哈希值，然后计算哈希表中相应链ptr的字节偏移量。
17      这是我们搜索开始的位置。 首先，我们计算此密钥的哈希表中的偏移量。*/
18      /*db->chainoff：散列表指针的位置，即第几个链表指针。找到对应key的链表指针*/
19     db->chainoff = (_db_hash(db, key) * PTR_SZ) + db->hashoff;
20     db->ptroff = db->chainoff;
21     
22     printf("db->chainoff:%p
",db->chainoff);
23 
24     /*
25      * We lock the hash chain here.  The caller must unlock it
26      * when done.  Note we lock and unlock only the first byte.
27      */
28      /*锁定哈希链表，只锁定第一个字节，可最大程度增加并发性*/
29     if (writelock) {
30         if (writew_lock(db->idxfd, db->chainoff, SEEK_SET, 1) < 0)
31             err_dump("_db_find_and_lock: writew_lock error");
32     } else {
33         if (readw_lock(db->idxfd, db->chainoff, SEEK_SET, 1) < 0)
34             err_dump("_db_find_and_lock: readw_lock error");
35     }
36 
37     /*
38      * Get the offset in the index file of first record
39      * on the hash chain (can be 0).
40      */
41      /*取到索引文件中第一条记录的偏移量（指针）*/
42      /**通过散列表中查到的偏移量（指针），找到索引记录中的第一个元素（链表指针），
43      及下一条记录的（偏移量）指针，0代表是最后一条记录*/
44     offset = _db_readptr(db, db->ptroff);
45     while (offset != 0) {
46 
47         /*此函数返回下一条索引记录的指针，同时，如果查询到记录数据内容，
48         则填充db结构中，数据记录的信息*/
49         nextoffset = _db_readidx(db, offset);
50         if (strcmp(db->idxbuf, key) == 0)
51             break;       /* found a match 找到匹配，退出查询 */
52         /*准备下一次循环查询工作*/
53         db->ptroff = offset; /* offset of this (unequal) record */
54         offset = nextoffset; /* next one to compare */
55     }
56     /*
57      * offset == 0 on error (record not found).
58      */
59     return(offset == 0 ? -1 : 0);
60 }

 1 /*
 2  * Read the next index record.  We start at the specified offset
 3  * in the index file.  We read the index record into db->idxbuf
 4  * and replace the separators with null bytes.  If all is OK we
 5  * set db->datoff and db->datlen to the offset and length of the
 6  * corresponding data record in the data file.
 7  */
 8  /*读下一条索引记录。从索引文件中指定的偏移位置开始。将索引记录内容
 9  读到db->idxbuf中，并用null替换分隔符。如果所有正常，将用对应数据文
10  件中的数据数据记录的偏移量和长度设置db->datoff和db->datlen。 */
11  /*单条索引记录结构:链表指针(7)+索引记录长度(4)+键值+:+数据记录偏移+:+数据记录长度*/
12 static off_t
13 _db_readidx(DB *db, off_t offset)
14 {
15     ssize_t                i;
16     char            *ptr1, *ptr2;
17     char            asciiptr[PTR_SZ + 1], asciilen[IDXLEN_SZ + 1];
18     struct iovec    iov[2];
19 
20     /*
21      * Position index file and record the offset.  db_nextrec
22      * calls us with offset==0, meaning read from current offset.
23      * We still need to call lseek to record the current offset.
24      */
25      /*索引文件和记录的位置偏移。db_nextrec调用此函数时offset==0,
26      意味着从当前的位置开始读。我们仍需要调用lseek来记录当前的偏移。*/
27      /*db->idxoff:索引文件中当前记录偏移量。*/
28     if ((db->idxoff = lseek(db->idxfd, offset,
29       offset == 0 ? SEEK_CUR : SEEK_SET)) == -1)
30         err_dump("_db_readidx: lseek error");
31 
32     /*
33      * Read the ascii chain ptr and the ascii length at
34      * the front of the index record.  This tells us the
35      * remaining size of the index record.
36      */
37     iov[0].iov_base = asciiptr;
38     iov[0].iov_len  = PTR_SZ;
39     iov[1].iov_base = asciilen;
40     iov[1].iov_len  = IDXLEN_SZ;
41     if ((i = readv(db->idxfd, &iov[0], 2)) != PTR_SZ + IDXLEN_SZ) {
42         if (i == 0 && offset == 0)
43             return(-1);        /* EOF for db_nextrec */
44         err_dump("_db_readidx: readv error of index record");
45     }
46 
47     /*
48      * This is our return value; always >= 0.
49      */
50      /*当前索引记录的首字段*/
51     asciiptr[PTR_SZ] = 0;        /* null terminate */
52     db->ptrval = atol(asciiptr); /* offset of next key in chain */
53 
54     /*当前索引记录的长度*/
55     asciilen[IDXLEN_SZ] = 0;     /* null terminate */
56     if ((db->idxlen = atoi(asciilen)) < IDXLEN_MIN ||
57       db->idxlen > IDXLEN_MAX)
58         err_dump("_db_readidx: invalid length");
59 
60     /*
61      * Now read the actual index record.  We read it into the key
62      * buffer that we malloced when we opened the database.
63      */
64      /*读取索引记录内容，存储到了db->idxbuf中*/
65     if ((i = read(db->idxfd, db->idxbuf, db->idxlen)) != db->idxlen)
66         err_dump("_db_readidx: read error of index record");
67     if (db->idxbuf[db->idxlen-1] != NEWLINE)    /* sanity check */
68         err_dump("_db_readidx: missing newline");
69     db->idxbuf[db->idxlen-1] = 0;     /* replace newline with null */
70 
71     /*
72      * Find the separators in the index record.
73      */
74      /*ptr1:指针指向键值*/
75     if ((ptr1 = strchr(db->idxbuf, SEP)) == NULL)
76         err_dump("_db_readidx: missing first separator");
77     *ptr1++ = 0;                /* replace SEP with null */
78     /*指针指向数据记录偏移*/
79     if ((ptr2 = strchr(ptr1, SEP)) == NULL)
80         err_dump("_db_readidx: missing second separator");
81     *ptr2++ = 0;                /* replace SEP with null */
82 
83     if (strchr(ptr2, SEP) != NULL)
84         err_dump("_db_readidx: too many separators");
85 
86     /*
87      * Get the starting offset and length of the data record.
88      */
89      /*将解析到的数据记录信息填充到db结构中*/
90     if ((db->datoff = atol(ptr1)) < 0)
91         err_dump("_db_readidx: starting offset < 0");
92     if ((db->datlen = atol(ptr2)) <= 0 || db->datlen > DATLEN_MAX)
93         err_dump("_db_readidx: invalid length");
94     return(db->ptrval);        /* return offset of next key in chain */
95 }

 1 /*
 2  * Delete the current record specified by the DB structure.
 3  * This function is called by db_delete and db_store, after
 4  * the record has been located by _db_find_and_lock.
 5  */
 6  /*删除db结构中的当前记录。
 7  此函数需要记录被_db_find_and_lock函数定位后，被调用*/
 8 static void
 9 _db_dodelete(DB *db)
10 {
11     int        i;
12     char    *ptr;
13     off_t    freeptr, saveptr;
14 
15     /*
16      * Set data buffer and key to all blanks.
17      */
18      /*将数据缓存区置为空格*/
19     for (ptr = db->datbuf, i = 0; i < db->datlen - 1; i++)
20         *ptr++ = SPACE;
21     *ptr = 0;    /* null terminate for _db_writedat */
22     /*清索引记录*/
23     ptr = db->idxbuf;
24     while (*ptr)
25         *ptr++ = SPACE;
26 
27     /*
28      * We have to lock the free list.
29      */
30      /*锁定空闲链表，因为要将删除记录移到空闲链表上*/
31     if (writew_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
32         err_dump("_db_dodelete: writew_lock error");
33 
34     /*
35      * Write the data record with all blanks.
36      */
37      /*将一个数据记录写为空白*/
38     _db_writedat(db, db->datbuf, db->datoff, SEEK_SET);
39 
40     /*
41      * Read the free list pointer.  Its value becomes the
42      * chain ptr field of the deleted index record.  This means
43      * the deleted record becomes the head of the free list.
44      */
45      /*读空闲链表指针*/
46     freeptr = _db_readptr(db, FREE_OFF);
47 
48     /*
49      * Save the contents of index record chain ptr,
50      * before it's rewritten by _db_writeidx.
51      */
52      /*保存索引记录首项，即下条记录的指针*/
53     saveptr = db->ptrval;
54 
55     /*
56      * Rewrite the index record.  This also rewrites the length
57      * of the index record, the data offset, and the data length,
58      * none of which has changed, but that's OK.
59      */
60      /*重写索引记录，重写索引记录长度，数据偏移，数据长度*/
61      /*idxbuf和idxoff已经被清空*/
62     _db_writeidx(db, db->idxbuf, db->idxoff, SEEK_SET, freeptr);
63 
64     /*
65      * Write the new free list pointer.
66      */
67      /*将索引记录的首项数据写到空闲链表*/
68     _db_writeptr(db, FREE_OFF, db->idxoff);
69 
70     /*
71      * Rewrite the chain ptr that pointed to this record being
72      * deleted.  Recall that _db_find_and_lock sets db->ptroff to
73      * point to this chain ptr.  We set this chain ptr to the
74      * contents of the deleted record's chain ptr, saveptr.
75      */
76      /*重写指向该删除记录的链表指针。重新调用_db_find_and_lock设置
77      db->ptroff指向该链表指针。设置链表指针指向删除的记录链表指针内容，
78      下条记录的指针。*/
79     _db_writeptr(db, db->ptroff, saveptr);
80     if (un_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
81         err_dump("_db_dodelete: un_lock error");
82 }

七、性能

　　通过比较在单进程和多进程下，采用不同的加锁方式下，用户时间、系统时间的消耗程度来比较数据库性能。