Skip to content

Instantly share code, notes, and snippets.

@dbremner dbremner/main.c
Last active Feb 5, 2018

Embed
What would you like to do?
Memory Safety in Rust : A Safer C Implementation
#include "vec.h"
int main(void) {
Vec* vec = vec_new();
//vec is a pointer to a struct of an unknown type
//so the compiler will not allow bugs 6 and 7 to occur.
vec_push(vec, 107);
vec_push(vec, 110);
vec_free(vec);
}
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include "vec.h"
// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
struct vec{
size_t mark; // Used to detect invalid objects
int* data; // Pointer to our array on the heap
size_t length; // How many elements are in our array
size_t capacity; // How many elements our array can hold
};
static const size_t kVecMark = 65521; //the Adler prime
static const size_t kVecMarkFreed = 0xdeadbeef;
static const size_t kInitialCapacity = 16;
static const size_t kFreedCapacity = 13;
Vec* vec_new(void) {
Vec *vec = calloc(1, sizeof(*vec));
int *data = calloc(kInitialCapacity, sizeof(int));
if (!vec) {
goto failure;
}
if (!data) {
free(vec);
goto failure;
}
vec->data = data;
vec->length = 0;
vec->capacity = kInitialCapacity;
vec->mark = kVecMark;
return vec;
failure:
exit(EXIT_FAILURE);
}
static bool check_nonnull_vec(Vec *vec)
{
const uintptr_t value = (uintptr_t)vec;
//malloc and calloc must return memory that is
//aligned properly for all standard types.
const bool valid_alignment = (value & 7) == 0;
if (!valid_alignment) {
return false;
}
if (vec->mark != kVecMark) {
return false;
}
if (vec->data == NULL) {
return false;
}
const bool over_initial = vec->capacity >= kInitialCapacity;
if (!over_initial) {
return false;
}
const bool valid_capacity = vec->capacity >= vec->length;
if (!valid_capacity) {
return false;
}
return true;
}
static bool check_vec_push_argument(Vec *vec)
{
if (!vec) {
return false;
}
const size_t max_capacity = (size_t)-1;
const bool can_add_capacity = vec->capacity < max_capacity;
if (!can_add_capacity) {
return false;
}
return check_nonnull_vec(vec);
}
void vec_push(Vec* vec, int n) {
if (!check_vec_push_argument(vec)) {
goto failure;
}
if (vec->length == vec->capacity) {
size_t new_capacity = vec->capacity * 2;
if (new_capacity < vec->capacity) {
goto failure;
}
//let cap = vec->capacity
//(cap * 2) * sizeof(int) == cap * (sizeof(int) * 2)
//Using the RHS instead of the LHS allows calloc
//to detect overflow if a compiler removes
//the previous check. Some compilers have
//an option to make unsigned overflow undefined.
int* new_data = (int*) calloc(vec->capacity, sizeof(int) * 2);
if (!new_data) {
goto failure;
}
for (size_t i = 0; i < vec->length; ++i) {
new_data[i] = vec->data[i];
}
free(vec->data);
vec->data = new_data;
vec->capacity = new_capacity;
}
vec->data[vec->length] = n;
++vec->length;
return;
failure:
exit(EXIT_FAILURE);
}
void vec_free(Vec* vec) {
if (!vec) {
return;
}
if (!check_nonnull_vec(vec)) {
exit(EXIT_FAILURE);
}
free(vec->data);
vec->data = NULL;
vec->mark = kVecMarkFreed;
vec->capacity = kFreedCapacity;
free(vec);
}
#ifndef VEC_H
#define VEC_H
typedef struct vec Vec;
//public API of Vec which hides the internals
Vec* vec_new(void);
void vec_push(Vec* vec, int n);
void vec_free(Vec* vec);
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.