Antecedents feed
In the author’s last blog Linux system programming [3.1] – writing ls command, the primary version of LS command has been realized, but compared with the original LS command, there are still differences in display format and no color marking. After two days of study, the author basically solved these two problems, and realized “ls-L”, and had better support for the optional parameters “-a” and “-L” (regardless of the input order of -a and -L, whether it is “lS-a-L”, “ls-L-A”, “ls-al”, or “ls-ls”, Position geometry, repeat or not, will work correctly).
Ls display format solution
First, let’s look at the format of the original LS display:
- 1. Display them in sequence
- 2. Display columns from top to bottom according to the sorting rule. When the current column is displayed, go to the next column
- 3. Each column is left-justified
- 4. The width of each column is the maximum file name length plus 2
- 5. The number of columns should be as large as possible so that each line is “filled” with the filename without causing the last filename in the line to be wrapped
How do we satisfy these five rules when we implement LS display ourselves?
For rule 1, the author has used the sorting algorithm to satisfy. Rule 3 can be satisfied by using “%-*s” in the printf function. The other three rules are not easy to satisfy. The crux of the problem is that we don’t know the number of rows and columns to display, or the maximum string length for each column. In order to obtain these data, I will introduce an algorithm developed by the author, let’s call it the “column algorithm”.
Columns algorithm
The problem can be simplified as follows: give you an array of sorted Pointers to strings and find the number of rows/columns that output these strings in accordance with the above five rules, as well as the maximum string length for each column.
So let’s build a function signature that, since it returns three different pieces of data, passes one as the return value and the other two as Pointers.
2. Determine the function parameters: string pointer array, number of strings, column number pointer, the maximum string length array for each column
The function signature looks like this:
int cal_row(char** filenames,int file_cnt,int* cal_col,int* col_max_arr);Copy the code“Without understanding” version of the column algorithm
In the body of the function, it first evaluates
Minimum number of characters = (Length of each string +2) x Total number of stringsCopy the code2 is added because each string is displayed with at least two Spaces after it. Using the ioctl function call, get the current screen width (the number of characters that can fit in a line). Divide the minimum number of characters by the screen width to get a baseline number of lines. This baseline is the minimum number of lines needed, because it only fits if every string is the same length and the length added by 2 is exactly divisible by the screen width.
When the length difference between strings is large, more space is required. For example, if one string in the same column is too long and the others are too short, the number of Spaces after the short string will be greatly increased to satisfy rule 4.
, after winning the datum line number pre-allocated datum line number * screen width size of the number of characters, will a string from the top down (datum line number), arranged from left to right (the number of columns kept to a pointer to the number of columns), at the same time for each column to obtain maximum string length (in each column in the maximum length of the string array), to calculate the total number of characters, Multiply the maximum string length of each column by the value of the number of rows. The total number of characters is then subtracted from the pre-allocated size, and enough rows are allocated to accommodate the difference.
Iterate through the above steps until the total number of characters is no greater than the pre-allocated size. Returns the number of rows last allocated.
The diagram is shown below:
Source code is as follows:
int cal_row(char** filenames,int file_cnt,int* cal_col,int* col_max_arr)
{
// Get the length before the file name in the pathname
int path_len = strlen(filenames[0]);
while(filenames[0][path_len] ! ='/'){
--path_len;
}
++path_len;
struct winsize size;
ioctl(STDIN_FILENO,TIOCGWINSZ,&size);
int col = size.ws_col; // Get the width of the current window (characters)
int col_max = 0;
int cur_file_size = 0;
int filenames_len[file_cnt];
*cal_col = 0;
int i = 0;
// Get the character length of each filename
for(i = 0; i < file_cnt; ++i){ filenames_len[i] =strlen(filenames[i]) - path_len;
cur_file_size += (filenames_len[i] + 2); // Count the total number of filename characters plus two Spaces
}
// Minimum number of lines to iterate on
int base_row = cur_file_size / col;
if(cur_file_size % col){
base_row++;
}
int pre_allc_size = 0;
do{
*cal_col = 0;
pre_allc_size = base_row * col;
cur_file_size = 0;
for(i = 0; i < file_cnt; ++i){// The last row of the current column
if(i % base_row == base_row - 1){
++(*cal_col);
col_max = (filenames_len[i] > col_max) ? filenames_len[i] : col_max;
cur_file_size += (col_max + 2) * base_row;
col_max_arr[*cal_col- 1] = col_max;
col_max = 0;
}
// Not the last line
else{ col_max = (filenames_len[i] > col_max) ? filenames_len[i] : col_max; }}// The last column is not full
if(i % base_row){
++(*cal_col);
cur_file_size += (col_max + 2) * (i % base_row);
col_max_arr[*cal_col- 1] = col_max;
col_max = 0;
}
int dis = 0;
if(cur_file_size > pre_allc_size){
dis = cur_file_size - pre_allc_size;
}
base_row += (dis / col);
if(dis % col){ ++base_row; }}while(cur_file_size > pre_allc_size);
return base_row;
}
Copy the codeWhen printing, print from left to right, top to bottom, and later in the code.
“Frugal” version of the column algorithm
When calculating the base line count, it’s the same as the “hullabaloo” column sorting algorithm. The difference lies in the treatment of excess columns. Sets a variable of the current screen remaining width. For each string, if its length exceeds the remaining width, the arrangement is terminated. The amount of extra space required is the sum of the length of all remaining unarranged string blocks.
The diagram is shown below:
Source code is as follows:
int cal_row(char** filenames,int file_cnt,int* cal_col,int* col_max_arr)
{
// Get the length before the file name in the pathname
int path_len = strlen(filenames[0]);
while(filenames[0][path_len] ! ='/'){
--path_len;
}
++path_len;
struct winsize size;
ioctl(STDIN_FILENO,TIOCGWINSZ,&size);
int col = size.ws_col; // Get the width of the current window (characters)
int col_max = 0;
int cur_file_size = 0;
int filenames_len[file_cnt];
*cal_col = 0;
int i = 0;
int j = 0;
// Get the character length of each filename
for(i = 0; i < file_cnt; ++i){ filenames_len[i] =strlen(filenames[i]) - path_len + 2; // The string must contain at least two Spaces
/* Special case: if the maximum string length is larger than the screen width, return the line number :file_cnt, column number: 1, maximum width: the maximum string length */
if(filenames_len[i] > col){
*cal_col = 1;
col_max_arr[0] = filenames_len[i];
return file_cnt;
}
cur_file_size += filenames_len[i];
}
// Minimum number of lines to iterate on
int base_row = cur_file_size / col;
if(cur_file_size % col){
base_row++;
}
int flag_succeed = 0; // Indicate whether the arrangement is complete
// Start sorting
while(! flag_succeed){int remind_width = col; // The current available width
*cal_col = - 1;
for(i = 0; i < file_cnt; ++i){/* If the remaining width is not enough to hold the current string, it jumps out and allocates additional line space */
if(filenames_len[i] > remind_width){
break;
}
// A new column
if(i % base_row == 0){
++(*cal_col);
col_max_arr[*cal_col] = filenames_len[i];
}
else{
col_max_arr[*cal_col] = (filenames_len[i] > col_max_arr[*cal_col]) ? filenames_len[i] : col_max_arr[*cal_col];
}
// The last line updates the remaining width
if(i % base_row == base_row - 1){ remind_width -= col_max_arr[*cal_col]; }}// Check whether the array is complete
if(i == file_cnt){
flag_succeed = 1;
}
// Reallocate additional row space
else{
int extra = 0; // The number of additional characters required
while(i < file_cnt){
extra += filenames_len[i++];
}
if(extra % col){
base_row += (extra / col + 1);
}
else{
base_row += (extra / col);
}
}
}
++(*cal_col); // The columns start at 0, so the final increment is 1
return base_row;
}
Copy the codeColumn effect display and deficiencies
Comparison of two column sorting algorithms
1. The comparison between the column sorting algorithm and the original LS
2.” frugal “version of the column algorithm and” be swallowed “version of the column algorithm comparison
As mentioned earlier, in some cases, the “swallowed without chewing” column algorithm format does not display correctly. Here’s an example:
Deficiency in
For now, there are two major drawbacks to even the more sophisticated “frugal” version of the column segmentation algorithm.
Firstly, the sorting is different from the original version. The author uses ASCII value to sort the string. For upper and lower case letters, special symbols and Chinese characters, it is not as suitable as the original LS.
The second problem is that the format of Chinese file name is not correct when it is displayed, as shown below:
Ls display color resolution
Because I need to find information about colors, I decided that the dircolors command would give me useful information by using Linux guidance information, typing:
man dircolors
Copy the codeThe following information is displayed:
dircolors -p > color
Copy the code“>” saves the output of the dircolors -p command to the color file (if not, it is created automatically).
Then type:
vim color
Copy the codeYou can go to the file and view the contents (use the “more color” command, of course, but I prefer to use the “vim” command), as shown below:
The next thing to do is to get the specified file type, which leads to the next section: the implementation of lS-L.
The realization of LS – L
Gets the stat structure content
Take a look at the output of the original LS-L:
- Part one: Mode, the first character of each line indicates the file type. -” for ordinary files, “d” for directories, and so on. The next nine characters represent file access permissions, divided into read permission, write permission, and execute permission, respectively for three types of objects: users, group users, and other users.
- The second part: Links, indicating the number of times the file has been referenced.
- The third part: file owner, which represents the user name of the file owner
- Part four: Group, which indicates the name of the group to which the file owner belongs
- Part five: Size, which indicates the number of bytes in the file
- Part 6: Laste-Modified
- Part 7: File name (Name)
How to obtain this information? I read books and found a “stat” function to help us get this information.
Input:
man 2 stat
Copy the codePs: Enter man stat directly to get stat(1), which is a terminal command, not what we want. The stat(2) found in “SEE ALSO” is what we need.
Format conversion
But don’t get too excited. If you print st_mode, ST_uid, st_GID, and st_mtime directly from the stat structure, you’ll get some numbers, so you’ll have to convert them to strings before printing them.
St_mode bit operations
St_mode is actually a 16-bit binary number with the following structure:
How do you determine the value of a particular bit? Here is the need for the mask this thing, the author in the computer network learned a similar thing – IP address mask. The purpose of a mask is to mask other bits, exposing only the bits needed. That is, the other bits of the mask are set to 0, and the required bit is set to 1. The “and” operation (&) is used to match the number to be processed with the mask, and the result is compared with the number stored in advance to see if it is consistent.
// define a macro that determines the file type
#define S_ISFIFO(m) (((m)&(0170000))==(0010000))
#define S_ISDIR(m) (((m)&(0170000))==(0040000))
#define S_ISCHR(m) (((m)&(0170000))==(0020000))
#define S_ISBLK(m) (((m)&(0170000))==(0060000))
#define S_ISREG(m) (((m)&(0170000))==(0100000))
#define S_ISLNK(m) (((m)&(0170000))==(0120000))
#define S_ISSOCK(m) (((m)&(0170000))==(0140000))
#defineS_ISEXEC(m) (((m)&(0000111))! = (0))
Copy the codeFor example: In the figure above, the first mask is 0170000, the first 0 indicates that the number is octal, which is converted to binary 1111000000000000, that is, all the type bits are 1, assuming that st_mode is 0001000000000000, then the phase is 0001000000000000. Octal = 0100000; this is a regular file.
Similarly, the second mask in the figure above is 0000111, which sets the ‘x’ bit to 1 and the other bits to 0. If any of the ‘x’ bits in st_mode are 1, then the result is not 0, which can determine whether the file is executable.
In this way, we can use masks and predefined values to assist in the transformation of pattern strings.
St_uid/ST_GID/ST_mtime format conversion
With the help of getPwuid function, getgrgid function and ctime function to complete the conversion of user name, group name and time format respectively.
Ls-l effect display
The source code
Ls Optional parameters: -A,-l
/* * ls04.c * writed by lularible * 2021/02/09 * ls -a -l */
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<sys/types.h>
#include<dirent.h>
#include<string.h>
#include<sys/ioctl.h>
#include<unistd.h>
#include<termios.h>
#include<sys/stat.h>
#include<time.h>
#include</home/lularible/bin/sort.h>
#include<pwd.h>
#include<grp.h>
/* / define the macro that determines the file type. Write it here for reference # define S_ISFIFO (m) (((m) & (0170000)) = = (0010000)) # define S_ISDIR (m) (((m) & (0170000)) = = (0040000)) # define S_ISCHR(m) (((m)&(0170000))==(0020000)) #define S_ISBLK(m) (((m)&(0170000))==(0060000)) #define S_ISREG(m) (((m)&(0170000))==(0100000)) #define S_ISLNK(m) (((m)&(0170000))==(0120000)) #define S_ISSOCK(m)(((m)&(0170000))==(0140000)) */
#defineS_ISEXEC(m) (((m)&(0000111))! = (0))
// Function declaration
void do_ls(const char*); / / main frame
void error_handle(const char*); // Error handling
void restored_ls(struct dirent*,const char*); // Save the file name temporarily
void color_print(char*,int.int); // Print the filename in different colors according to the file type
void showtime(long);
void show_with_l(a); // Displays the content with the -l argument
void show_without_l(a); // Displays the content without the -l parameter
int cal_row(char* *,int.int*,int*); // Provides the number of rows/columns to display for the column sorting algorithm
void mode_to_letters(int.char*); // In -l, convert the mode attribute to a string
char* uid_to_name(uid_t); // In -l, convert uid to a string
char* gid_to_name(gid_t); // In -l, convert gid to a string
// Global variables
int a_flag = 0; // Whether to take the -a parameter
int l_flag = 0; // Whether to take the -l parameter
char* dirnames[4096]; // Save the directory name temporarily
int dir_cnt = 0; // Number of directories
char* filenames[4096]; // Save the file name in the temporary directory
int file_cnt = 0;
int main(int argc,char* argv[])
{
// Store the file name and parameters
while(--argc){
++argv;
// An optional argument is encountered
if(*argv[0] = =The '-') {while(*(++(*argv))){
if(**argv == 'a'){
a_flag = 1;
}
else if(**argv == 'l'){
l_flag = 1;
}
else{ error_handle(*argv); }}}// The directory name is encountered
else{ dirnames[dir_cnt++] = *argv; }}if(dir_cnt == 0){
dirnames[dir_cnt++] = ".";
}
sort(dirnames,0,dir_cnt - 1);
// Handle the filename in filenames with different optional arguments
int i = 0;
DIR* cur_dir;
struct diren* cur_item;
// Walk through directory files
for(i = 0; i < dir_cnt; ++i){printf("Here is the content of" %s ":\n",dirnames[i]); do_ls(dirnames[i]); }}void do_ls(const char* dir_name)
{
DIR* cur_dir;
struct dirent* cur_item;
file_cnt = 0;
// Open the directory
if((cur_dir = opendir(dir_name)) == NULL){
error_handle(dir_name);
}
else{
// Read the directory and display the information
// Store the file name in the array
while((cur_item = readdir(cur_dir))){
restored_ls(cur_item,dir_name);
}
// lexicographical sort
sort(filenames,0,file_cnt- 1);
// Output the result
if(l_flag){
// With -l
show_with_l();
}
else{
// No -l argument
show_without_l();
}
// Free memory
int i = 0;
for(i = 0; i < file_cnt; ++i){free(filenames[i]);
}
// Close the directoryclosedir(cur_dir); }}void restored_ls(struct dirent* cur_item,const char* dir_name)
{
char* file_path = (char*)malloc(sizeof(char) *256);
strcpy(file_path,dir_name);
char* result = cur_item->d_name;
strcat(file_path,"/");
strcat(file_path,result);
// Hide files starting with '.' when no -a parameter is taken
if(! a_flag && *result =='. ') return;
filenames[file_cnt++] = file_path;
}
void show_without_l(a)
{
int i = 0;
int j = 0;
struct stat file_info; // Save the structure of the file attributes
// column sorting algorithm
int col = 0;
int col_max_arr[256];
int row = cal_row(filenames,file_cnt,&col,col_max_arr);
for(i = 0; i < row; ++i){for(j = 0; j < col; ++j){if((j*row+i) < file_cnt){
if(stat(filenames[j*row+i],&file_info) ! =- 1) {int mode = file_info.st_mode;
color_print(filenames[j*row+i],mode,col_max_arr[j]);
}
else{ error_handle(filenames[j*row+i]); }}}printf("\n"); }}void show_with_l(a)
{
struct stat info;
char modestr[11];
int i = 0;
for(i = 0; i < file_cnt; ++i){if(stat(filenames[i],&info) == - 1){
error_handle(filenames[i]);
}
else{
mode_to_letters(info.st_mode,modestr);
printf("%s",modestr);
printf("%4d ", (int)info.st_nlink);
printf("%-12s",uid_to_name(info.st_uid));
printf("%-12s",gid_to_name(info.st_gid));
printf("%-8ld ", (long)info.st_size);
showtime((long)info.st_mtime);
color_print(filenames[i],info.st_mode,0);
printf("\n"); }}}void showtime(long timeval)
{
char* tm;
tm = ctime(&timeval);
printf(24.24 "% s",tm);
}
void color_print(char* pathname,int filemode,int width)
{
// Intercepts the file name in the pathname
char* filename;
int len = strlen(pathname);
while(pathname[len] ! ='/'){
--len;
}
filename = &pathname[len+1];
if(S_ISDIR(filemode)){
printf("\033[01;34m%-*s\033[0m",width,filename);
}
else if(S_ISLNK(filemode)){
printf("\033[01;36m%-*s\033[0m",width,filename);
}
else if(S_ISFIFO(filemode)){
printf("\033[40;33m%-*s\033[0m",width,filename);
}
else if(S_ISSOCK(filemode)){
printf("\033[01;35m%-*s\033[0m",width,filename);
}
else if(S_ISBLK(filemode)){
printf("\033[40;33;01m%-*s\033[0m",width,filename);
}
else if(S_ISCHR(filemode)){
printf("\033[40;33;01m%-*s\033[0m",width,filename);
}
else if(S_ISREG(filemode)){
if(S_ISEXEC(filemode)){
printf("\033[01;32m%-*s\033[0m",width,filename);
}
else{
printf("%-*s",width,filename); }}else{
printf("%-*s",width,filename); }}int cal_row(char** filenames,int file_cnt,int* cal_col,int* col_max_arr)
{
// Get the length before the file name in the pathname
int path_len = strlen(filenames[0]);
while(filenames[0][path_len] ! ='/'){
--path_len;
}
++path_len;
struct winsize size;
ioctl(STDIN_FILENO,TIOCGWINSZ,&size);
int col = size.ws_col; // Get the width of the current window (characters)
int col_max = 0;
int cur_file_size = 0;
int filenames_len[file_cnt];
*cal_col = 0;
int i = 0;
int j = 0;
// Get the character length of each filename
for(i = 0; i < file_cnt; ++i){ filenames_len[i] =strlen(filenames[i]) - path_len + 2; // The string must contain at least two Spaces
// Special case: If the maximum string length is larger than the screen width, return file_cnt, column number: 1, maximum width: the maximum string length
if(filenames_len[i] > col){
*cal_col = 1;
col_max_arr[0] = filenames_len[i];
return file_cnt;
}
cur_file_size += filenames_len[i];
}
// Minimum number of lines to iterate on
int base_row = cur_file_size / col;
if(cur_file_size % col){
base_row++;
}
int flag_succeed = 0; // Indicate whether the arrangement is complete
// Start sorting
while(! flag_succeed){int remind_width = col; // The current available width
*cal_col = - 1;
for(i = 0; i < file_cnt; ++i){// If the remaining width is not enough to hold the current string, it jumps out and allocates additional line space
if(filenames_len[i] > remind_width){
break;
}
// A new column
if(i % base_row == 0){
++(*cal_col);
col_max_arr[*cal_col] = filenames_len[i];
}
else{
col_max_arr[*cal_col] = (filenames_len[i] > col_max_arr[*cal_col]) ? filenames_len[i] : col_max_arr[*cal_col];
}
// The last line updates the remaining width
if(i % base_row == base_row - 1){ remind_width -= col_max_arr[*cal_col]; }}// Check whether the array is complete
if(i == file_cnt){
flag_succeed = 1;
}
// Reallocate additional row space
else{
int extra = 0; // The number of additional characters required
while(i < file_cnt){
extra += filenames_len[i++];
}
if(extra % col){
base_row += (extra / col + 1);
}
else{
base_row += (extra / col);
}
}
}
++(*cal_col); // The columns start at 0, so we increment them by 1
return base_row;
}
void mode_to_letters(int mode,char* str)
{
strcpy(str,"-- -- -- -- -- -- -- -- -- --"); // File type and permission, first occupy 10 pits
// Only three of the seven common file types are converted here
if(S_ISDIR(mode)) str[0] = 'd';
if(S_ISCHR(mode)) str[0] = 'c';
if(S_ISBLK(mode)) str[0] = 'b';
// Permission conversion
// Current user permission
if(mode & S_IRUSR) str[1] = 'r';
if(mode & S_IWUSR) str[2] = 'w';
if(mode & S_IXUSR) str[3] = 'x';
// Permissions of other users in the current group
if(mode & S_IRGRP) str[4] = 'r';
if(mode & S_IWGRP) str[5] = 'w';
if(mode & S_IXGRP) str[6] = 'x';
/ / other
if(mode & S_IROTH) str[7] = 'r';
if(mode & S_IWOTH) str[8] = 'w';
if(mode & S_IXOTH) str[9] = 'x';
}
char* uid_to_name(uid_t uid)
{
struct passwd* pw_ptr;
static char numstr[10];
if((pw_ptr = getpwuid(uid)) == NULL) {sprintf(numstr,"%d",uid);
return numstr;
}
else{
returnpw_ptr->pw_name; }}char* gid_to_name(gid_t gid)
{
struct group* grp_ptr;
static char numstr[10];
if((grp_ptr = getgrgid(gid)) == NULL) {sprintf(numstr,"%d",gid);
return numstr;
}
else{
returngrp_ptr->gr_name; }}void error_handle(const char* name)
{
perror(name);
}
Copy the codeconclusion
The ls display effect is optimized and LS – L is realized. Ls-l is a bit more business, need to carry out multiple format conversion processing, algorithm without too many stumbling points, relatively smooth. Most of the author’s time has been spent on the implementation of ls’s “column algorithm”, which is worth studying the algorithm logic, and there must be a better optimization algorithm. What looks like a very simple LS display contains a lot of technical details, which is the charm of Linux.
The resources
Understanding Unix/Linux Programming A Guide to Theory and Practice
I also have a personal blog: Lularible’s personal blog. Please visit it.