C言語ゼミ

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

C言語には、連想配列ライブラリがありませんので、自作するかライブラリを使います。

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

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

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

C言語における連想配列の実装例

解説はないですが、連想配列の作成、連想配列の値の取得と設定という基本的な関数だけですので、ヘッダを見れば、使い方はわかると思います。連想配列の値は汎用ポインタ型 void*です。要素の削除と存在の確認の関数は、残念ながら、実装されていません。内部で使用しているハッシュ関数は、ごく簡単なもので、セキュリティ強度はないです。

spvm_hash.h

連想配列のヘッダです。

#ifndef SPVM_HASH_H
#define SPVM_HASH_H

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

struct spvm_hash;
typedef struct spvm_hash SPVM_HASH;

struct spvm_hash_entry;
typedef struct spvm_hash_entry SPVM_HASH_ENTRY;

// Hash table
struct spvm_hash {
  int32_t* table;
  char* key_buffer;
  SPVM_HASH_ENTRY* entries;
  int32_t table_capacity;
  int32_t entries_capacity;
  int32_t entries_length;
  int32_t key_buffer_capacity;
  int32_t key_buffer_length;
};

// Hash entry
struct spvm_hash_entry {
  void* value;
  int32_t next_index;
  int32_t key_index;
};

SPVM_HASH* SPVM_HASH_new(int32_t capacity);

void SPVM_HASH_insert(SPVM_HASH* hash, const char* key, int32_t length, void* value);
void* SPVM_HASH_fetch(SPVM_HASH* hash, const char* key, int32_t length);

void SPVM_HASH_free(SPVM_HASH* hash);

int32_t SPVM_HASH_new_hash_entry(SPVM_HASH* hash, const char* key, int32_t length, void* value);
void SPVM_HASH_rehash(SPVM_HASH* hash, int32_t new_table_capacity);
void SPVM_HASH_insert_norehash(SPVM_HASH* hash, const char* key, int32_t length, void* value);
int32_t SPVM_HASH_calc_hash_value(const char* str, int32_t len);
void SPVM_HASH_maybe_extend_entries(SPVM_HASH* hash);

#endif

spvm_hash.c

連想配列の実装です。

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

#include "spvm_hash.h"

SPVM_HASH* SPVM_HASH_new(int32_t table_capacity) {
  
  assert(table_capacity >= 0);

  // Create hash
  SPVM_HASH* hash = calloc(1, sizeof(SPVM_HASH));

  // Default table capacity
  if (table_capacity == 0) {
    hash->table_capacity = 1;
  }
  else {
    hash->table_capacity = table_capacity;
  }
  
  // Initialize table
  hash->table = calloc(hash->table_capacity, sizeof(int32_t));
  memset(hash->table, -1, hash->table_capacity * sizeof(int32_t));
  
  // Initialize entries
  hash->entries_capacity = 1;
  hash->entries =  calloc(hash->entries_capacity, sizeof(SPVM_HASH_ENTRY));
  hash->entries_length = 0;
  
  // Initialize key buffer
  hash->key_buffer_capacity = 1;
  hash->key_buffer = calloc(1, hash->key_buffer_capacity);
  hash->key_buffer_length = 0;
  
  return hash;
}

void SPVM_HASH_insert(SPVM_HASH* hash, const char* key, int32_t length, void* value) {
  
  assert(hash);
  assert(key);
  assert(length >= 0);
  
  // Rehash
  if (hash->entries_length > hash->table_capacity * 0.75) {
    int32_t new_table_capacity = (hash->table_capacity * 2) + 1;
    
    SPVM_HASH_rehash(hash, new_table_capacity);
  }
  
  SPVM_HASH_insert_norehash(hash, key, length, value);
}

void* SPVM_HASH_fetch(SPVM_HASH* hash, const char* key, int32_t length) {
  
  assert(hash);
  assert(length >= 0);
  
  int32_t hash_value = SPVM_HASH_calc_hash_value(key, length);
  int32_t table_index = hash_value % hash->table_capacity;
  
  int32_t entry_index = -1;
  if (hash->table[table_index] != -1) {
    entry_index = hash->table[table_index];
  }
  while (1) {
    assert(entry_index >= -1);
    if (entry_index != -1) {
      int32_t match = 0;
      int32_t key_length;
      memcpy(&key_length, &hash->key_buffer[hash->entries[entry_index].key_index], sizeof(int32_t));
      if (length == 0 && key_length == 0) {
        match = 1;
      }
      else if (key_length == length && memcmp(key, &hash->key_buffer[hash->entries[entry_index].key_index + sizeof(int32_t)], length) == 0) {
        match = 1;
      }
      
      if (match) {
        return hash->entries[entry_index].value;
      }
      else {
        if (hash->entries[entry_index].next_index == -1) {
          entry_index = -1;
        }
        else {
          entry_index = hash->entries[entry_index].next_index;
        }
      }
    }
    else {
      return NULL;
    }
  }
}

void SPVM_HASH_free(SPVM_HASH* hash) {
  
  assert(hash);
  
  free(hash->table);
  free(hash->entries);
  free(hash->key_buffer);
  free(hash);
}

void SPVM_HASH_maybe_extend_entries(SPVM_HASH* hash) {
  
  assert(hash);
  
  int32_t entries_length = hash->entries_length;
  
  assert(entries_length >= 0);
  
  int32_t entries_capacity = hash->entries_capacity;
  
  if (entries_length >= entries_capacity) {
    int32_t new_entries_capacity = entries_capacity * 2;
    
    SPVM_HASH_ENTRY* new_entries = calloc(new_entries_capacity, sizeof(SPVM_HASH_ENTRY));
    memcpy(new_entries, hash->entries, entries_capacity * sizeof(SPVM_HASH_ENTRY));
    free(hash->entries);
    hash->entries = new_entries;
    
    hash->entries_capacity = new_entries_capacity;
  }
}

void SPVM_HASH_maybe_extend_key_buffer(SPVM_HASH* hash, int32_t length) {
  
  assert(hash);
  
  int32_t key_buffer_length = hash->key_buffer_length;
  
  assert(key_buffer_length >= 0);
  
  int32_t key_buffer_capacity = hash->key_buffer_capacity;
  
  if (key_buffer_length + length + (int32_t)sizeof(int32_t) >= key_buffer_capacity) {
    int32_t new_key_buffer_capacity = (key_buffer_length + length + sizeof(int32_t)) * 2;
    
    char* new_key_buffer = calloc(1, new_key_buffer_capacity);
    memcpy(new_key_buffer, hash->key_buffer, key_buffer_capacity);
    free(hash->key_buffer);
    hash->key_buffer = new_key_buffer;

    hash->key_buffer_capacity = new_key_buffer_capacity;
  }
}

int32_t SPVM_HASH_new_hash_entry(SPVM_HASH* hash, const char* key, int32_t key_length, void* value) {
  
  assert(hash);
  assert(key);
  
  int32_t index = hash->entries_length;
  
  SPVM_HASH_maybe_extend_entries(hash);
  
  SPVM_HASH_maybe_extend_key_buffer(hash, key_length);
  
  hash->entries[index].key_index = hash->key_buffer_length;
  
  // Copy key length
  memcpy(&hash->key_buffer[hash->key_buffer_length], &key_length, sizeof(int32_t));
  
  // Copy key
  memcpy(&hash->key_buffer[hash->key_buffer_length + sizeof(int32_t)], key, key_length);
  
  hash->key_buffer_length += sizeof(int32_t) + key_length;
  
  hash->entries[index].value = value;
  hash->entries[index].next_index = -1;
  
  hash->entries_length++;
  
  return index;
}

void SPVM_HASH_rehash(SPVM_HASH* hash, int32_t new_table_capacity) {
  
  assert(hash);
  assert(new_table_capacity > 0);
  
  // Create new hash
  SPVM_HASH* new_hash = SPVM_HASH_new(new_table_capacity);
  
  // Rehash
  {
    int32_t i;
    for (i = 0; i < hash->entries_length; i++) {
      int32_t key_length;
      memcpy(&key_length, &hash->key_buffer[hash->entries[i].key_index], sizeof(int32_t));
      const char* key = &hash->key_buffer[hash->entries[i].key_index + sizeof(int32_t)];
      
      void* value = hash->entries[i].value;
      
      SPVM_HASH_insert_norehash(new_hash, key, key_length, value);
    }
  }
  
  // Replace hash fields
  free(hash->table);
  free(hash->entries);
  free(hash->key_buffer);
  hash->entries_length = new_hash->entries_length;
  hash->table_capacity = new_hash->table_capacity;
  hash->entries_capacity = new_hash->entries_capacity;
  hash->table = new_hash->table;
  hash->entries = new_hash->entries;
  
  hash->key_buffer_capacity = new_hash->key_buffer_capacity;
  hash->key_buffer_length = new_hash->key_buffer_length;
  hash->key_buffer = new_hash->key_buffer;
  
  free(new_hash);
}

void SPVM_HASH_insert_norehash(SPVM_HASH* hash, const char* key, int32_t length, void* value) {
  
  assert(hash);
  assert(key);
  assert(length >= 0);
  
  int32_t hash_value = SPVM_HASH_calc_hash_value(key, length);
  int32_t table_index = hash_value % hash->table_capacity;
  
  assert(hash->table[table_index] >= -1);
  
  if (hash->table[table_index] != -1) {
    
    int32_t entry_index = hash->table[table_index];
    while (1) {
      int32_t match = 0;
      int32_t key_length;
      memcpy(&key_length, &hash->key_buffer[hash->entries[entry_index].key_index], sizeof(int32_t));
      if (key_length == 0 && length == 0) {
        match = 1;
      }
      else if (key_length == length && memcmp(key, &hash->key_buffer[hash->entries[entry_index].key_index + sizeof(int32_t)], length) == 0) {
        match = 1;
      }
      
      if (match) {
        hash->entries[entry_index].value = value;
        break;
      }
      else {
        if (hash->entries[entry_index].next_index != -1) {
          entry_index = hash->entries[entry_index].next_index;
        }
        else {
          int32_t new_entry_index = SPVM_HASH_new_hash_entry(hash, key, length, value);
          hash->entries[entry_index].next_index = new_entry_index;
          break;
        }
      }
    }
  }
  else {
    int32_t new_entry_index = SPVM_HASH_new_hash_entry(hash, key, length, value);
    hash->table[table_index] = new_entry_index;
  }
}

int32_t SPVM_HASH_calc_hash_value(const char* str, int32_t len) {
  
  assert(len >= 0);
  
  const char* str_tmp = str;
  int32_t hash = 5381;
  while (len--) {
    hash = ((hash << 5) + hash) + (uint8_t) *str_tmp++;
  }
  
  if (hash < 0) {
    hash = ~hash;
  }
  
  return hash;
}