# Extension
## Top 10 frequency word
I had been creating an algorithm but it seems not correct and not as fast as optimization insertion sort ......
## .tar Word Counting
[Github](https://github.com/ilkclord/Extension-of-wordcount)
### .tar
* **Structue**
Each chunk of .tar is 512 * 8 bytes and if the file size isn't the mutilple of 512 * 8 , the empty memory will be filled with `^@` aka **NULL character** with ascii code 0 .
* **header**
Each file has a header to store the information of each file
```clike
struct posix_header
{ /* byte offset */
char name[100]; /* 0 */
char mode[8]; /* 100 */
char uid[8]; /* 108 */
char gid[8]; /* 116 */
char size[12]; /* 124 */
char mtime[12]; /* 136 */
char chksum[8]; /* 148 */
char typeflag; /* 156 */
char linkname[100]; /* 157 */
char magic[6]; /* 257 */
char version[2]; /* 263 */
char uname[32]; /* 265 */
char gname[32]; /* 297 */
char devmajor[8]; /* 329 */
char devminor[8]; /* 337 */
char prefix[155]; /* 345 */
/* 500 */
};
```
* **content**
```clike
char [512]
```
* **Fetch the file information**
we define a data structure correspond to each chunk , aim to mmap perfectly into the program .
```clike
struct tar {
char mem[512] ;
}typedef tar;
```
From the header , it is easy to get the file name and the size of each , if we get the size of each , we can find the next header quickly by calculating which chunk index .
* **Sample code**
```clike
int create_src(char * pwd){
char cmd[50] ;
strcpy(cmd , "tar -C src/ -xf ") ;
strcat(cmd , pwd) ;
int fd = open("src/" , O_RDONLY) ;
if(fd == -1 ){
system("mkdir src/") ;
}
if(system(cmd) == -1) return 0 ;
return 1 ;
}
int s2int(char * s , int size){
int r = 0 ;
int l = size ;
for(int i = l - 2 ; i >= 0 ; i--){
int num = s[i] - 48 ;
if(num > 0 && num < 10)
r = r + (s[i] - 48) * pow(8 ,(l - 2 - i)) ;
}
return r ;
}
int next_header(tar *t , int * sz){
int next = 1 ;
char size[12] ;
strncpy( size, &(t->mem[124]),12) ;
int contents = s2int(size , 12) ;
*sz = contents;
int add = 0 ;
if(contents % 512 != 0)
add = 1 ;
if(contents)
return contents / 512 + add + next ;
else
return 0 ;
}
```
Since the size in .tar is Octet , the value of nth digit is d * 8^n^ ,after converting , we can calculate the next one's position .The `create_src` is to unpack the .tar into a file , which can prevent tar bomb (found at wiki ) .
Here are some method that I had come into mind to do word-counting in mutiple file .
### Version 1
If we get a .tar file , we first mmap the .tar file and use the algorithm above to get the list of the file name . Then we call the word-count function to count for each , word-count funtion here is a function version of word-count.exe .
* **start_count**
```clike
int count_start(queue *q ){
job * j ;
int work = threadn ;
queue_r(q , &j) ;
if(!j){
perror("wrong job") ;
exit(EXIT_FAILURE) ;
}
if(!word_count( work , j->data->pwd , 1)){
perror("first word_count error") ;
exit(EXIT_FAILURE) ;
}
job_destroy(j) ;
while(atomic_load(&q->entry) > 0){
queue_r(q , &j) ;
if(j){
if(!word_count( work , j->data->pwd , 0)){
perror("duration word_count error") ;
exit(EXIT_FAILURE) ;
}
job_destroy(j) ;
}
}
return 1 ;
}
```
* **word-count function**
```clike
int word_count( int n , char * pwd , int first)
{
n_threads = n ;
file_name = pwd ;
printf("%d %d %s\n" ,first, n_threads , pwd) ;
if(mr_init(first) == -1) { perror("wrong init\n") ; exit(EXIT_FAILURE) ;}
run_threads();
wait_threads();
if (mr_reduce()) return 0 ;
//if (mr_print()) exit(EXIT_FAILURE);
file_content = NULL ;
munmap(NULL ,file_size) ;
printf("done word_count\n") ;
return 1 ;
}
```
* **Program Flowchart**
```graphviz
Digraph G{
"Get the file name list" -> "init for once" ->"Do the word-count" ->"print out result" -> "free the memory"
}
```
There are only one initializations to do for each time , which preserve the time for malloc .
* **counter initialize**
When merging , for same word in diffrent cache , we preserve only the node exist in main cache , for the other we add the counter to main node and set its counter to 0
* **execution**
```clike
gcc tar-word-count.c -o tar-word-count -lpthread -lm
./tar-word-count .tar thead_n
```
Result
```clike
>> ./tar-word-count a.tar 4
Words: 14028, word counts: 209040, full buckets: 1243 (ideal 8192)
Operating a.tar with 3 files inside
Done in 52.479 msec
```
The execution time of program is slightly longer than the sum of word-counting for each file.
* **Bug**
And there exist a bug but I can't find out where goes wrong .
* **Mutiple file but has a big difference in file size**
When I was testing , when two file's size has a big diffrence , A is 443100 and B is 64 , the program cause an invalid access .
```clike
==8147== Thread 3:
==8147== Invalid read of size 8
==8147== at 0x109EC3: ht_find (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10A599: wc_add_word (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B060: add_sep (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B0D2: buff_proceed (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B49E: mr_map (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x4869608: start_thread (pthread_create.c:477)
==8147== by 0x4AF4292: clone (clone.S:95)
==8147== Address 0x4be2370 is 107,632 bytes inside an unallocated block of size 4,186,336 in arena "client"
==8147==
==8147== Invalid read of size 8
==8147== at 0x109ECE: ht_find (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10A599: wc_add_word (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B060: add_sep (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B0D2: buff_proceed (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B49E: mr_map (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x4869608: start_thread (pthread_create.c:477)
==8147== by 0x4AF4292: clone (clone.S:95)
==8147== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8147==
==8147==
==8147== Process terminating with default action of signal 11 (SIGSEGV)
==8147== Access not within mapped region at address 0x0
==8147== at 0x109ECE: ht_find (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10A599: wc_add_word (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B060: add_sep (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B0D2: buff_proceed (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x10B49E: mr_map (in /home/ilkclord/linux2020/quiz8/project/Extension-of-wordcount/pof)
==8147== by 0x4869608: start_thread (pthread_create.c:477)
==8147== by 0x4AF4292: clone (clone.S:95)
```
### Version 2
Plugging a thread pool , and handle the mapping / reduce operation
1 . get the list of the file
2 . divide the file according to the size
3 . follows main pool's order , run the mr_map or reduce function
### Version 3
MapReduce model , but the fast key has to be implement fisrt
1 . get the list of the file
2 . operate mutiple files by parallely calling word-counting for each
### Conclude
For mutiple file input , i think MapReduce is still works . When calling the function word-count , we can specified the thread number , so for the smaller file , we call less thread to operate it .But I think version 2 , which plugs in a thread pool will be the best way . I will implement it as soon as possible .
## Reference
[GNU Basic Tar Format](https://www.gnu.org/software/tar/manual/html_node/Standard.html)
Sign in with Wallet
Connect another wallet