Another C Library Table of Contents

• Copyright 2019 Andy Curtis and Daniel Curtis

The book/code started in August 2019, so it's a work in progress. This is not a usage book. I'm working on a book that simply explains usage. I'm following patterns used by https://nikhilm.github.io/uvbook/index.html. I think you create velocity by slowing down and making sure that you always have understanding of what you are doing (or at a minimum make sure you have an understanding of what you don't understand). Developers get better when they can explain what they know (and this is independent of language or technology). Becoming a great developer takes practice. This book may take several reads before you fully get it. The examples intentionally build upon each other, but may build too quickly for some. Feel free to send me an email at contactandyc@gmail.com if you have questions.

This software and documentation contains code and ideas derived from works published by Robert Sedgewick relating to the Red-Black Tree and the Quicksort algorithm. Many other works (both code and explanations) were studied. I've spent years studying many open source implementations including the details of the linux kernel, so I'm sure you will see their influence in how the code is written. I have tried to write the code without borrowing any code or explanations from other projects, but I'm sure that approaches, variable names, etc will look similar. I've worked with brilliant engineers over the years and certainly borrowed approaches from their work. I will try and call out where I have learned things when it is relevant (and I remember). I'm sure that there are better ways to do things and welcome help!

Goals of this project...

1. To provide an open source collection of algorithms necessary to build complex applications
2. To help engineers understand algorithms and C better, so that they can create their own
3. To show that it is possible to overcome many of the known challenges in C
4. To help people to learn what it takes to create something new
5. Build scalable applications using technology like Kubernetes, nginx, and docker.

My hope is that others will contribute!

One of my favorite books is the Introduction to Algorithms by MIT Press. I've often wondered if there was a follow up book (as the implication in the title is that it is for beginners). I believe that the author wanted to convey that one should understand known algorithms to build better algorithms. To that end, I found an improvement to quicksort. I have no idea if my improvement to quicksort is new. I could not find it in any existing open source implementation. Read about it on Medium or LinkedIn

git clone https://github.com/contactandyc/another-c-library.git
cd another-c-library/demo
make

The ac_schedule is demonstrated in a second demo directory named scheduler_demo. This demos how to chain input together through a variety of sorts and merges to produce a final output. In addition, the sorts and merges will work within the confines of the environment described by the user. This is something like the hadoop map/reduce framework only written in C (and at the moment, only capable of supporting one box). This framework attempts to stay out of your way, but also provides a number of useful utilities to get common work done.

cd ../scheduler_demo
make
./word_demo -h
./word_demo .. --cpus 4

The package depends on libuv in the uvdemo directory. On a mac, use the following command to install libuv.

brew install libuv
cd another-c-library/uvdemo
make

1. Getting Started
2. Timing Your Code (the first project)
   a. A brief introduction to C
   b. What happens during compilation
   c. How to time code
   d. Reversing a string
   e. The basic Makefile
   f. More accurately timing code
   g. Compiler optimizations
   h. Splitting up code into multiple files
   i. Separating the implementation from the interface
   j. Defining an object
   k. The timer interface
   l. Making the timer object reusable
   m. Splitting up a project into multiple directories
   n. Splitting up the Makefile
   
3. The Buffer Object
   a. How it compares to other languages
   b. A bit of history and setup
   c. The buffer interface
   d. The implementation
   
4. Linked Lists
   a. A data structure interface
   b. The data structure interface test driver
   c. The singly linked list
   d. The doubly linked list
   
5. Threads
   a. Introducing threads
   b. Creating threads
   c. Threads and optimizing code
   d. Avoid global variables when you can
   e. Mutexes
   f. Timing considerations
   
6. Macros
7. The Global Allocator Object
8. The Global Allocator Implementation
9. The Pool Object
10. Binary Search Trees
    a. The basic structure
    b. Find
    c. Insert
    d. First, Last, Next, Previous
    e. Erase
    f. Postorder iteration
    g. Printing a binary tree
    
11. Balancing Binary Search Trees
    a. Why balancing is important
    b. Properties of a red black tree
    c. Coloring
    d. Rotations
    
12. The Red Black Tree
    a. Testing the red black tree properties
    b. Insert
    c. Erase
    d. Packing color into the parent node
    
13. (Started 9/23/19) Turning the Red Black Tree into a map
14. The set and multimap
15. (Coming soon!) Building a generic least recently used cache
16. (Coming soon!) Binary search
17. (Coming soon!) Heaps and priority queues
18. (Coming soon!) Quicksort
19. (Coming soon!) Building web services in C

Things that have been helpful to me

1. Line spacing in markdown
2. Escape characters in markdown
3. Create multiline macro in C
4. Static inline vs inline
5. Regex find replace
6. Atom-beautify problems

Some useful reading...

This book assumes you have a basic understanding of C. I hope to show some tricks along the way, but you should have a basic understanding of the language before continuing. You should also know machine architecture, multithreaded programming, the bash shell, and probably read over kubernetes tutorials. I like to avoid thread contention, context switching, and optimize cpu caching in multithreaded programming (which this will be). To do this, I believe that you need to avoid locking as much as possible and carve out different spaces in RAM for each thread to operate in. It's good to understand machine architecture to really understand optimizations.

Markdown (how to write this)

Markdown Cheatsheet

C Tutorials

https://www.programiz.com/c-programming
https://www.tutorialspoint.com/cprogramming/
https://www.learn-c.org
https://www.guru99.com/c-programming-tutorial.html
https://www.javatpoint.com/c-programming-language-tutorial

Understanding the machine

Why software developers should care about CPU caches

Let's get started!