2019-06-19 王議偉

contributed by < yiwei01 >

Q1: memory alignment

以下程式碼改寫自 Linux 核心，比較兩個 Ethernet MAC 地址是否一致。在特定的硬體平台 (如 Arm 和 MIPS) 可能會遇到 unaligned memory access，請改寫以避開這個問題。考慮輸入值必為 16-bit-aligned addresses

#include <stdint.h>
bool addr_equal(const uint8_t *addr1, const uint8_t *addr2)
{
    uint32_t fold = ((*(const uint32_t *)addr1) ^ (*(const uint32_t *)addr2)) |
                    ((*(const uint16_t *)(addr1 + 4)) ^ (*(const uint16_t *)(addr2 + 4)));
    return fold == 0;
}

Hint: 考慮地址是 0x10003

Reference:

• MAC Addresses With Formatting Examples

Answer

const uint16_t *a = (const uint16_t *)addr1, *b = (const uint16_t *)addr2;
return (0 == (a[0] ^ b[0]) | a[1] ^ b[1] | a[2] ^ b[2])); 

---

Q2:

使用 Linux 核心的 list.h，寫出對一個已經排序過的 linked list 做新增節點的操作。

Hint: list_empty, list_add, list_for_each_entry, list_add_tail

Answer

version 1

#include <stddef.h>
#include <stdint.h>
#include "list.h"

struct listitem {
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2) {
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
    struct listitem *item = NULL;
    if (list_empty(head)) {
        list_add(&entry->list, head);
        return;
    }

    list_for_each_entry(item, head, list) {
        if(item->i > entry->i){
            list_add_tail(&entry->list, &item->list);
            return;
        }
    }
    
    list_add(&entry->list, head->next)
}

想法是：走訪 linked list 的同時做比較，符合比較的結果便直接插入。
注意：list_add 及 list_add_tail 的原始碼。

version 2

struct list_head *right = NULL;
INIT_LIST_HEAD(right);
list_for_each_entry_safe (item, is, &testlist, list) {
    if(item->i > entry->i){
        list_move_tail(&item->list,&right);
    }
}

list_add(&entry->list,right);
list_splice_tail(right,head);

此版本雖然 worst case 雖然也是 O(n)，但與上述 version1 的答案相比，較不直觀。

如果不是 circular list，該做哪些額外的檢查？

若不是 circular list ，則必須紀錄 front 及 rear ，因此在程式碼的撰寫上會多一些邊界條件判斷，以確保 front 及 rear 的正確性。

tags: sysprog2019