File	Date	Author	Commit
Samples	2018-11-13	cc	[e015cc] Commit
src	2018-11-13	cc	[e015cc] Commit
NOTICE	2018-10-15	cc	[b99288] Commit
README	2018-11-13	cc	[e015cc] Commit

Read Me

About StoneValley Project

i   Preface

	*) The author claimed that he does will refine source files and references later.
	*) Caution that there are still some bugs hide in function "treBPTRemove" at "svstree.c".
	*) The author of this library needs time and arms to fix it.
	*) Should you have any problems with this library, please do not hesitate to contact me via Email.

ii  Acknowledgment

	*) The whole project is published under Public Domain license.
	*) StoneValley is provided with NO warranty.
	*) Bugs may cause nuisances in StoneValley, although this library has been tested for a considerable quantity of times. So, JBC(Just Be Careful).

iii Table of Contents

	[Contents]                                                    [Line number]
	Preface ................................................................. 3
	Acknowledgment ......................................................... 10
	Table of Contents ...................................................... 16
	Senario ................................................................ 31
	Function Naming ........................................................ 51
	Callbacks .............................................................. 59
	Checklist .............................................................. 63
	Alteration Guide ...................................................... 113
	Limitations ........................................................... 155
	Logs .................................................................. 170
	Appendix .............................................................. 193

iv  Senario

	StoneValley is a program library that was written in plain C programming language and aimed at providing its users a set of functions with a variety of algorithms that could manipulate various data structures. This Readme file briefly introduced this library in a users’ perspective. Contents in this Readme file guide users in an approaching procedure of what it is, how to use it and how to reprogram it in a block of extra instructions. To advance and fully control this library need users to practice programming with it.

	The whole library has been divided into several parts. There are String, Stack, Queue, Tree, Hash table, Graph and Set.

	String part is a collection of linear data structures. It contains array, single linked-list, doubly linked-list, bit-stream and bit-matrix. Functions that operate on linear data structures were exported into file "svstring.h". And StoneValley has separated declarations about these functions into file "svatom.c", "svarray.c", "svlist.c" and "svmisc.c".

	File "svstack.c" implemented stack data structures. And functions for stacks have been exported into file "svstack.h". Two types of stack implementations involved in this library. They are fixed size array type and single linked-list type. Fix-size-array stacks are suitable to use in memory-space-concerned situations. While linked-list stacks are convenient to use for circumstances of dynamic memory allocations.

	Functions for queues were exported into "svqueue.h" and simultaneously implemented in file "svqueue.c". Three types of queue implementations have been written in StoneValley. The fixed size array implementation for circular queues and the single linked-list implemented queues were both collected in the library. And a doubly linked-list achievement for dequeues(Double-Ended Queues) also involved in this library. Like stacks, users may use fix-size-array queues to strictly control memory spaces. If users need to allocate memory spaces dynamically, linked-list queues are accessible to work.

	Too many tree data structures appear in this world. StoneValley cannot gather them one by one but instead of achieving a few important tree data structures. Binary trees use doubly pointer nodes; generic trees use arrays; heap trees use fixed size arrays and BSTs(Binary search trees) utilized AA-trees. Another searching/indexing tree occupied in the library is a B-Plus tree. Finally, a Huffman-coding tree settled in StoneValley at file "svctree.c". As the same manner, StoneValley exported these functions into a header file named "svtree.h". Diverse types of trees were implemented in different source files. These source files are "svbtree.c", "svgtree.c", "svhtree.c", "svstree.c" and "svctree.c" for the reason that "b" denotes "binary", "g" means "generic", "h" dictates "heap", "s" indicates "searching" and "c" represents "coding".

	Header file "svhash.h" contains function definitions for hash tables. Separate chaining hash tables use linked-lists as buckets. And the array type is directly used for open addressing hash tables. All functions for hash tables outputted into "svhash.c".

	Sets using hash tables or Binary-search-trees to manage their elements. Interfaces for sets in StoneValley were collected into file "svset.h". Implementations were written in "svset.c".

	File "svgraph.c" schemes graph data structures. And functions for graphs should be interfaced with "svgraph.h".

v  The naming of types and library functions

	There is a guideline to name functions and types in StoneValley. For functions, such as function "stkInitA", the suffix "stk" means this function belongs to a group of stack structures. Users should include "svstack.h" first to use this function. Infix "Init" means to initialize a stack structure. The final "A" denotes that this function is used to initialize a stack which uses an array to form the stack itself. Thus, "stkInitL" can be interpreted to initialize a stack of which uses a linked list to manage. Have a notice that there is a difference between the word "Init" and "Create" in StoneValley. "Init" meant to initialize an object which already exists in main memory. That was "Init" functions could be used if structures had been declared first. Then, users would pass the address of a structure to the parameter of an "Init" function to initialize the structure. By contrary, functions contain the word "Create" will create a new structure in main memory in the beginning and return a pointer to this structure at the end of its execution. If an "Init" function were used to allocate a structure, respectively, a free function should be in use to deallocate this structure. In the same way, if a creation function were adopted to fetch a pointer of a structure, a deletion function would be required to erase memories of this pointer addressed later.

	The naming for types is tricky. For example, "STACK_A" is a type of a stack, and this stack consists of an array. And "P_STACK_A" is a pointer to this array implemented stack. Type "HSHSET" at "svset.h" derived from type "HTCHG". It is not hard to image the implication of this kind of naming. It says a set that uses a hash table to approach derived from a chaining hash table structure. Certainly, the pointer to a hash table implemented set is called "P_HSHSET". Naming guidelines for function parameters are feasible to understand. For instance, "PSET", the first parameter of function "setInitH_O" at "svhash.h" means users should transfer a pointer to a hash table implemented set into this parameter while invoking function "setInitH_O". Some parameters like "CBF_HASH" means users should pass a pointer to a hash function while invoking the callee.

	Finally, a function name like "setSizeT_O" explored that there must be a macro to inline this function and the macro is called "setSizeT_M" for the reason that letter "O" instead of an original function declaration and function with letter "M" tailed is its macro version. Inline functions by using macros could avoid conflicts during linkage. But the drawback of macro-inline is that library maintainers have to write one function for twice. Firstly, maintainers should write a function for the original edition. Secondly, library maintainers need to write it again for its macro version. It seems to be verbose but it is useful in a variety of compiling environments.

vi  Callback functions and their usage

	Another important point of StoneValley is to use callback functions. There are two main types of callback functions. One is the type of callback function that used to traverse items in structures. The other is the type of callback function that used to compare values by pointers. The first one is named as "CBF_TRAVERSE". The second one is labeled as "CBF_COMPARE". Details about how to use these two types of callback functions are located at file "svdef.h". Additionally, two important values of callback function "CBF_TRAVERSE" returns are "CBF_TERMINATE" and "CBF_CONTINUE". 0, 1 and -1 will be returned after calling a "CBF_COMPARE" function. The callee for caller callback functions should obey their specific calling conventions.

vii Here is a simple checklist. Please retrieve it before you compile this library.
	 _________________________________________________________________
	|                # BEFORE COMPILING CHECK LIST #                  |\
	|_____[ITEM]___________[TYPE]_____[LINES]_____[FILE]_____[MARK]___|\
	| [_] DWC4100           MACRO       66         SVDEF.H    ALTER   |\
	| [_] REGISTER          MACRO       69         SVDEF.H    CONFIRM |\
	| [_] SV_OPTIMIZATION   MACRO       77         SVDEF.H    ALTER   |\
	|                                                                 |\
	| ALTER:   Alter item if necessary.                               |\
	| CONFIRM: Confirm item before compiling.            StoneValley. |\
	|_________________________________________________________________|\
	 \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
	 
	Non-normal handling:
	(Guiding actions will use upper case letters to type.)
	
	1) Errors of missing.
		In some environments, especially when users try to compile StoneValley
		on an embedded platform, because of the lack of supporting of the C 
		standard library, compilers will produce errors. For instance, if there
		were not installed the header file "stdio.h", compilers might explain
		an error about missing macro 'BUFSIZ' for the library source file
		"svmisc.c". In this circumstance, users shall simply IMPLEMENT macro
		'BUFSIZ' by themselves. In another way, users shall COLLECT missing
		macros in a header file that has the same name with the original header
		in the C standard library.
		
		If some C standard library functions that being used by functions in
		StoneValley were not implemented, compiler/linker would report errors
		about missing symbols while linking. There are two ways to handle a
		missing of C standard library functions. First, IMPLEMENT the C standard
		library functions on users' own. Second, REMOVE functions that use missing
		C standard library functions in StoneValley directly.
		
	2) Warnings of inline function expansion.
		Most optimizing compiler will automatically expand inline functions for
		a better performance. In general, library users could NEGLECT those
		warnings when compilers were attempting to expand inline functions.
		
	3) Warnings of library function returns.
		Some compilers installed with code analysis technics would check return
		values of functions in the C standard library. For example, it would check
		if the realloc function might return a NULL pointer to its left-hand-side
		expression. Library users could IGNORE these types of warnings.
		
	4) Other concerns.
		If an architecture did not support to use too many register variables,
		compilers would produce warnings. Library users could comment the
		'REGISTER' macro at file “svdef.h” or IGNORE compiler produced warnings.

viii Library Alteration Guide

	This short instruction will guide you fix the library.

	a] Altering an existed function in the library:

		1. Alter a function and check whether it has a macro version.

		2. If the function you amended has a '_O' sign at the tail of its name,
	       then both alter its macro version in the proper header file.

		3. If the original function has NO return value and it is simple,
	       write its macro version and use '{}' to brace it in multiple lines.

		4. If the original function HAS a return value and it is brief,
	       write its macro version in one line and use '()' to brace it.

		5. Altering is done.

	b] Adding a non-exist function into library:

		1. Write a definition for a new function.

		2. If the new function you wrote needs another callback function,
		then write the callback function for it. Then add an underscore '_' at the
		beginning of the callback function to declare it as an internal function.

		3. If you wrote a definition for a callback function, both implement its
	       declaration at the top of the current file section.

		4. Implement a declaration for your original new wrote function into proper
	       header file.

		5. If you need to inline a new wrote function, write a macro version in
	       the appropriate header file. And plus a '_O' to the end of the original one.
	       Both plus a '_M' sign to its macro version at header file.

		6. Put either the original function or its macro version into the right
	       place at the bottom of header file to optimize the performance of library.

		7. Addition is done.

ix  Limitations

	Dependencies:
		Despite some of the fundamental functions in StoneValley can be run without
		The C Standard Library, most part of this library needs dynamic memory allocation
		functions like 'malloc' and 'realloc' of The C Standard Library.

	Addressing:
		'size_t' which is a type of unsigned long integer is the most important data type
		of this library.

		The length of a 'size_t' integer depends on the specific machine environment that
		implements C programming language, and then the length of a size_t integer limits
		the addressing capability of most data structures in StoneValley.

x   Logs

12-26-2017: Bug fixed in Huffman coding tree.
12-26-2017: Samples are added.
12-27-2017: Samples are added.
12-28-2017: Samples are added. Docs refined. I gonna be in retired this year. Happy new year! Welcome 2018!
01-17-2018: Samples are added.
05-04-2018: A bug is fixed in function strTraverseArrayZ at file "svarray.c".
05-05-2018: Docs are refined.
05-18-2018: Library is refined.
08-31-2018: Library is refined. I hope this version of library should not be an anti-human edition for most English speakers. The idea of which impressed me was it was important to practice it when you were trying to learn a language. In a word, the lib now is readable at least.
09-24-2018: Library is refined. File "svstree.c" is altered. AA-tree is added. Macros are fixed.
09-25-2018: Bit-matrices were fixed. A sample is added to repository.
09-26-2018: A sample is added to repository. Library is refined.
10-02-2018: Library is refined.
10-02-2018: A name converting program is added.
10-11-2018: Library is refined. Refreshing rate will be reduced in the future, unless a new data structure has been introduced into library.
10-14-2018: A grammatical error was fixed. A verbose comment has been deleted. A logical mishap has been corrected. Heap tree was revised.
10-16-2018: Documents are refined.
10-24-2018: Library is refined.
11-07-2018: Library is refined.
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

xi  The Story of StoneValley

Part I The name of StoneValley

	When I finished my first hand-writing lexer in plain C, I decided to name it into BlueStone. After that, I planned to write my parser. And I have already named my unfinished parser into RedStone. However I didn't finish that, because I’ve learned to use Yacc. its much faster and better than the hand-write one. My third project in C was going to be a term rewriting system. But at that time I realized that I need a library in C just like the STL template provided by C++. STL in C++ is a good stuff, but I want a new one in plain C. And I think this library will be tremendously large than I ever write. It will contain a massive number of functions. And users can cut them into their own project. Each function is like a color of a stone. So I decided to name my new library into StoneValley. That's the story of the name StoneValley. After wrote the project GILIB. I realized a robust library is more important than a library with innovation. A library is that kind of software for programmers using. Not as the same as applications. So they must be robust and more bugless. After thinking about these ideas, I was starting to write StoneValley.

Part II Tui and Qiao

	Tang dynasty, ancient China. There was a bard named JiaDao(贾岛). One day, he was sitting on a donkey and conceiving his poem. "鸟宿池边树，僧敲月下门。”Which can be roughly translated into "Beside the pond, birds were sleeping in the tree. There was a monk knocking at the door in the moonlight."

	Then he was stuck at the word Tui(推) or Qiao(敲). He could not determine that whether he should use Tui means to push or Qiao means to knock. But even though was excising pushing and knocking again and again on the donkey’s back, he couldn’t make a decision.

	About 1300 years after. I am sitting in front of the computer and thinking about the StoneValley library. Time passing by, issues are accumulated. I can’t determine whether I should divide these abstract data type apart into any files, and whether I should use a hash table or a binary search tree to construct the set. Even I can’t determine whether I should use str or lnr as the prefix of functions of linear structures.

	StoneValley is really hard to control. If I want a super-fast running speed for functions in this library. I can’t get a super small library size. To be or not to be, this is still a question. Like the bard, I’m stuck at the library’s pivot. But like the bard, I don’t forget what I really want. It is a robust and reusable data structure library.

	So nearly one year, I was trying my best to write StoneValley. I tuiqiao every function in the library again and again. There is a word wrote on essay The Cathedral and The Bazaar "A good design is not have nothing to add. It should be nothing to reduce from the design." That inspired me to finish StoneValley better. But the best is not reachable. The best can only be a forever target. StoneValley is not the best library now. And It can’t be the best library forever. I’m willing to make StoneValley better and better in the next days.

Enjoy!