cgcs_vector

A data structure for the C language; a buffer (vector) of pointers.

Note:
This document, and this repo -- is a work in progress.

Directories:

demo - target to demonstrate usage of cgcs_vector

• cgcs_vector_demo.c
  • demonstrates usage of cgcs_vector.
• CMakeLists.txt
  • cmake instructions on building this target

src - target for cgcs_vector library

• cgcs_vector.c
  • Implementation details
• cgcs_vector.h
  • Public declarations

Building:

Run the included makebuilds script to have cmake
create Unix-Makefile builds in the following modes:

• Debug
• Release
• MinSizeRel
• RelWithDebInfo

% ./makebuilds

A build/make subdirectory will be created with subdirectories
of the modes described above.

If we want to create a Debug build of our demo program (which will also build the cgcs_vector library):

make -C ./build/make/Debug/demo

Generally,

make -C ./build/make/[build-mode]/[target-name]

If you want to use an alternative build system, i.e. Xcode or Visual Studio
(see the list of supported generators on your system using cmake -help), invoke the following:

% cmake -S ./ -B ./build/[generator-name] -G "[generator-name]"

For example, for Xcode:

% cmake -S ./ -B ./build/xcode -G "Xcode"

Foreword on struct cgcs_vector, aka cgcs_vector

The C language leaves it up to the user to create their own data structures.
Whenever I would write C++, I would always be grateful for std::vector,
as it is a very useful data structure to have, it's versatile, and it's fast.

My goal with cgcs_vector is to have a data structure
that can be just as useful, when you must program in C.

I have been down this rabbit hole before, with one of my previous repositories,
gcslib, which was meant to be an entire container library for C, which was loosely inspired by the C++ STL.
Over time, I ended up abandoning it, realizing that I had over engineered everything.

In practice, all I ever really needed was a useful "vector" data structure,
so I think it's best to focus my sights on that.

Although I am taking inspiration from C++, there is no use in trying to reinvent the wheel.
I also don't think there is much use in trying to implement "generics",
or to create too many abstractions.

In the gcslib repository, there is a subdirectory, test__vptr --
and this new repo is pretty much picking up where I left off with test__vptr.

struct cgcs_vector's alias, or typedef is vector_t.

How is it implemented

Often times while writing in C, large objects (instances of struct),
or strings (represented as char *) have to be dynamically allocated.
We do not have constructors/destructors, references, or RAII in C.

I have decided to implement cgcs_vector as follows
(The memory layout is inspired from the GCC implementation of std::vector)

typedef struct cgcs_vector vector_t;
typedef void *voidptr;                      
typedef voidptr *vector_iterator_t;

// The "vector" structure
struct cgcs_vector {
    struct cgcs_vector_base {
        voidptr *m_start;
        voidptr *m_finish;
        voidptr *m_end_of_storage;
    } m_impl;
};

We are ultimately dealing with a buffer of pointers.
Each block is sizeof(void *) bytes large.

• typedef struct cgcs_vector cgcs_vector_t

  We alias struct cgcs_vector with vector_t.

• typedef void * voidptr

  m_start in struct cgcs_vector_base
  is a pointer that addresses a buffer of pointers.
  By aliasing void *, I believe this idea is made clearer.

  m_finish addresses one-past the last block in m_start.
  If m_start and m_finish are the same address, m_start is an empty buffer.

  m_end_of_storage addresses the last block in m_start.
  If m_finish and m_end_of_storage are the same address,
  the buffer will be full after using the space at m_finish.

• typedef voidptr *vector_iterator_t

  Since we can do pointer arithmetic on a voidptr *, or void **,
  we will alias it so that the user knows that it can be used as an iterator.

Sample Usage

TODO - please see comments/documentation for now.