2024q1 Homework1 (lab0)

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i7-12700H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  14
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4700.0000
    CPU min MHz:         400.0000
    BogoMIPS:            5376.00

$ ./qtest 
cmd> new
l = []

$ ./qtest 
cmd> new
l = []
cmd> ih p
l = [p]
cmd> ih l
l = [l p]
cmd> free
l = NULL

$ make check
...
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
make: *** [Makefile:57: check] Error 1

    if (!head)
        return;
-    struct list_head *node, *safe = malloc(sizeof(struct list_head));
+    struct list_head *node, *safe = NULL;

$ ./qtest 
cmd> new
l = []
cmd> ih r
l = [r]
cmd> ih s
l = [s r]

cmd> new
l = []
cmd> ih r
ERROR: Need to allocate and copy string for new queue element
l = [r]
cmd> ih a
ERROR: Need to allocate and copy string for new queue element
l = [a ��!\]

    new_node->value = malloc(strlen(s) + 1);
    if (!new_node->value) {
        return false;
    }
    strcpy(new_node->value, s);

    new_node->value = strdup(s);

$ ./qtest 
cmd> new
l = []
cmd> it e
l = [e]
cmd> it q
l = [e q]

l = [s e q]
cmd> ih o
l = [o s e q]
cmd> rh
Removed o from queue
l = [s e q]

cmd> ih y
l = [y u i o]
cmd> rt
Removed o from queue
l = [y u i]

l = [a b c d e f g h]
cmd> size
Queue size = 8
l = [a b c d e f g h]

l = [a c e g i]
cmd> dm
l = [a c g i]
cmd> dm
l = [a c i]
cmd> dm
l = [a i]
cmd> dm
l = [a]

l = [a a a b b c]
cmd> dedup
l = [c]

l = [a b c d e f]
cmd> swap
l = [b a d c f e]

l = [a b c d e f]
cmd> reverse
l = [f e d c b a]

l = [1 2 3 4 5 6]
cmd> reverseK 2
l = [2 1 4 3 6 5]
cmd> reverseK 6
l = [5 6 3 4 1 2]

-    if (count % k == 0) {
-        list_cut_position(&tmp, head, cur);
-        q_reverse(&tmp);
-        list_splice_tail_init(&tmp, &tmp_rev);
-        if (cur->next == head)
-            list_splice(&tmp_rev, head);
-    } else if (cur->next == head) {
-        list_splice(&tmp_rev, head);
-    }
+    if (count % k == 0 && cur->next == head) {
+        list_cut_position(&tmp, head, cur);
+       q_reverse(&tmp);
+        list_splice_tail_init(&tmp, &tmp_rev);
+        list_splice(&tmp_rev, head);
+    } else if (count % k == 0) {
+        list_cut_position(&tmp, head, cur);
+        q_reverse(&tmp);
+        list_splice_tail_init(&tmp, &tmp_rev);
+    } else if (cur->next == head) {
+        list_splice(&tmp_rev, head);
+    }

l = [a b c d e f]
cmd> reverseK 2
l = []

l = [8 4 9 5 2 1 3]
cmd> sort
l = [1 2 3 4 5 8 9]

l = [2 1 3 6 5 8 9]
cmd> ascend
l = [1 3 5 8 9]

l = [7 9 4 5 3 2 1]
cmd> descend
l = [9 5 3 2 1]

l = [2 4 5]
cmd> new
l = []
cmd> ih 3
l = [3]
cmd> ih 1
l = [1 3]
cmd> merge
l = [1 2 3 4 5]

extern void q_shuffle(struct list_head *head);

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    if (!current || !current->q) {
        report(3, "Warning: Calling shuffle on null queue");
        return false;
    }
    error_check();
    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();
    set_noallocate_mode(false);
    q_show(3);
    return !error_check();
}

ADD_COMMAND(shuffle, "Shuffle all nodes in the list", "");

python3 ./scripts/testShuffle.py

ray@ray:~/linux2024/lab0-c$ python3 ./scripts/testShuffle.py
Expectation:  41666
Observation:  {
'1234': 41456, '1243': 41703, '1324': 41676,
'1342': 41873, '1423': 41882, '1432': 41708, 
'2134': 41708, '2143': 41375, '2314': 41695,
'2341': 41946, '2413': 41477, '2431': 41719, 
'3124': 41287, '3142': 41524, '3214': 41680, 
'3241': 41479, '3412': 41482, '3421': 41840, 
'4123': 41591, '4132': 41793, '4213': 41849, 
'4231': 41768, '4312': 41554, '4321': 41935
}
chi square sum:  18.113281812508998

valgrind --tool=massif ./qtest -f traces/trace-15-perf.cmd

sudo apt install massif-visualizer

massif-visualizer massif.out.3445

/*
 * Returns a list organized in an intermediate format suited
 * to chaining of merge() calls: null-terminated, no reserved or
 * sentinel head node, "prev" links not maintained.
 */

digraph{
    rankdir=LR
    NULL [shape=none,color=black]
    head [shape=none,label=head]
    tail [shape=none,label=tail]
    tail -> head -> NULL

}

digraph{
    rankdir=LR
    head [shape=none,label=head]
    tail [shape=none,label=tail]
    a [shape=none,label=a]
    a_next [shape=none,label=a_next]
    head -> a
    tail -> a -> a_next
    
}

struct list_head *head, **tail = &head;

for (;;) {
    /* if equal, take 'a' -- important for sort stability */
    if (cmp(priv, a, b) <= 0) {
        *tail = a;
        tail = &a->next;
        a = a->next;
        if (!a) {
            *tail = b;
            break;
        }
    } else {
        ...

digraph{
    rankdir=LR
    head_next [shape=none,color=black]
    head [shape=none,label=head]
    tail [shape=none,label=tail]
    
    head -> head_next
    tail -> head_next

}

digraph{
    rankdir=LR
    node [shape=none,color=black]
    
    tail -> a -> tail
    head -> a

}

digraph{
    rankdir=LR
    node [shape=none,color=black]
    
    head -> tail

}

/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
    /*
     * If the merge is highly unbalanced (e.g. the input is
     * already sorted), this loop may run many iterations.
     * Continue callbacks to the client even though no
     * element comparison is needed, so the client's cmp()
     * routine can invoke cond_resched() periodically.
     */
    if (unlikely(!++count))
        cmp(priv, b, b);
    b->prev = tail;
    tail = b;
    b = b->next;
} while (b);
...

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

/**
 * This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.

/**
 * The merging is controlled by "count", the number of elements in the
 * pending lists.  This is beautifully simple code, but rather subtle.
 *
 * Each time we increment "count", we set one bit (bit k) and clear
 * bits k-1 .. 0.  Each time this happens (except the very first time
 * for each bit, when count increments to 2^k), we merge two lists of
 * size 2^k into one list of size 2^(k+1).
 * ...
 * ...

do {
    size_t bits;
    struct list_head **tail = &pending;

    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }

    /* Move one element from input list to pending */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);

/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);