連想配列をCで実装する
戻る
当然本来はハッシュを使って実装するのが普通ですが、
ポインタの使い方の実例を説明するために私が大昔に書いたソースを公開します...なんてか（笑）
ちなみに全くオブジェクト指向的ではありませーん。
::::::::::::::
bbtnew.h
::::::::::::::
/*--------------------------------------------------------------------------*/
/* File ID : bbtnew.h */
/* Description: awkの連想配列に相当するものを実現する関数を記述している */
/* Author : Y.Kishi */
/*--------------------------------------------------------------------------*/
/* $Id: bbtnew.html,v 1.1 2009/06/22 16:12:05 kishi Exp kishi $ */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STRINGSIZE 2048
#define SPACE 0x20
#define MAXFIELDS 1024
char pb[MAXFIELDS][STRINGSIZE + 1]; /* 文字列分解用バッファ */
/* デ−タ部 */
struct dnode {
int value;
char *str;
};
/* キー部 */
struct binnode {
char *key;
struct dnode node;
struct binnode *l;
struct binnode *r;
struct binnode *p; /* Parent node address */
};
struct binnode *minnode(struct binnode ** y)
{
struct binnode *index;
index = *y;
if (index == NULL)
return NULL;
while (index->l != NULL)
index = index->l;
return index;
}
struct binnode *nextnode(struct binnode * y)
{
struct binnode *index;
index = y;
if (index == NULL)
return NULL;
if (index->r != NULL) {
index = index->r;
while (index->l != NULL)
index = index->l;
return index;
} else
while (index->p != NULL) {
if (index->p->l == index)
return index->p;
index = index->p;
}
return NULL;
}
struct binnode *maxnode(struct binnode ** y)
{
struct binnode *index;
index = *y;
if (index == NULL)
return NULL;
while (index->r != NULL)
index = index->r;
return index;
}
struct binnode *prevnode(struct binnode * y)
{
struct binnode *index;
index = y;
if (index == NULL)
return NULL;
if (index->l != NULL) {
index = index->l;
while (index->r != NULL)
index = index->r;
return index;
} else
while (index->p != NULL) {
if (index->p->r == index)
return index->p;
index = index->p;
}
return NULL;
}
struct binnode *rrotate(struct binnode * y)
{
/* r rotate. Demote y to r node of l of y */
struct binnode *x, *b;
x = y->l;
b = x->r;
x->r = y;
y->l = b;
x->p = y->p;
if (y->p != NULL) /* y was a child. Change pointer in parent */
if (y->p->l == y)
y->p->l = x;
else
y->p->r = x;
y->p = x;
if (b != NULL)
b->p = y;
return x;
}
struct binnode *lrotate(struct binnode * x)
{
struct binnode *y, *b;
y = x->r;
b = y->l;
y->l = x;
x->r = b;
y->p = x->p;
if (x->p != NULL) /* x was a child. Change pointer in parent */
if (x->p->l == x)
x->p->l = y;
else
x->p->r = y;
x->p = y;
if (b != NULL)
b->p = x;
return y;
}
struct binnode *splay(struct binnode * x)
{
struct binnode *index;
int xleftchild, pxleftchild;
index = x;
while (index->p != NULL) {
if (index->p->l == x)
xleftchild = 1;
else
xleftchild = 0;
if (index->p->p == NULL)
if (xleftchild == 1)
rrotate(index->p);
else
lrotate(index->p);
else {
if (index->p->p->l == x->p)
pxleftchild = 1;
else
pxleftchild = 0;
if (pxleftchild == 1 && xleftchild == 1) {
rrotate(index->p->p);
rrotate(index->p);
}
if (pxleftchild == 0 && xleftchild == 0) {
lrotate(index->p->p);
lrotate(index->p);
}
if (pxleftchild == 0 && xleftchild == 1) {
rrotate(index->p);
lrotate(index->p);
}
if (pxleftchild == 1 && xleftchild == 0) {
lrotate(index->p);
rrotate(index->p);
}
}
}
return index;
}
struct binnode *get_node(struct binnode ** tree, char *key)
{
struct binnode *index;
struct binnode *index2;
int scomp;
index = *tree;
while (index != NULL) {
scomp = strcmp(index->key, key);
if (scomp == 0) {
index2 = splay(index);
*tree = index2;
return index2;
}
if (scomp < 0)
index = index->r;
else
index = index->l;
}
return NULL;
}
struct binnode *insert_node(struct binnode ** tree, char *key)
{
struct binnode *index;
struct binnode *index2;
int len, scomp;
len = strlen(key) + 1;
index = *tree;
if (index == NULL) { /* new tree, just create node */
index = (struct binnode *) malloc(sizeof(struct binnode));
if (index == NULL) {
perror("Failure in malloc of insert_node");
exit(1);
}
index->l = NULL;
index->r = NULL;
index->p = NULL;
index->key = (char *) malloc(sizeof(char) * len);
if (index->key == NULL) {
perror("Failure in malloc of insert_node");
exit(2);
}
index->node.value = 0;
strcpy(index->key, key);
*tree = index;
return index;
}
while (index != NULL) {
scomp = strcmp(index->key, key);
if (scomp == 0) { /* key already in tree */
index2 = splay(index);
*tree = index2;
return index2;
}
if (scomp < 0) /* index-> key < key , go r */
if (index->r == NULL) { /* time to insert */
index->r = (struct binnode *) malloc(sizeof(struct binnode));
if (index->r == NULL) {
perror("Failure in malloc of insert_node");
exit(2);
}
index->r->p = index;
index = index->r;
index->l = NULL;
index->r = NULL;
index->key = (char *) malloc(sizeof(char) * len);
if (index->key == NULL) {
perror("Failure in malloc of insert_node");
exit(2);
}
strcpy(index->key, key);
index->node.value = 0;
index2 = splay(index);
*tree = index2;
return index2;
} else
index = index->r;
else if (index->l == NULL) { /* time to insert */
index->l = (struct binnode *) malloc(sizeof(struct binnode));
if (index->l == NULL) {
perror("Failure in malloc of insert_node");
exit(2);
}
index->l->p = index;
index = index->l;
index->l = NULL;
index->r = NULL;
index->key = (char *) malloc(sizeof(char) * len);
if (index->key == NULL) {
perror("Failure in malloc of insert_node");
exit(2);
}
strcpy(index->key, key);
index->node.value = 0;
index2 = splay(index);
*tree = index2;
return index2;
} else
index = index->l;
}
perror("Unable to find insert location in insert_node");
exit(3);
return NULL;
}
int parsestring(char *in, int tok)
{
int count;
char *p1, *p2;
count = 0;
p1 = in;
p2 = strchr(p1, tok);
while (p2 != NULL) {
strncpy(pb[count], p1, p2 - p1);
pb[count++][p2 - p1] = 0;
p1 = p2 + 1;
p2 = strchr(p1, tok);
}
strcpy(pb[count++], p1);
return count;
}
int
splitstring(char *in, char *sep)
{
int count = 0, pos;
int check_range = strlen(sep);
char *p, *from, *to;
p = in;
pos = 0;
from = in;
while (*p != 0) {
if (!strncmp(p++, sep, check_range)) {
to = p - 1;
memset(pb[count], 0x00, sizeof pb[count]);
memcpy(pb[count++], from, to - from);
pos += check_range;
from = to + check_range;
}
pos++;
}
memset(pb[count], 0x00, sizeof pb[count]);
memcpy(pb[count++], from, p - from);
return count;
}
::::::::::::::
ez.h
::::::::::::::
#include "bbtnew.h"
/* $Id: bbtnew.html,v 1.1 2009/06/22 16:12:05 kishi Exp kishi $ */
/*--------------------------------------------------------*/
/* File ID : ez.h */
/* Description: bbtnew.hを使用するという前提で利用します */
/* Author : Y.Kishi */
/*--------------------------------------------------------*/
/***********/
/* Integer */
/***********/
void
set_value(struct binnode ** ARR, char *keystr, int value)
{
struct binnode *index;
index = insert_node(ARR, keystr);
index->node.value = value;
}
void
add_value(struct binnode ** ARR, char *keystr, int value)
{
struct binnode *index;
index = insert_node(ARR, keystr);
index->node.value += value;
}
int
get_value(struct binnode ** ARR, char *keystr)
{
struct binnode *index;
index = get_node(ARR, keystr);
return (index != NULL) ? index->node.value : 0;
}
/***********/
/* Strings */
/***********/
int
set_str(struct binnode ** ARR, char *keystr, char *datastr)
{ /* 同一キ−の場合，最後にセットされたものを有効
* にする */
struct binnode *index;
char *tmp, *saved_ptr;
index = get_node(ARR, keystr);
if (index != NULL) { /* 既に同一キ−がある */
saved_ptr = index->node.str;
tmp = realloc(index->node.str, strlen(datastr) + 1); /* メモリ再割当て */
if (tmp != NULL) {
index->node.str = tmp;
strcpy(index->node.str, datastr);
return 0;
} else {
index->node.str = saved_ptr;
fprintf(stderr, "memeory reallocation error in set_str!!\n");
return (-1);
}
} else { /* 新規 */
index = insert_node(ARR, keystr);
index->node.str = (char *) malloc(strlen(datastr) + 1);
if (index->node.str == NULL)
fprintf(stderr, "malloc error!!\n"), exit(11);
strcpy(index->node.str, datastr);
return 0;
}
}
char *get_str(struct binnode ** ARR, char *keystr)
{
struct binnode *index;
index = get_node(ARR, keystr);
if (index != NULL) {
/* 見つかった時は文字列に対するポインタを返す */
return (char *)index->node.str;
} else {
/* 見つからない時は NULL を返す */
return (char *)NULL;
}
}
/*********/
/* Float */
/*********/
void
set_fvalue(struct binnode ** ARR, char *keystr, float fvalue)
{
struct binnode *index;
index = get_node(ARR, keystr);
if (index == NULL) {
index = insert_node(ARR, keystr);
index->node.str = (char *) malloc(sizeof(float));
if (index->node.str == NULL)
fprintf(stderr, "malloc error!!\n"), exit(12);
*(float *) index->node.str = 0.0;
}
index = insert_node(ARR, keystr);
*(float *) index->node.str = fvalue;
}
void
add_fvalue(struct binnode ** ARR, char *keystr, float fvalue)
{
struct binnode *index;
index = get_node(ARR, keystr);
if (index == NULL) {
index = insert_node(ARR, keystr);
index->node.str = (char *) malloc(sizeof(float));
if (index->node.str == NULL)
fprintf(stderr, "malloc error!!\n"), exit(13);
*(float *) index->node.str = 0.0;
}
index = insert_node(ARR, keystr);
*(float *) index->node.str += fvalue;
}
float
get_fvalue(struct binnode ** ARR, char *keystr)
{
struct binnode *index;
index = get_node(ARR, keystr);
return (index != NULL) ? *(float *) index->node.str : 0.0;
}
::::::::::::::
test1.c
::::::::::::::
#include "bbtnew.h"
/* $Id: bbtnew.html,v 1.1 2009/06/22 16:12:05 kishi Exp kishi $ */
int
main (void)
{
struct binnode **COMB;
struct binnode *index;
COMB = (struct binnode **) malloc (sizeof (struct binnode *)), *COMB = NULL;
index = insert_node (COMB, "あいうえお");
index->node.value = 1000;
index = insert_node (COMB, "まみむめも");
index->node.value = 500;
index = insert_node (COMB, "かきくけこ");
index->node.value = 40;
/* 全件表示 */
index = minnode (COMB);
while (index != NULL) {
printf ("%s\t%d\n", index->key, index->node.value);
index = nextnode (index);
}
return 0;
}
::::::::::::::
test2.c
::::::::::::::
#include "ez.h"
/* $Id: bbtnew.html,v 1.1 2009/06/22 16:12:05 kishi Exp kishi $ */
int
main (void)
{
struct binnode **COMB;
struct binnode *index;
COMB = (struct binnode **) malloc (sizeof (struct binnode *)), *COMB = NULL;
set_fvalue (COMB, "あいうえお", 3.5);
set_fvalue (COMB, "まみむめも", 200.13);
set_fvalue (COMB, "かきくけこ", 40.6);
/* 全件表示 */
index = minnode (COMB);
while (index != NULL) {
printf ("%s\t%3.2f\n", index->key, get_fvalue(COMB, index->key) );
index = nextnode (index);
}
return 0;
}
■実行結果
$ make test1; ./test1
gcc test1.c -o test1
あいうえお 1000
かきくけこ 40
まみむめも 500
$ make test2; ./test2
gcc test2.c -o test2
あいうえお 3.50
かきくけこ 40.60
まみむめも 200.13
戻る
