2021q1 Homework2 (quiz2)

contributed by < XDEv11 >

GitHub
第 2 週測驗題

測驗 1

程式碼解說

透過 __extension__ 來明確表示要使用 GNU C extensions，並避免在某些情況下產生警告。

-pedantic and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing extension before the expression. extension has no effect aside from this.

({}) 有點類似於 , 運算子，藉此達到類似於函式回傳值的效果。

The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.

__typeof__() 可得到變數的型態。

If you are writing a header file that must work when included in ISO C programs, write __typeof__ instead of typeof.

offsetof() 得到某個成員的位置偏移量。

/**
 * container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
#ifndef container_of
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#endif

doubly-linked list 的鏈結，納入新結構的成員中即可。

/**
 * struct list_head - Head and node of a doubly-linked list
 * @prev: pointer to the previous node in the list
 * @next: pointer to the next node in the list
 */
struct list_head {
    struct list_head *prev, *next;
};

/**
 * LIST_HEAD - Declare list head and initialize it
 * @head: name of the new object
 */
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

/**
 * INIT_LIST_HEAD() - Initialize empty list head
 * @head: pointer to list head
 */
static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head; head->prev = head;
}

/**
 * list_add_tail() - Add a list node to the end of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

/**
 * list_del() - Remove a list node from the list
 * @node: pointer to the node
 */
static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next, *prev = node->prev;
    next->prev = prev; prev->next = next;
}

/**
 * list_empty() - Check if list head has no nodes attached
 * @head: pointer to the head of the list
 */
static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

/**
 * list_is_singular() - Check if list head has exactly one node attached
 * @head: pointer to the head of the list
 */
static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

把 list 接到 node 的尾端。

/**
 * list_splice_tail() - Add list nodes from a list to end of another list
 * @list: pointer to the head of the list with the node entries
 * @head: pointer to the head of the list
 */
static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next, *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

把串列從 node 的地方切開，前半部分接到 head_to，後半部分留在 head_from。

/**
 * list_cut_position() - Move beginning of a list to another list
 * @head_to: pointer to the head of the list which receives nodes
 * @head_from: pointer to the head of the list
 * @node: pointer to the node in which defines the cutting point
 */
static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

假設自己定義的 struct S，裡面有一個 list_head list，可以透過 list_entry(node, S, list) 得到整個物件的指標 struct S *。

/**
 * list_entry() - Calculate address of entry that contains list node
 * @node: pointer to list node
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_entry(node, type, member) container_of(node, type, member)

/**
 * list_first_entry() - get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

/**
 * list_for_each - iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

運用上述程式碼實作 merge sort。 list_ele_t 中的 next 與 queue_t 中的 head 和 tail 都不需要。

list_ele_t 與 queue_t 中都有一個 struct list_head 即可形成 circular doubly-linked list。

這邊進一步改進，將 struct list_head 放在結構中的第一個成員，存取整個物件時，只需把 struct list_head * 轉型為 list_ele_t *，而不需要使用 list_entry() (container_of()) 這個 macro，不只讓操作更便利以外，也節省運算指標位置的減法 (- offsetof(type, member)))。

container_of 用到 offsetof，後者是編譯時期的操作。在結構體中的第一個成員 struct list_head list; 需要特別標注其位置，也該考慮到 padding，例如 Typical alignment of C structs on x86 所及，第二個成員實際的記憶體位置可能會因 padding 調整

根據 C11 standard 6.7.2.1 Structure and union specifiers 中第 15 點，對於第一個成員的位置是有規範的。

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

typedef struct __element {
    struct list_head list;
    /* Put struct list_head in the initial(first) member */
    char *value;
} list_ele_t;

程式碼精簡後，不難發現 queue_t 根本就是多餘的結構，應該一併調整。這是設計題目時，讓同學們得以進一步重構 (refactor) 的空間。

jserv

已經進行重構，把多餘的結構去除並改寫程式碼！

回傳值改為 list_head *，會比較好進行串列的操作。需要時，也可透過 list_entry() 得到整個物件。

static struct list_head *get_middle(struct list_head *head)
{
    struct list_head *fast = head->next, *slow = head->next;
    while (fast->next != head && fast->next->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

static void list_merge(struct list_head *lhs,
                       struct list_head *rhs,
                       struct list_head *head)
{
    INIT_LIST_HEAD(head);

    while (!list_empty(lhs) && !list_empty(rhs)) {
        char *lv = ((list_ele_t *)lhs->next)->value;
        char *rv = ((list_ele_t *)rhs->next)->value;
        struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
        list_del(tmp);
        list_add_tail(tmp, head);
    }
    list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

void list_merge_sort(struct list_head *q)
{
    if (list_empty(q) || list_is_singular(q))
        return;

    struct list_head left, sorted;
    INIT_LIST_HEAD(&left);
    list_cut_position(&left, q, get_middle(q));
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left, q, &sorted);
    INIT_LIST_HEAD(q);
    list_splice_tail(&sorted, q);
}

測試程式碼

static bool validate(struct list_head *q)
{
    struct list_head *node;
    for (node = q->next; node->next != q; node = node->next) {
        if (strcmp(((list_ele_t *)node)->value,
                   ((list_ele_t *)node->next)->value) > 0)
            return false;
    }
    return true;
}

static struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q) return NULL;

    INIT_LIST_HEAD(q);
    return q;
}

static void q_free(struct list_head *q)
{
    struct list_head *current = q->next;
    while (current != q) {
        struct list_head *tmp = current;
        current = current->next;
        free(((list_ele_t *)tmp)->value);
        free((list_ele_t *)tmp);
    }
    free(q);
}

這邊可以利用 list_add_tail 把他接到第一個元素 (q->next) 的前面。

bool q_insert_head(struct list_head *q, char *s)
{
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    char *new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    list_add_tail((struct list_head *)newh, q->next);

    return true;
}

static void q_show(struct list_head *q)
{
    struct list_head *node;
    list_for_each (node, q) {
        printf("%s", ((list_ele_t *)node)->value);
    }
}

int main(void)
{
    FILE *fp = fopen("cities.txt", "r");
    if (!fp) {
        perror("failed to open cities.txt");
        exit(EXIT_FAILURE);
    }

    struct list_head *q = q_new();
    char buf[256];
    while (fgets(buf, 256, fp))
        q_insert_head(q, buf);
    fclose(fp);

    list_merge_sort(q);
    q_show(q);
    assert(validate(q));

    q_free(q);

    return 0;
}

---

測驗 2

程式碼解說

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

N |= N >> 1; 會讓第一個 1 的位元的下一個位元變成 1，接著 N |= N >> 2; 會讓第一個 1 的位元開始的四個位元都變成 1，以此類推。

最後得到一個第一個 1 的位元以下皆為 1 的數字，加上 1 後往左位移，即可得到第一個 1 的位元以下皆為 0 的數字。

程式碼最後一行應該改為 return (N >> 1) + 1;，避免 msb 為 1 的數字會溢位。
特別注意的是 func(0) 會從 0 變為 1，不過 小於或等於 0 的 power-of-2 本身就是未定義的，這邊就不管它了。

不過因為這邊型別是 16 位元的無號整數，利用 gdb 去看組合語言。

0x000000000000118a <+65>:    add    $0x1,%eax
0x000000000000118d <+68>:    sar    %eax
0x000000000000118f <+70>:    pop    %rbp
0x0000000000001190 <+71>:    retq

可以發現 return (N + 1) >> 1; 是用 32 位元的暫存器 (%eax) 做運算，所以不會有整數溢位的問題。

如果把寫法改成，

    ...
    N += 1;
    return N >> 1;

就會得到，

   0x0000000000001186 <+61>:    addw   $0x1,-0x4(%rbp)
   0x000000000000118b <+66>:    movzwl -0x4(%rbp),%eax
   0x000000000000118f <+70>:    shr    %ax
   0x0000000000001192 <+73>:    pop    %rbp
   0x0000000000001193 <+74>:    retq

可以發現程式碼會使用 16 位元的暫存器做運算，
或是改成 32 位元的無號整數版本，都會產生整數溢位的問題。

根據 C11 standard 6.3.1 Arithmetic operands 6.3.1.1 Boolean, characters, and integers 中第 2 點，

If an int can represent all values of the original type (as restricted by the width, for abit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions.

return (N + (uint16_t)1) >> 1; 在這邊一樣是用 int 做運算，並不會有整數溢位的問題。

---

測驗 3

程式碼解說

要從某個位元開始存取資料時，當前的位元組往左位移 _read_lhs 與下一個位元組往右移 _read_rhs 後，進行 bitwise or 運算，即可得到一整個位元組大小的資料。

寫入時則剛好相反，整個位元組往右位移 _write_lhs 寫入當前的位元組，往左位移 _write_rhs 則寫入下一個位元組。

_*_rhs 的值剛好也是代表當前位元組佔了幾個位元，所以要判斷有沒有跨越位元組時，可以用 bitsize 與 _*_rhs 進行比較。

下圖為 _read_lhs 等於 3 時的示意圖。

_read / 8 即可得知從第幾個位元組開始操作，而 _read & 7 則是計算從此位元組的第幾個位元開始，(_read / 8 可用 _read >> 3 替代)。

_write 部分的操作與 _read 同理。

這邊做了一些小修改，

• >> 3 替代 / 8
• 去除 origin 這個變數，直接用 *dest 表示
• 去除一些不必要的條件判斷
• 將 read_mask 與 write_mask 改名，使其更易理解。
  • left_mask[b] 代表位元 b 左邊為 1
  • right_mask[b] 代表位元 b 右邊及本身為 1

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    static const uint8_t left_mask[] = {
        0x00, /*    == 0    00000000b   */
        0x80, /*    == 1    10000000b   */
        0xC0, /*    == 2    11000000b   */
        0xE0, /*    == 3    11100000b   */
        0xF0, /*    == 4    11110000b   */
        0xF8, /*    == 5    11111000b   */
        0xFC, /*    == 6    11111100b   */
        0xFE, /*    == 7    11111110b   */
        0xFF  /*    == 8    11111111b   */
    };
    static const uint8_t right_mask[] = {
        0xFF, /*    == 0    11111111b   */
        0x7F, /*    == 1    01111111b   */
        0x3F, /*    == 2    00111111b   */
        0x1F, /*    == 3    00011111b   */
        0x0F, /*    == 4    00001111b   */
        0x07, /*    == 5    00000111b   */
        0x03, /*    == 6    00000011b   */
        0x01, /*    == 7    00000001b   */
        0x00  /*    == 8    00000000b   */
    };

    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read >> 3);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write >> 3);

    while (count > 0) {
        size_t bitsize = (count > 8) ? 8 : count;
        uint8_t data = *source++;
        if (read_lhs > 0) {
            data <<= read_lhs;
            data |= (*source >> read_rhs);
        }
        data &= left_mask[bitsize];

        uint8_t mask = left_mask[write_lhs];
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest = (*dest & mask) | (data >> write_lhs);
            ++dest;
            *dest = (*dest & right_mask[bitsize - write_rhs]) | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            mask |= right_mask[write_lhs + bitsize];
            *dest = (*dest & mask) | (data >> write_lhs);
            ++dest;
        }

        count -= bitsize;
    }
}

第 39 行開始，先把下一個位元組大小的資料放入 data 中，44 行再把多餘的位元利用 left_mask 去除。

下面用了一些遮罩，為了保存頭尾我們沒有要寫入的部分 ，取用 left_mask 以及 right_mask 的引索意義如下，

• write_lhs 代表從當前位元組的第幾個位元開始
• write_lhs + bitsize 代表寫到當前位元組的第幾個位元
• bitsize - write_rhs 代表寫到下一位元組的第幾個位元 (上述說過，write_rhs 也代表在當前位元組佔了多少位元，所以 bitsize 扣除它後，剩下的就是在下一位元組。)

如果 bitsize <= write_rhs，代表寫入的部分不需要跨位元，54 行後，mask 示意圖如下，以 write_lhs 為 3，bitsize 為 4 為例。

如果 bitsize > write_rhs，mask 右側一定都為 0，下圖以 write_lhs 為 3，bitsize 為 7 為例。

51 行的 right_mask[bitsize - write_rhs] 則得到另一個 mask，

效率更高的實作

中間的部分，每次剛好複製 source 的一個位元組，可降低讀取時的運算量。

void bitcpy_opt(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    static const uint8_t left_mask[] = {
        0x00, /*    == 0    00000000b   */
        0x80, /*    == 1    10000000b   */
        0xC0, /*    == 2    11000000b   */
        0xE0, /*    == 3    11100000b   */
        0xF0, /*    == 4    11110000b   */
        0xF8, /*    == 5    11111000b   */
        0xFC, /*    == 6    11111100b   */
        0xFE, /*    == 7    11111110b   */
        0xFF  /*    == 8    11111111b   */
    };

    static const uint8_t right_mask[] = {
        0xFF, /*    == 0    11111111b   */
        0x7F, /*    == 1    01111111b   */
        0x3F, /*    == 2    00111111b   */
        0x1F, /*    == 3    00011111b   */
        0x0F, /*    == 4    00001111b   */
        0x07, /*    == 5    00000111b   */
        0x03, /*    == 6    00000011b   */
        0x01, /*    == 7    00000001b   */
        0x00  /*    == 8    00000000b   */
    };

    const uint8_t *source = (const uint8_t *) _src + (_read >> 3);
    _read &= 7;
    uint8_t *dest = (uint8_t *) _dest + (_write >> 3);
    _write &= 7;

    // first byte in source
    size_t bitsize = count < 8 - _read ? count : 8 - _read;
    uint8_t data = (*source++ << _read) & left_mask[bitsize];
    uint8_t mask = left_mask[_write] | (_write + bitsize < 8 ? right_mask[_write + bitsize] : 0x00);
    *dest = (*dest & mask) | (data >> _write);
    if (_write + bitsize >= 8) {
        ++dest;
        size_t remain = _write + bitsize - 8;
        if (_write)
            *dest = (*dest & right_mask[remain]) | (data << (8 - _write));
    }
    count -= bitsize;
    _write = (_write + bitsize) & 7;

    while (count >= 8) {
        data = *source++;
        *dest = (*dest & left_mask[_write]) | (data >> _write);
        ++dest;
        if (_write)
            *dest = (*dest & right_mask[_write]) | data << (8 - _write);
        count -= 8;
    }

    // last byte in source
    data = *source++ & left_mask[count];
    mask = left_mask[_write] | (_write + count < 8 ? right_mask[_write + count] : 0x00);
    *dest = (*dest & mask) | (data >> _write);
    if (count > 8 - _write) {
        ++dest;
        size_t remain = count - (8 - _write);
        *dest = (*dest & right_mask[remain]) | (data << (8 - _write));
    }
}

---

測驗 4

程式碼解說

cstr.h

#pragma once
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

分別用 2 的冪次代表，可以透過 | (bitwise or) 進行聯集形成集合。

enum {
    CSTR_PERMANENT = 1,
    CSTR_INTERNING = 2,
    CSTR_ONSTACK = 4,
};

#define CSTR_INTERNING_SIZE (32)
#define CSTR_STACK_SIZE (128)

typedef struct __cstr_data {
    char *cstr;
    uint32_t hash_size;
    uint16_t type;
    uint16_t ref;
} * cstring;

這邊定義 cstr_buffer 為 __cstr_buffer[1]，在大多時候，array 會退化 (decay) 成一個 pointer，
這邊的功能類似 __cstr_buffer*，但在使用時，卻不用寫成

__cstr_buffer obj;
cstr_buffer ptr = &obj;

而是

cstr_buffer ptr;

，即可在 stack 上有一個 __cstr_buffer 的物件，而名稱可以當作指標使用。

可參考 Everything you need to know about pointers in C

typedef struct __cstr_buffer {
    cstring str;
} cstr_buffer[1];

#define CSTR_S(s) ((s)->str)

把 var 中的 str 初始成一個字串放在 stack 上的 __cstr_data。

#define CSTR_BUFFER(var)                                                      \
    char var##_cstring[CSTR_STACK_SIZE] = {0};                                \
    struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \
    cstr_buffer var;                                                          \
    var->str = &var##_cstr_data;

初使化一個靜態的 cstring，並透過 __sync_bool_compare_and_swap() 確保在多執行緒的環境下能夠正確執行。

#define CSTR_LITERAL(var, cstr)                                               \
    static cstring var = NULL;                                                \
    if (!var) {                                                               \
        cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1); \
        if (tmp->type == 0) {                                                 \
            tmp->type = CSTR_PERMANENT;                                       \
            tmp->ref = 0;                                                     \
        }                                                                     \
        if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) {                 \
            if (tmp->type == CSTR_PERMANENT)                                  \
                free(tmp);                                                    \
        }                                                                     \
    }

do { } while(0) 可參考 multi-line macro: do/while(0) vs scope block;

#define CSTR_CLOSE(var)               \
    do {                              \
        if (!(var)->str->type)        \
            cstr_release((var)->str); \
    } while (0)

/* Public API */
cstring cstr_grab(cstring s);
cstring cstr_clone(const char *cstr, size_t sz);
cstring cstr_cat(cstr_buffer sb, const char *str);
int cstr_equal(cstring a, cstring b);
void cstr_release(cstring s);

cstr.c

#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>

#include "cstr.h"

#define INTERNING_POOL_SIZE 1024

#define HASH_START_SIZE 16 /* must be power of 2 */

struct __cstr_node {
    char buffer[CSTR_INTERNING_SIZE];
    struct __cstr_data str;
    struct __cstr_node *next;
};

struct __cstr_pool {
    struct __cstr_node node[INTERNING_POOL_SIZE];
};

struct __cstr_interning {
    int lock;
    int index;
    unsigned size;
    unsigned total;
    struct __cstr_node **hash;
    struct __cstr_pool *pool;
};

static struct __cstr_interning __cstr_ctx;

/* FIXME: use C11 atomics */
#define CSTR_LOCK()                                               \
    ({                                                            \
        while (__sync_lock_test_and_set(&(__cstr_ctx.lock), 1)) { \
        }                                                         \
    })
#define CSTR_UNLOCK() ({ __sync_lock_release(&(__cstr_ctx.lock)); })

進行 malloc，失敗則直接中止程式。

static void *xalloc(size_t n)
{
    void *m = malloc(n);
    if (!m)
        exit(-1);
    return m;
}

將物件放入雜湊表。

static inline void insert_node(struct __cstr_node **hash,
                               int sz,
                               struct __cstr_node *node)
{
    uint32_t h = node->str.hash_size;
    int index = h & (sz - 1);
    node->next = hash[index];
    hash[index] = node;
}

將 si 中的雜湊表 (hash) 擴大一倍。

static void expand(struct __cstr_interning *si)
{
    unsigned new_size = si->size * 2;
    if (new_size < HASH_START_SIZE)
        new_size = HASH_START_SIZE;

    struct __cstr_node **new_hash =
        xalloc(sizeof(struct __cstr_node *) * new_size);
    memset(new_hash, 0, sizeof(struct __cstr_node *) * new_size);

    for (unsigned i = 0; i < si->size; ++i) {
        struct __cstr_node *node = si->hash[i];
        while (node) {
            struct __cstr_node *tmp = node->next;
            insert_node(new_hash, new_size, node);
            node = tmp;
        }
    }

    free(si->hash);
    si->hash = new_hash;
    si->size = new_size;
}

嘗試進行字串駐留，若 si 本身為空，或是裡面的物件多於雜湊表大小的 80% 時，則失敗。

static cstring interning(struct __cstr_interning *si,
                         const char *cstr,
                         size_t sz,
                         uint32_t hash)
{
    if (!si->hash)
        return NULL;

    int index = (int) (hash & (si->size - 1));
    struct __cstr_node *n = si->hash[index];
    while (n) {
        if (n->str.hash_size == hash) {
            if (!strcmp(n->str.cstr, cstr))
                return &n->str;
        }
        n = n->next;
    }
    // 80% (4/5) threshold
    if (si->total * 5 >= si->size * 4)
        return NULL;
    if (!si->pool) {
        si->pool = xalloc(sizeof(struct __cstr_pool));
        si->index = 0;
    }
    n = &si->pool->node[si->index++];
    memcpy(n->buffer, cstr, sz);
    n->buffer[sz] = 0;

    cstring cs = &n->str;
    cs->cstr = n->buffer;
    cs->hash_size = hash;
    cs->type = CSTR_INTERNING;
    cs->ref = 0;

    n->next = si->hash[index];
    si->hash[index] = n;

    return cs;
}

進行字串駐留，若失敗了，則拓展雜湊表，再進行一次。

static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
    cstring ret;
    CSTR_LOCK();
    ret = interning(&__cstr_ctx, cstr, sz, hash);
    if (!ret) {
        expand(&__cstr_ctx);
        ret = interning(&__cstr_ctx, cstr, sz, hash);
    }
    ++__cstr_ctx.total;
    CSTR_UNLOCK();
    return ret;
}

真正的雜湊函數。

static inline uint32_t hash_blob(const char *buffer, size_t len)
{
    const uint8_t *ptr = (const uint8_t *) buffer;
    size_t h = len;
    size_t step = (len >> 5) + 1;
    for (size_t i = len; i >= step; i -= step)
        h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]);
    return h == 0 ? 1 : h;
}

這邊 void *ptr = (void *) (p + 1); 應為 char *ptr = (char *)(p + sizeof(struct __cstr_data));，在一個 struct __cstr_data 之後，才是配置給字串的空間。

如果字串長度小於 CSTR_INTERNING_SIZE，就進行字串駐留，否則的話，直接配置一個新的 cstring。

cstring cstr_clone(const char *cstr, size_t sz)
{
    if (sz < CSTR_INTERNING_SIZE)
        return cstr_interning(cstr, sz, hash_blob(cstr, sz));
    cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);
    if (!p)
        return NULL;
    char *ptr = (char *)(p + sizeof(struct __cstr_data));
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    memcpy(ptr, cstr, sz);
    ptr[sz] = 0;
    p->hash_size = 0;
    return p;
}

cstring cstr_grab(cstring s)
{
    if (s->type & (CSTR_PERMANENT | CSTR_INTERNING))
        return s;
    if (s->type == CSTR_ONSTACK)
        return cstr_clone(s->cstr, s->hash_size);
    if (s->ref == 0)
        s->type = CSTR_PERMANENT;
    else
        __sync_add_and_fetch(&s->ref, 1);
    return s;
}

對字串進行記憶體釋放，這邊使用 sync_sub_and_fetch 來確保在多執行緒的環境下能夠正確運作。

void cstr_release(cstring s)
{
    if (s->type || !s->ref)
        return;
    if (__sync_sub_and_fetch(&s->ref, 1) == 0)
        free(s);
}

如果 s 是放在 stack 上，hash_size 是它的長度，否則的話，確認是否計算過雜湊值。 (回傳值應改為 uint32_t )

static uint32_t cstr_hash(cstring s)
{
    if (s->type == CSTR_ONSTACK)
        return hash_blob(s->cstr, s->hash_size);
    if (s->hash_size == 0)
        s->hash_size = hash_blob(s->cstr, strlen(s->cstr));
    return s->hash_size;
}

如果 a 與 b 都是被駐留的字串，那只有當指標相同時才會是一樣的字串；如果字串在 stack 上，可以先用字串長度 (hash_size) 判斷一下，否則也可以先用雜湊值判斷一下。

int cstr_equal(cstring a, cstring b)
{
    if (a == b)
        return 1;
    if ((a->type == CSTR_INTERNING) && (b->type == CSTR_INTERNING))
        return 0;
    if ((a->type == CSTR_ONSTACK) && (b->type == CSTR_ONSTACK)) {
        if (a->hash_size != b->hash_size)
            return 0;
        return memcmp(a->cstr, b->cstr, a->hash_size) == 0;
    }
    if (cstr_hash(a) != cstr_hash(b))
        return 0;
    return !strcmp(a->cstr, b->cstr);
}

這邊 char *ptr = (char *) (p + 1); 應為 char *ptr = (char *)(p + sizeof(struct __cstr_data));，理由同上。

如果 a 與 b 的長度小於 CSTR_INTERNING_SIZE，會進行字串駐留，否則的話就另外配置一個 cstring。

static cstring cstr_cat2(const char *a, const char *b)
{
    size_t sa = strlen(a), sb = strlen(b);
    if (sa + sb < CSTR_INTERNING_SIZE) {
        char tmp[CSTR_INTERNING_SIZE];
        memcpy(tmp, a, sa);
        memcpy(tmp + sa, b, sb);
        tmp[sa + sb] = 0;
        return cstr_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
    }
    cstring p = xalloc(sizeof(struct __cstr_data) + sa + sb + 1);
    if (!p)
        return NULL;

    char *ptr = (char *)(p + sizeof(struct __cstr_data));
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    memcpy(ptr, a, sa);
    memcpy(ptr + sa, b, sb);
    ptr[sa + sb] = 0;
    p->hash_size = 0;
    return p;
}

先看看原本 sb 中的字串是不是放在 stack，是的話嘗試把 str 也放入，不行的話就呼叫 cstr_cat2 去進行記憶體配置並完成字串連接。

cstring cstr_cat(cstr_buffer sb, const char *str)
{
    cstring s = sb->str;
    if (s->type == CSTR_ONSTACK) {
        int i = s->hash_size;
        while (i < CSTR_STACK_SIZE - 1) {
            s->cstr[i] = *str;
            if (*str == 0)
                return s;
            ++s->hash_size;
            ++str;
            ++i;
        }
        s->cstr[i] = 0;
    }
    cstring tmp = s;
    sb->str = cstr_cat2(tmp->cstr, str);
    cstr_release(tmp);
    return sb->str;
}

從 cstr.h 中可以看到，會得到 cstring 的有 cstr_grab() 、 cstr_clone() 與 cstr_cat()，還有 CSTR_BUFFER 與 CSTR_LITERAL 二個巨集。

可以歸納出處理字串的行為，如果字串長度小於 CSTR_INTERNING_SIZE 的話，就會進行字串駐留， type 為 CSTR_INTERNING，hash_size 中保存它的雜湊值，否則的話，就直接放在一個 cstring 中而已，type 為 0，hash_size 也為 0；比較特別的是，透過 CSTR_BUFFER 宣告的變數，其中的 cstring 一開始是指向放在 stack 上的記憶體，最多可以存放 CSTR_STACK_SIZE - 1 長度的字串，type 為 CSTR_ONSTACK，hash_size 為字串長度。

另外，CSTR_LITERAL 中透過 cstr_clone() 得到的 cstring，如果沒有進行字串駐留，type 則會變成 CSTR_PERMANENT，ref 則為 0。

程式碼中，會減少 ref 的只有 cstr_release()，但是當它變為 0 後，又會直接釋放記憶體，另一邊 cstr_grab() 的地方則是在 ref 為 0 時會把 type 轉為 CSTR_PERMANENT。

這邊對於 ref 這個成員以及 CSTR_PERMANENT 這樣的 cstring，看起來並沒有太多應用，也不太完整，或許是為了未來開發作保留的。

tags: linux2021