c-programming

Simple C programs
git clone git://git.laack.co/c-programming.git
Log | Files | Refs

dynamic-array.c (2358B)

      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 
      4 typedef struct{
      5     int* data;
      6     int size;
      7     int capacity;
      8 }DynamicArray;
      9 
     10 DynamicArray* makeArr(int* data, int size){
     11     int capacity = size * 2;
     12     DynamicArray* result = malloc(sizeof(DynamicArray));
     13 
     14     int* localData = malloc(capacity * sizeof(int));
     15     for(int i = 0; i < size; ++i){
     16         localData[i] = data[i];
     17     }
     18 
     19     result->data = localData;
     20     result->size = size;
     21     result->capacity = capacity;
     22     return result;
     23 }
     24 
     25 
     26 void extendArr(DynamicArray* arr){
     27     int resultingCap = arr->capacity * 2;
     28     if(resultingCap == 0){
     29         resultingCap = 1;
     30     }
     31     int* newArr = malloc(resultingCap * sizeof(int));
     32     for(int i = 0; i < arr->size; ++i){
     33         newArr[i] = arr->data[i];
     34     }
     35     free(arr->data);
     36     arr->data = newArr;
     37     arr->capacity = resultingCap;
     38 }
     39 
     40 void printArr(DynamicArray* arr){
     41     for(int i = 0 ; i < arr->size; ++i){
     42         printf("%3d: %4d\n", i, arr->data[i]);
     43     }
     44 }
     45 
     46 void arrAppend(DynamicArray* arr, int element){
     47     if(arr->capacity > arr->size){
     48         arr->data[arr->size] = element;
     49         arr->size += 1;
     50     }
     51     else{
     52         extendArr(arr);
     53         arrAppend(arr, element);
     54     }
     55 }
     56 
     57 void arrCompress(DynamicArray* arr){
     58     int resultingCap = arr->size;
     59     int* newData = malloc(sizeof(int) * resultingCap);
     60     for(int i = 0; i < arr->size; ++i){
     61         newData[i] = arr->data[i];
     62     }
     63     free(arr->data);
     64     arr->data = newData;
     65     arr->capacity = resultingCap;
     66 }
     67 
     68 
     69 void arrPop(DynamicArray* arr){
     70 
     71     if(arr->size == 0){
     72         return;
     73     }
     74     // if it is at least half full, no need to resize
     75     if(arr->size > arr->capacity/2){
     76         arr->size -= 1;
     77     }
     78     else{
     79         arrCompress(arr);
     80         arrPop(arr);
     81     }
     82 }
     83 
     84 int main(){
     85 
     86     for(int i = 0; i < 10; ++i){
     87 
     88 
     89         int size = 0;
     90         int data [size];
     91 
     92         DynamicArray* arr = makeArr(data, size);
     93 
     94         for(int i = 0 ; i < 1000000; ++i){
     95             arrAppend(arr,i);
     96         }
     97         char* before = "Size after appending:";
     98         printf("%30s %10d\n", before, arr->size);
     99         //printArr(arr);
    100         for(int i = 0 ; i < 1000000; ++i){
    101             arrPop(arr);
    102         }
    103         char* after = "Size after popping:";
    104         printf("%30s %10d\n", after, arr->size);
    105         //printArr(arr);
    106         free(arr->data);
    107         free(arr);
    108     }
    109 }