C言語ゼミ

C言語における動的配列は自作するかライブラリを使う

C言語には、静的配列と動的にメモリ確保を行う方法はありますが、動的配列ライブラリがありませんので、自作するかライブラリを使います。

なぜ動的配列という使用頻度の高いライブラリがないのかというと、ライブラリの内部でメモリ確保が必要なライブラリは、C言語のコアには入らないという方針があるような気がします。

動的配列の例としてプログラミング言語SPVMの内部実装で使用している動的配列の実装例を一つのサンプルとして書いておきます。

依存はないので、ヘッダとソースをコピペして使うことができます。

C言語における動的配列の実装例

解説はないですが、動的配列の作成、配列の要素の取得と設定、先頭や末尾から取り出しという基本的な関数だけですので、ヘッダを見れば、使い方はわかると思います。配列の要素は汎用ポインタ型 void*です。

spvm_list.h

動的配列のヘッダです。

#ifndef SPVM_LIST_H
#define SPVM_LIST_H

#include <stdint.h>
#include <stddef.h>

struct spvm_list;
typedef struct spvm_list SPVM_LIST;

struct spvm_list {
  void** values;
  int32_t length;
  int32_t capacity;
};

SPVM_LIST* SPVM_LIST_new(int32_t capacity);
void SPVM_LIST_free(SPVM_LIST* array);
void SPVM_LIST_maybe_extend(SPVM_LIST* array);

void SPVM_LIST_push(SPVM_LIST* array, void* value);
void* SPVM_LIST_fetch(SPVM_LIST* array, int32_t index);
void SPVM_LIST_store(SPVM_LIST* array, int32_t index, void* value);
void* SPVM_LIST_pop(SPVM_LIST* array);
void* SPVM_LIST_shift(SPVM_LIST* array);

#endif

spvm_list.c

動的配列の実装です。

#include <string.h>
#include <stdlib.h>
#include <assert.h>

#include "spvm_list.h"

SPVM_LIST* SPVM_LIST_new(int32_t capacity) {
  
  assert(capacity >= 0);
  
  SPVM_LIST* array = calloc(1, sizeof(SPVM_LIST));
  
  array->length = 0;
  
  if (capacity == 0) {
    array->capacity = 1;
  }
  else {
    array->capacity = capacity;
  }
  
  void** values = calloc(array->capacity, sizeof(void*));
  
  array->values = values;
  
  return array;
}

void SPVM_LIST_maybe_extend(SPVM_LIST* array) {
  
  assert(array);
  
  int32_t length = array->length;
  int32_t capacity = array->capacity;
  
  if (length >= capacity) {
    int32_t new_capacity = capacity * 2;
    
    void** new_values = calloc(new_capacity, sizeof(void*));
    memcpy(new_values, array->values, capacity * sizeof(void*));
    free(array->values);
    array->values = new_values;
    
    array->capacity = new_capacity;
  }
}

void SPVM_LIST_free(SPVM_LIST* array) {
  
  free(array->values);
  free(array);
}

void SPVM_LIST_push(SPVM_LIST* array, void* value) {
  
  SPVM_LIST_maybe_extend(array);
  
  int32_t length = array->length;
  
  *(void**)&array->values[length] = value;
  array->length++;
}

void* SPVM_LIST_fetch(SPVM_LIST* array, int32_t index) {
  assert(array);
  assert(index >= 0);
  assert(index < array->length);
  
  
  return *(void**)&array->values[index];
}

void SPVM_LIST_store(SPVM_LIST* array, int32_t index, void* value) {
  
  assert(array);
  assert(index >= 0);
  assert(index < array->length);
  
  *(void**)&array->values[index] = value;
}

void* SPVM_LIST_pop(SPVM_LIST* array) {
  
  assert(array->length >= 0);
  
  if (array->length == 0) {
    return NULL;
  }
  else {
    array->length--;
    return *(void**)&array->values[array->length];
  }
}

void* SPVM_LIST_shift(SPVM_LIST* array) {
  
  assert(array->length >= 0);
  
  if (array->length == 0) {
    return NULL;
  }
  else {
    void* return_value = array->values[0];
    for (int32_t i = 0; i < array->length - 1; i++) {
      array->values[i] = array->values[i + 1];
    }

    array->length--;
    return return_value;
  }
}