APUE-数据库函数库

妖狐艹你老母 2021-12-21 11:57 188阅读 0赞

一、函数库

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无法保存访问的次序。

**二、实现概述**

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

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

![520820-20181218150412109-1634061993.png][]

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

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

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

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

Alpha：键值

:：分隔符

0：数据记录的偏移量

6：数据记录长度

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

![520820-20181218150431007-1153191982.png][]

**三、集中式或非集中式**

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, "\n");
    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\r\n",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 }

**七、性能**

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

转载于:https://www.cnblogs.com/mofei004/p/10135315.html

[520820-20181218150412109-1634061993.png]: /images/20211220/d3fc57d35dbb41e794d4140485956800.png
[520820-20181218150431007-1153191982.png]: /images/20211220/b21bc373e621493b80d3b3e02f39db31.png