# facebooc_q0
###### tags: `facebooc 2022`

[Github 專案點我](https://github.com/owenowenisme/facebooc-q0)
[共筆](https://hackmd.io/@qJEZpNvuSHe0kzJAmMSeQg/BkTau1P-j)
[Hackmd 範本](https://hackmd.io/@ktvexe/rk5ayZDKx?type=view)
[數學怎麼寫](https://hackmd.io/@CynthiaChuang/Basic-LaTeX-Commands#%E4%BA%8C%E5%85%83%E9%97%9C%E4%BF%82%E7%AC%A6%E8%99%9F)
## Memory leak test

root@DESKTOP-3JKELOB:/mnt/c/Users/mses0/Desktop/facebooc-q0# make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 test
make[1]: Entering directory '/mnt/c/Users/mses0/Desktop/facebooc-q0'
rm -f test.o queue.o  .test.o.d .queue.o.d *~ test /tmp/test.*
rm -rf *.dSYM
(cd traces; rm -f *~)
/bin/sh: 1: cd: can't cd to traces
gcc -O1 -g -Wall -Werror -I. -c -MMD -MF .test.o.d test.c
gcc -O1 -g -Wall -Werror -I. -c -MMD -MF .queue.o.d queue.c
gcc   test.o queue.o   -o test
make[1]: Leaving directory '/mnt/c/Users/mses0/Desktop/facebooc-q0'
valgrind --leak-check=full ./test
==19756== Memcheck, a memory error detector
==19756== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==19756== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==19756== Command: ./test
==19756==
test: test.c:42: main: Assertion `validate(q)' failed.

==19756== LEAK SUMMARY:
==19756==    definitely lost: 0 bytes in 0 blocks
==19756==    indirectly lost: 0 bytes in 0 blocks
==19756==      possibly lost: 0 bytes in 0 blocks
==19756==    still reachable: 3,868,103 bytes in 187,655 blocks
==19756==         suppressed: 0 bytes in 0 blocks
==19756== Reachable blocks (those to which a pointer was found) are not shown.
==19756== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==19756==
==19756== For lists of detected and suppressed errors, rerun with: -s
==19756== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
make: *** [Makefile:35: valgrind] Aborted

---
## queue_new()

queue_t *q_new()
{
    queue_t *newq=malloc(sizeof(queue_t));// allocate the queue_t's memory and save to pointer newq.
    if(newq==0) return NULL;//couldn't allocate space so return null.
    newq->head=NULL;//empty queue so there is no head element.
    newq->tail=NULL;//empty queue so there is no tail element.
    newq->size=0;//empty queue size=0.
    return newq;
} 

---

## q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if(q==NULL)
        return false;
    element_t *ele=malloc(sizeof(element_t));

    if(ele==NULL) 
        return false;
    
    ele->value=malloc(strlen(s)+1);//allocate new memory for string s.
    
    if(ele->value==NULL){
        free(ele);
        return false;
        }

    strcpy(ele->value,s);

    ele->next=q->head;
    q->head=ele;

    if(ele->next==NULL)
    q->tail=ele;//when there is only one element in queue.

    q->size++;
    return true;
}

---

## q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{   
    if(q==NULL)
        return false;

    element_t *ele=malloc(sizeof(element_t));

    if(ele==NULL) 
        return false;
    
    ele->value=malloc(strlen(s)+1);//allocate new memory for string s.
    
    if(ele->value==NULL){
        free(ele);
          return false;
        }

    strcpy(ele->value,s);

    ele->next=NULL;
    q->tail=ele;

    if(q->head==NULL)
    q->head=ele;//when there is only one element in queue.

    q->size++;
    return true;
    
}

---

## q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{   
    if(q==NULL)
    return false;

    if(q->head==NULL)
    return false;

    element_t *ele=q->head; 
    q->head=q->head->next;

    
    strncpy(sp,ele->value,bufsize-1);
    free(ele->value);
    free(ele);
    q->size--;
    
    
    return true;
}

---
## q_size

size_t q_size(queue_t *q)
{   
    if(q!=NULL)
        return q->size;
    return 0;
}

---
## q_reverse

void q_reverse(queue_t *q)
{
    if(q==NULL)
    return;

    element_t *prev=q->head;
    element_t *now=prev->next;
    element_t *nexttt=now->next;
    prev->next=NULL;//head change to tail so pointer change to null. 

    while(nexttt!=NULL){
        nexttt=now->next;
        now->next=prev;
        prev=now;
        now=nexttt;
    }
    now->next=prev;

    element_t *tmp=q->head;//swap head and tail.
    q->head=q->tail;
    q->tail=tmp;

    
}

---
## merge sort
### q_spilt

void q_spilt(element_t *src,element_t **front,element_t **back){//ref:https://ithelp.ithome.com.tw/articles/10242225
    
    element_t *fast,*slow;//implement with two pointer.
    slow=src;
    fast=src->next;

    while(fast!=NULL){

        fast=fast->next;

        if(fast!=NULL){

            slow=slow->next;
            fast=fast->next;

        }
    }

    *front=src;
    *back=slow->next;
    slow->next=NULL;

}

### *sortedmerge

element_t *sortedmerge(element_t *a,element_t *b){

    element_t *result=NULL;
    if(a==NULL){
        return b;
    }

    if(b==NULL){
        return a;
    }

    if(a->value<=b->value){
        result=a;
        result->next=sortedmerge(a->next,b);
    }
    else{
        result=b;
        result->next=sortedmerge(a,b->next);
    }

    return result;
}

### mergesort

void merge_sort(element_t **head)
{
    if (!(*head) || !(*head)->next)
        return;
    
    element_t *a,*b;

    q_spilt(*head,&a,&b);

    merge_sort(&a);
    merge_sort(&b);

    *head=sortedmerge(a,b);
}