Tar实现

Question

为了教育目的，我编写了一个tar实现，我从从tar文件中读取并打印文件内容开始。

我使用递归获取下一个tar头，并在googled上搜索“何时使用递归？”在彼得·伯恩斯所说的这岗位上着陆：

语言实现者可以使用一种称为尾调用优化的技术来消除某些类型的堆栈溢出。简单地说:如果一个函数的返回表达式只是函数调用的结果，那么您不需要在堆栈中添加一个新的级别，您可以为被调用的函数重用当前的级别。遗憾的是，很少有命令式语言实现内置了尾叫优化。

他的意思是语言实施者，还是我也能用呢？

当我被告知要添加完整的代码时，我将添加我现在得到的内容。这并不是什么原因，因为这是我第一次使用标准化的格式，我首先希望能够读取每一个标题并得到正确的偏移量，因为tar pads将内容添加到下一个更大的块中。

它只适用于只包含文件的tar文件。如果我理解得更多，我将实现所有其他类型的类型。

就像我们已经问过的。关于尾递归和上面的引号，tar_getNextHeader()函数设计得不好吗？

我想提高我对结构和定义的命名技巧，因为我认为有些结构和定义没有很好的命名。

另外，如果你看到一些我能做得更好或者不应该做/使用的事情，请告诉我。

tar.h:

#ifndef _TAR_H    // BEGIN INCLUDE GUARD
#define _TAR_H

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/

typedef struct tar tar;

/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

tar* tar_load(const char *filename);
void tar_print(tar *tar);

#endif

tar.c:

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "tar.h"
#include "tar_internal.h"

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/



/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

/**
 * @brief Loads a tar file and parses/allocates included headers
 * NOTE: check for errno after calling
 * 
 * @param path path to tar file
 * @retval tar* on success
 * @retval NULL on failure 
 */
tar* tar_load(const char *path)
{
    struct stat fi;
    if(stat(path, &fi) != 0) {
        return NULL;
    }

    tar *tar = malloc(sizeof *tar);
    if(tar == NULL) {
        return NULL;
    }

    tar->size = fi.st_size;
    tar->filename = path;

    tar->fd = open(path, O_RDONLY);
    if(tar->fd == -1) {
        free(tar);
        return NULL;
    }

    tar->files = tar_getNextHeader(tar);

    return tar;
}

/**
 * @brief Prints file content (for testing purposes)
 * 
 * @param tar 
 */
void tar_print(tar *tar)
{
    lseek(tar->fd, 0, SEEK_SET);

    tar_entry *current = tar->files;

    while(current) {
        lseek(tar->fd, current->offset, SEEK_SET);
        char buffer[512];
        if(read(tar->fd, buffer, current->size) == 0) {
            printf("EOF\n");
            return;
        }

        printf("File: %s\n", current->header.filename);
        printf("Content:\n%s\n\n", buffer);

        current = current->next;
    }

}

tar_internal.h:

#ifndef _TAR_INTERNAL_H    // BEGIN INCLUDE GUARD
#define _TAR_INTERNAL_H

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include <errno.h>

#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <dirent.h>


/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/


#define NORMAL_FILE '0'
#define HARD_LINK '1'
#define SYMBOLIC_LINK '2'
#define CHARACTER_SPECIAL '3'
#define BLOCK_SPECIAL '4'
#define DIRECTORY '5'
#define FIFO '6'
#define CONTIGUOUS_FILE '7'
#define GLOBAL_EXTENDET_HEADER 'g'
#define EXTENDED_HEADER 'x'


/*

*/
#define TAR_BLOCKSIZE 512
#define USTAR "ustar"


typedef struct tar_header {
    union {
        struct {
            char filename[100];
            char mode[8];
            char uid[8];
            char gid[8];
            char size[12];
            char mtime[12];
            char chksum[8];
            char type;
            char link_filename[100];
            char magic[6];
            char version[2];
            char owner[32];
            char group[32];
            char devicemajor[8];
            char deviceminor[8];
            char prefix[155];
        };
        char padding[TAR_BLOCKSIZE];
    };
} tar_header;

typedef struct tar_entry {
    struct tar_entry *next;
    const char *filename;
    off_t offset;
    size_t size;
    tar_header header;
} tar_entry;

typedef struct tar {
    const char *filename; // tar filename
    size_t size; // tar file size
    tar_entry *files; // linked list
    size_t fd;
} tar;

/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

size_t RoundUpBlock(size_t size, size_t blksz);

/*********************************************************************************************************/
/*                                           TAR HEADER INTERFACE                                        */
/*********************************************************************************************************/
bool tar_header_isUstar(tar_header *header);
void tar_header_setEmpty(tar_header *header);
bool tar_header_isDirectory(tar_header *header);
bool tar_header_isRegFile(tar_header *header);
bool tar_header_isLongName(tar_header *header);
bool tar_header_isLongLink(tar_header *header);
size_t tar_header_getSize(tar_header *header);
void tar_header_getPath(tar_header *header, char *path_buf, size_t len);


/*********************************************************************************************************/
/*                                             TAR FILE INTERFACE                                        */
/*********************************************************************************************************/

tar_entry* tar_getNextHeader(tar *tar);
int tar_skipFileContent(tar *tar, size_t filesz);

#endif

tar_internal.c:

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include "tar.h"
#include "tar_internal.h"

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/



/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

bool tar_header_isUstar(tar_header *header)
{
    return ( strncmp(header->magic, USTAR, sizeof(USTAR)-1) == 0 );
}

size_t RoundUpBlock(size_t size, size_t blksz)
{
    size_t result = size % blksz;
    if( result == size ) {
        return blksz;
    }
    else if( result == 0 ) {
        return result;
    }

    return (size / blksz + 1) * blksz;
}

void tar_header_setEmpty(tar_header *head)
{
    memset(head->padding, 0, TAR_BLOCKSIZE);
}

bool tar_header_isDirectory(tar_header *head)
{
    return head->type == DIRECTORY;
}

bool tar_header_isRegFile(tar_header *head)
{
    return head->type == NORMAL_FILE;
}

/*
 always check errno for error after this call
*/
size_t tar_header_getSize(tar_header *head)
{
    return strtoul(head->size, NULL, 8);
}


/**
 * @brief skips the file content inside file and jumps to the next header
 * 
 * @param tar tar*
 * @param filesz size of file of the current header
 * @retval -1 on failure
 * @retval current offset in file in bytes 
 */
int tar_skipFileContent(tar *tar, size_t filesz)
{
    off_t curpos = lseek(tar->fd, 0, SEEK_CUR);
    size_t roundup = RoundUpBlock(filesz, TAR_BLOCKSIZE);

    if(curpos == -1) {
        return -1;
    }

    if(curpos + roundup > tar->size) {
        printf("DEBUG: TAR OVERREAD!!!\n");
        return -1;
    }

    if(lseek(tar->fd, roundup, SEEK_CUR) == -1) {
        return -1;
    }

    return curpos;
}

/**
 * @brief Recusive call to fill the linked list of entries
 * NOTE: alway check errno for this call. if errno == 0, and NULL is returned then EOF is reached, otherwise an error occured
 * NOTE: this function checks for ustar magic string to skip 0-byte sequences at the end of file, it does not work for tar files using the old standard
 * @param tar 
 * @retval NULL on failure (EOF or error while read)
 * @retval tar_entry *
 */
tar_entry* tar_getNextHeader(tar *tar)
{
    tar_entry *entry = malloc(sizeof *entry);
    if(entry == NULL) {
       return NULL;
    }

    size_t ret = read(tar->fd, &entry->header, TAR_BLOCKSIZE);
    if(ret == 0 || ret == -1) {
       goto CLEANUP;
    }

    if(!tar_header_isUstar(&entry->header)) {
       goto CLEANUP;
    }

    entry->size = tar_header_getSize(&entry->header);
    if(errno) {
        perror("tar_getNextHeader()->tar_header_getSize()");
        goto CLEANUP;
    }

    entry->offset = tar_skipFileContent(tar, entry->size);
    if(entry->offset == -1) {
        goto CLEANUP;
    }

    entry->next = tar_getNextHeader(tar);
    if(errno) {
        perror("tar_getNextHeader()->tar_getNextHeader()");
        return NULL;
    }
    return entry;

    CLEANUP:
    free(entry);
    return NULL;
}

Answer 1

这里的递归不是尾递归。

尾调用是指在被调用函数的返回和调用函数的返回之间不需要进一步处理的情况(这意味着当前函数可以被调用函数替换，而不是创建新的堆栈框架)。

在C语言中，看起来就像

return other_function(/*...*/);

或(对于不返回值的函数)

other_function(/*...*/);
return;

其他任何事情都不是尾递归。

例如，这个阶乘函数不是尾递归函数：

unsigned int fact(unsigned int n)
{
    if (!n) return 1;
    return n * fact(n-1);
}

尾递归实现如下所示：

static unsigned int fact_acc(unsigned int n, unsigned int accumulated)
{
    if (!n) return accumulated;
    return fact_acc(n-1, accumulated * n);
}

unsigned int fact(unsigned int n)
{
    return fact_acc(n, 1);
}

无论如何，C并不要求以这种方式优化尾调用:一些编译器将保存堆栈，而有些编译器则不会(在这里，不同的编译器很可能是同一个编译器程序，但使用不同的参数调用！)