tcler's blog --- 其实我是一个程序员
Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.

创建递归目录树

昨天 Zorro 在鼓捣一个C程序，看见我问怎么用递归方法创建一个递归的目录树结构: 指定子目录数量和层数。递归太烧脑，想了想可以用循环实现，很久没写C了，写写练习一下:

create_dirtree.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <errno.h>

uint64_t power_uint(uint64_t base, int x)
{
	uint64_t sum = 1;

	for (int i=0; i<x; i++) {
		sum = sum * base;
	}

	return sum;
}

/*
 * do the action like "mkdir(1) -p"
 */
int mkdir_p(char * path)
{
	char * ptr = NULL;
	int i, len, ret;

	len = strlen(path);
	if (NULL == (ptr = malloc(len + 2))) {
		return (-1);
	}
	strcpy(ptr, path);

	/*
	 * convert "a/b/c/d" to "a/b/c/d/"
	 */
	if (ptr[len - 1] != '/') {
		ptr[len] = '/'; ptr[len + 1] = '\0';
	}

	/*
	 * create dir recursively
	 */
	for (i = 1; i < len + 1; i++) {
		if (ptr[i] == '/') {
			ptr[i] = '\0';
			ret = mkdir(ptr, 0755);
			if (ret < 0 && errno != EEXIST) {
				free(ptr);
				return (-1);
			}
			ptr[i] = '/';
		}
	}

	free(ptr);
	return (0);
}

int main(int argc, char *argv[])
{
	uint64_t base = (uint64_t)atoll(argv[1]);
	int x = atoi(argv[2]);

	uint64_t leafn = power_uint(base, x);
	printf("%lu ^ %u = %lu\n", base, x, leafn);

	char path[PATH_MAX] = {0};
	uint64_t *binpath = calloc(sizeof(uint64_t), (size_t)x);

	for (uint64_t i = 0; i < leafn; i++) {
		path[0] = '\0';
		uint64_t S = i;
		for (int j = 0; j < x; j++) {
			binpath[j] = S % base;
			S = S / base;
			if (S == 0) {
				break;
			}
		}
		for (int k = x-1; k >= 0; k--) {
			sprintf(&path[0]+(strlen(path)), "%lu/", binpath[k]);
		}
		mkdir_p(path);
	}
	return 0;
}

因为偷懒实现了一个 mkdir_p()，问题被简化了，但是这样会有很多冗余的 mkdir(2) 调用，如果节点数量很多的话浪费性能。所以给 mkdir_p() 增加第二个参数，避免无用的mkdir(2)调用:

create_dirtree2.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <errno.h>

uint64_t power_uint(uint64_t base, int x)
{
	uint64_t sum = 1;
	int i = 0;

	for (i=0; i<x; i++) {
		sum = sum * base;
	}

	return sum;
}

/*
 * do the action like "mkdir(1) -p"
 */
int mkdir_p(char * path, int skip)
{
	int i, len, ret, depth = 0;
	int syscalln = 0;
	char ptr[PATH_MAX] = {0};

	len = strlen(path);
	strcpy(ptr, path);

	/*
	 * convert "a/b/c/d" to "a/b/c/d/"
	 */
	if (ptr[len - 1] != '/') {
		ptr[len] = '/'; ptr[len + 1] = '\0';
	}

	/*
	 * create dir recursively
	 */
	depth = skip;
	for (i = 1; i < len; i++) {
		if (ptr[i] == '/' && depth-- <= 0) {
			ptr[i] = '\0';
			ret = mkdir(ptr, 0755);
			++syscalln;
			if (ret < 0) {
				if (errno != EEXIST) {
					fprintf(stderr, "[Err] mkdir(%s in %s) %d, %d, %s\n", 
							ptr, path, skip, depth, strerror(errno));
					return (syscalln);
				} else {
					fprintf(stderr, "[War] mkdir(%s in %s) %d, %d, %s\n", 
							ptr, path, skip, depth, strerror(errno));
				}
			}
			ptr[i] = '/';
		}
	}

	return (syscalln);
}

int main(int argc, char *argv[])
{
	uint64_t base = (uint64_t)atoll(argv[1]);
	int x = atoi(argv[2]);
	int syscalln = 0;

	uint64_t leafn = power_uint(base, x);
	printf("%lu ^ %u = %lu\n", base, x, leafn);

	char path[PATH_MAX] = {0};
	uint64_t *binpath = calloc(sizeof(uint64_t), (size_t)x);

	uint64_t i = 0;
	for (i = 0; i < leafn; i++) {
		path[0] = '\0';
		uint64_t S = i;
		int j = 0;
		int skip = 0;
		skip = x - 1;

		for (j = 0; j < x; j++) {
			binpath[j] = S % base;
			S = S / base;
			if (S == 0) {
				break;
			}
		}

		/* generate the path */
		int k = 0;
		for (k = x-1; k >= 0; k--) {
			sprintf(&path[0]+(strlen(path)), "%lu/", binpath[k]);
		}

		/* fix skip level */
		int n = 0;
		for (n=0; n<x-1; n++) {
			if (binpath[n] != 0)
				break;
			--skip;
		}

		if (skip != (x-1)) {
			syscalln += mkdir_p(path, skip);
		} else {
			int ret;
			ret = mkdir(path, 0755);
			++syscalln;
			if (ret < 0) {
				fprintf(stderr, "[Err] mkdir(%s) %d, %s\n", 
						path, skip, strerror(errno));
			}
		}
	}

	printf("mkdir syscalln = %d\n", syscalln);
	return 0;
}