summaryrefslogtreecommitdiff
path: root/src/common/db.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/db.c')
-rw-r--r--src/common/db.c1002
1 files changed, 501 insertions, 501 deletions
diff --git a/src/common/db.c b/src/common/db.c
index 1f00ffd6b..58f0ea4f7 100644
--- a/src/common/db.c
+++ b/src/common/db.c
@@ -1,501 +1,501 @@
-// $Id: db.c,v 1.2 2004/09/23 14:43:06 MouseJstr Exp $
-// #define MALLOC_DBN
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include "db.h"
-#include "mmo.h"
-#include "utils.h"
-
-#ifdef MEMWATCH
-#include "memwatch.h"
-#endif
-
-#define ROOT_SIZE 4096
-#ifdef MALLOC_DBN
-static struct dbn *dbn_root[512], *dbn_free;
-static int dbn_root_rest=0,dbn_root_num=0;
-
-static void * malloc_dbn(void)
-{
- struct dbn* ret;
-
- if(dbn_free==NULL){
- if(dbn_root_rest<=0){
- CREATE(dbn_root[dbn_root_num], struct dbn, ROOT_SIZE);
-
- dbn_root_rest=ROOT_SIZE;
- dbn_root_num++;
- }
- return &(dbn_root[dbn_root_num-1][--dbn_root_rest]);
- }
- ret=dbn_free;
- dbn_free = dbn_free->parent;
- return ret;
-}
-
-static void free_dbn(struct dbn* add_dbn)
-{
- add_dbn->parent = dbn_free;
- dbn_free = add_dbn;
-}
-#endif
-
-static int strdb_cmp(struct dbt* table,void* a,void* b)
-{
- if(table->maxlen)
- return strncmp(a,b,table->maxlen);
- return strcmp(a,b);
-}
-
-static unsigned int strdb_hash(struct dbt* table,void* a)
-{
- int i;
- unsigned int h;
- unsigned char *p=a;
-
- i=table->maxlen;
- if(i==0) i=0x7fffffff;
- for(h=0;*p && --i>=0;){
- h=(h*33 + *p++) ^ (h>>24);
- }
- return h;
-}
-
-struct dbt* strdb_init(int maxlen)
-{
- int i;
- struct dbt* table;
-
- CREATE(table, struct dbt, 1);
-
- table->cmp=strdb_cmp;
- table->hash=strdb_hash;
- table->maxlen=maxlen;
- for(i=0;i<HASH_SIZE;i++)
- table->ht[i]=NULL;
- return table;
-}
-
-static int numdb_cmp(struct dbt* table,void* a,void* b)
-{
- int ia,ib;
-
- ia=(int)a;
- ib=(int)b;
-
- if((ia^ib) & 0x80000000)
- return ia<0 ? -1 : 1;
-
- return ia-ib;
-}
-
-static unsigned int numdb_hash(struct dbt* table,void* a)
-{
- return (unsigned int)a;
-}
-
-struct dbt* numdb_init(void)
-{
- int i;
- struct dbt* table;
-
- CREATE(table, struct dbt, 1);
-
- table->cmp=numdb_cmp;
- table->hash=numdb_hash;
- table->maxlen=sizeof(int);
- for(i=0;i<HASH_SIZE;i++)
- table->ht[i]=NULL;
- return table;
-}
-
-void* db_search(struct dbt *table,void* key)
-{
- struct dbn *p;
-
- for(p=table->ht[table->hash(table,key) % HASH_SIZE];p;){
- int c=table->cmp(table,key,p->key);
- if(c==0)
- return p->data;
- if(c<0)
- p=p->left;
- else
- p=p->right;
- }
- return NULL;
-}
-
-void * db_search2(struct dbt *table, const char *key)
-{
- int i,sp;
- struct dbn *p,*pn,*stack[64];
- int slen = strlen(key);
-
- for(i=0;i<HASH_SIZE;i++){
- if((p=table->ht[i])==NULL)
- continue;
- sp=0;
- while(1){
- if (strnicmp(key, p->key, slen) == 0)
- return p->data;
- if((pn=p->left)!=NULL){
- if(p->right){
- stack[sp++]=p->right;
- }
- p=pn;
- } else {
- if(p->right){
- p=p->right;
- } else {
- if(sp==0)
- break;
- p=stack[--sp];
- }
- }
- }
- }
- return 0;
-}
-
-static void db_rotate_left(struct dbn *p,struct dbn **root)
-{
- struct dbn * y = p->right;
- p->right = y->left;
- if (y->left !=0)
- y->left->parent = p;
- y->parent = p->parent;
-
- if (p == *root)
- *root = y;
- else if (p == p->parent->left)
- p->parent->left = y;
- else
- p->parent->right = y;
- y->left = p;
- p->parent = y;
-}
-
-static void db_rotate_right(struct dbn *p,struct dbn **root)
-{
- struct dbn * y = p->left;
- p->left = y->right;
- if (y->right != 0)
- y->right->parent = p;
- y->parent = p->parent;
-
- if (p == *root)
- *root = y;
- else if (p == p->parent->right)
- p->parent->right = y;
- else
- p->parent->left = y;
- y->right = p;
- p->parent = y;
-}
-
-static void db_rebalance(struct dbn *p,struct dbn **root)
-{
- p->color = RED;
- while(p!=*root && p->parent->color==RED){ // rootは必ず黒で親は赤いので親の親は必ず存在する
- if (p->parent == p->parent->parent->left) {
- struct dbn *y = p->parent->parent->right;
- if (y && y->color == RED) {
- p->parent->color = BLACK;
- y->color = BLACK;
- p->parent->parent->color = RED;
- p = p->parent->parent;
- } else {
- if (p == p->parent->right) {
- p = p->parent;
- db_rotate_left(p, root);
- }
- p->parent->color = BLACK;
- p->parent->parent->color = RED;
- db_rotate_right(p->parent->parent, root);
- }
- } else {
- struct dbn* y = p->parent->parent->left;
- if (y && y->color == RED) {
- p->parent->color = BLACK;
- y->color = BLACK;
- p->parent->parent->color = RED;
- p = p->parent->parent;
- } else {
- if (p == p->parent->left) {
- p = p->parent;
- db_rotate_right(p, root);
- }
- p->parent->color = BLACK;
- p->parent->parent->color = RED;
- db_rotate_left(p->parent->parent, root);
- }
- }
- }
- (*root)->color=BLACK;
-}
-
-static void db_rebalance_erase(struct dbn *z,struct dbn **root)
-{
- struct dbn *y = z, *x = NULL, *x_parent = NULL;
-
- if (y->left == NULL)
- x = y->right;
- else if (y->right == NULL)
- x = y->left;
- else {
- y = y->right;
- while (y->left != NULL)
- y = y->left;
- x = y->right;
- }
- if (y != z) { // 左右が両方埋まっていた時 yをzの位置に持ってきてzを浮かせる
- z->left->parent = y;
- y->left = z->left;
- if (y != z->right) {
- x_parent = y->parent;
- if (x) x->parent = y->parent;
- y->parent->left = x;
- y->right = z->right;
- z->right->parent = y;
- } else
- x_parent = y;
- if (*root == z)
- *root = y;
- else if (z->parent->left == z)
- z->parent->left = y;
- else
- z->parent->right = y;
- y->parent = z->parent;
- { int tmp=y->color; y->color=z->color; z->color=tmp; }
- y = z;
- } else { // どちらか空いていた場合 xをzの位置に持ってきてzを浮かせる
- x_parent = y->parent;
- if (x) x->parent = y->parent;
- if (*root == z)
- *root = x;
- else if (z->parent->left == z)
- z->parent->left = x;
- else
- z->parent->right = x;
- }
- // ここまで色の移動の除いて通常の2分木と同じ
- if (y->color != RED) { // 赤が消える分には影響無し
- while (x != *root && (x == NULL || x->color == BLACK))
- if (x == x_parent->left) {
- struct dbn* w = x_parent->right;
- if (w->color == RED) {
- w->color = BLACK;
- x_parent->color = RED;
- db_rotate_left(x_parent, root);
- w = x_parent->right;
- }
- if ((w->left == NULL ||
- w->left->color == BLACK) &&
- (w->right == NULL ||
- w->right->color == BLACK)) {
- w->color = RED;
- x = x_parent;
- x_parent = x_parent->parent;
- } else {
- if (w->right == NULL ||
- w->right->color == BLACK) {
- if (w->left) w->left->color = BLACK;
- w->color = RED;
- db_rotate_right(w, root);
- w = x_parent->right;
- }
- w->color = x_parent->color;
- x_parent->color = BLACK;
- if (w->right) w->right->color = BLACK;
- db_rotate_left(x_parent, root);
- break;
- }
- } else { // same as above, with right <-> left.
- struct dbn* w = x_parent->left;
- if (w->color == RED) {
- w->color = BLACK;
- x_parent->color = RED;
- db_rotate_right(x_parent, root);
- w = x_parent->left;
- }
- if ((w->right == NULL ||
- w->right->color == BLACK) &&
- (w->left == NULL ||
- w->left->color == BLACK)) {
- w->color = RED;
- x = x_parent;
- x_parent = x_parent->parent;
- } else {
- if (w->left == NULL ||
- w->left->color == BLACK) {
- if (w->right) w->right->color = BLACK;
- w->color = RED;
- db_rotate_left(w, root);
- w = x_parent->left;
- }
- w->color = x_parent->color;
- x_parent->color = BLACK;
- if (w->left) w->left->color = BLACK;
- db_rotate_right(x_parent, root);
- break;
- }
- }
- if (x) x->color = BLACK;
- }
-}
-
-struct dbn* db_insert(struct dbt *table,void* key,void* data)
-{
- struct dbn *p,*priv;
- int c,hash;
-
- hash = table->hash(table,key) % HASH_SIZE;
- for(c=0,priv=NULL ,p = table->ht[hash];p;){
- c=table->cmp(table,key,p->key);
- if(c==0){ // replace
- if (table->release)
- table->release(p, 3);
- p->data=data;
- p->key=key;
- return p;
- }
- priv=p;
- if(c<0){
- p=p->left;
- } else {
- p=p->right;
- }
- }
-#ifdef MALLOC_DBN
- p=malloc_dbn();
-#else
- CREATE(p, struct dbn, 1);
-#endif
- if(p==NULL){
- printf("out of memory : db_insert\n");
- return NULL;
- }
- p->parent= NULL;
- p->left = NULL;
- p->right = NULL;
- p->key = key;
- p->data = data;
- p->color = RED;
- if(c==0){ // hash entry is empty
- table->ht[hash] = p;
- p->color = BLACK;
- } else {
- if(c<0){ // left node
- priv->left = p;
- p->parent=priv;
- } else { // right node
- priv->right = p;
- p->parent=priv;
- }
- if(priv->color==RED){ // must rebalance
- db_rebalance(p,&table->ht[hash]);
- }
- }
- return p;
-}
-
-void* db_erase(struct dbt *table,void* key)
-{
- void *data;
- struct dbn *p;
- int c,hash;
-
- hash = table->hash(table,key) % HASH_SIZE;
- for(c=0,p = table->ht[hash];p;){
- c=table->cmp(table,key,p->key);
- if(c==0)
- break;
- if(c<0)
- p=p->left;
- else
- p=p->right;
- }
- if(!p)
- return NULL;
- data=p->data;
- db_rebalance_erase(p,&table->ht[hash]);
-#ifdef MALLOC_DBN
- free_dbn(p);
-#else
- free(p);
-#endif
- return data;
-}
-
-void db_foreach(struct dbt *table,int (*func)(void*,void*,va_list),...)
-{
- int i,sp;
- // red-black treeなので64個stackがあれば2^32個ノードまで大丈夫
- struct dbn *p,*pn,*stack[64];
- va_list ap;
-
- va_start(ap,func);
- for(i=0;i<HASH_SIZE;i++){
- if((p=table->ht[i])==NULL)
- continue;
- sp=0;
- while(1){
- func(p->key,p->data,ap);
- if((pn=p->left)!=NULL){
- if(p->right){
- stack[sp++]=p->right;
- }
- p=pn;
- } else {
- if(p->right){
- p=p->right;
- } else {
- if(sp==0)
- break;
- p=stack[--sp];
- }
- }
- }
- }
- va_end(ap);
-}
-
-void db_final(struct dbt *table,int (*func)(void*,void*,va_list),...)
-{
- int i,sp;
- struct dbn *p,*pn,*stack[64];
- va_list ap;
-
- va_start(ap,func);
- for(i=0;i<HASH_SIZE;i++){
- if((p=table->ht[i])==NULL)
- continue;
- sp=0;
- while(1){
- if(func)
- func(p->key,p->data,ap);
- if((pn=p->left)!=NULL){
- if(p->right){
- stack[sp++]=p->right;
- }
- } else {
- if(p->right){
- pn=p->right;
- } else {
- if(sp==0)
- break;
- pn=stack[--sp];
- }
- }
-#ifdef MALLOC_DBN
- free_dbn(p);
-#else
- free(p);
-#endif
- p=pn;
- }
- }
- free(table);
- va_end(ap);
-}
+// $Id: db.c,v 1.2 2004/09/23 14:43:06 MouseJstr Exp $
+// #define MALLOC_DBN
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "db.h"
+#include "mmo.h"
+#include "utils.h"
+
+#ifdef MEMWATCH
+#include "memwatch.h"
+#endif
+
+#define ROOT_SIZE 4096
+#ifdef MALLOC_DBN
+static struct dbn *dbn_root[512], *dbn_free;
+static int dbn_root_rest=0,dbn_root_num=0;
+
+static void * malloc_dbn(void)
+{
+ struct dbn* ret;
+
+ if(dbn_free==NULL){
+ if(dbn_root_rest<=0){
+ CREATE(dbn_root[dbn_root_num], struct dbn, ROOT_SIZE);
+
+ dbn_root_rest=ROOT_SIZE;
+ dbn_root_num++;
+ }
+ return &(dbn_root[dbn_root_num-1][--dbn_root_rest]);
+ }
+ ret=dbn_free;
+ dbn_free = dbn_free->parent;
+ return ret;
+}
+
+static void free_dbn(struct dbn* add_dbn)
+{
+ add_dbn->parent = dbn_free;
+ dbn_free = add_dbn;
+}
+#endif
+
+static int strdb_cmp(struct dbt* table,void* a,void* b)
+{
+ if(table->maxlen)
+ return strncmp(a,b,table->maxlen);
+ return strcmp(a,b);
+}
+
+static unsigned int strdb_hash(struct dbt* table,void* a)
+{
+ int i;
+ unsigned int h;
+ unsigned char *p=a;
+
+ i=table->maxlen;
+ if(i==0) i=0x7fffffff;
+ for(h=0;*p && --i>=0;){
+ h=(h*33 + *p++) ^ (h>>24);
+ }
+ return h;
+}
+
+struct dbt* strdb_init(int maxlen)
+{
+ int i;
+ struct dbt* table;
+
+ CREATE(table, struct dbt, 1);
+
+ table->cmp=strdb_cmp;
+ table->hash=strdb_hash;
+ table->maxlen=maxlen;
+ for(i=0;i<HASH_SIZE;i++)
+ table->ht[i]=NULL;
+ return table;
+}
+
+static int numdb_cmp(struct dbt* table,void* a,void* b)
+{
+ int ia,ib;
+
+ ia=(int)a;
+ ib=(int)b;
+
+ if((ia^ib) & 0x80000000)
+ return ia<0 ? -1 : 1;
+
+ return ia-ib;
+}
+
+static unsigned int numdb_hash(struct dbt* table,void* a)
+{
+ return (unsigned int)a;
+}
+
+struct dbt* numdb_init(void)
+{
+ int i;
+ struct dbt* table;
+
+ CREATE(table, struct dbt, 1);
+
+ table->cmp=numdb_cmp;
+ table->hash=numdb_hash;
+ table->maxlen=sizeof(int);
+ for(i=0;i<HASH_SIZE;i++)
+ table->ht[i]=NULL;
+ return table;
+}
+
+void* db_search(struct dbt *table,void* key)
+{
+ struct dbn *p;
+
+ for(p=table->ht[table->hash(table,key) % HASH_SIZE];p;){
+ int c=table->cmp(table,key,p->key);
+ if(c==0)
+ return p->data;
+ if(c<0)
+ p=p->left;
+ else
+ p=p->right;
+ }
+ return NULL;
+}
+
+void * db_search2(struct dbt *table, const char *key)
+{
+ int i,sp;
+ struct dbn *p,*pn,*stack[64];
+ int slen = strlen(key);
+
+ for(i=0;i<HASH_SIZE;i++){
+ if((p=table->ht[i])==NULL)
+ continue;
+ sp=0;
+ while(1){
+ if (strnicmp(key, p->key, slen) == 0)
+ return p->data;
+ if((pn=p->left)!=NULL){
+ if(p->right){
+ stack[sp++]=p->right;
+ }
+ p=pn;
+ } else {
+ if(p->right){
+ p=p->right;
+ } else {
+ if(sp==0)
+ break;
+ p=stack[--sp];
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+static void db_rotate_left(struct dbn *p,struct dbn **root)
+{
+ struct dbn * y = p->right;
+ p->right = y->left;
+ if (y->left !=0)
+ y->left->parent = p;
+ y->parent = p->parent;
+
+ if (p == *root)
+ *root = y;
+ else if (p == p->parent->left)
+ p->parent->left = y;
+ else
+ p->parent->right = y;
+ y->left = p;
+ p->parent = y;
+}
+
+static void db_rotate_right(struct dbn *p,struct dbn **root)
+{
+ struct dbn * y = p->left;
+ p->left = y->right;
+ if (y->right != 0)
+ y->right->parent = p;
+ y->parent = p->parent;
+
+ if (p == *root)
+ *root = y;
+ else if (p == p->parent->right)
+ p->parent->right = y;
+ else
+ p->parent->left = y;
+ y->right = p;
+ p->parent = y;
+}
+
+static void db_rebalance(struct dbn *p,struct dbn **root)
+{
+ p->color = RED;
+ while(p!=*root && p->parent->color==RED){ // rootは必ず黒で親は赤いので親の親は必ず存在する
+ if (p->parent == p->parent->parent->left) {
+ struct dbn *y = p->parent->parent->right;
+ if (y && y->color == RED) {
+ p->parent->color = BLACK;
+ y->color = BLACK;
+ p->parent->parent->color = RED;
+ p = p->parent->parent;
+ } else {
+ if (p == p->parent->right) {
+ p = p->parent;
+ db_rotate_left(p, root);
+ }
+ p->parent->color = BLACK;
+ p->parent->parent->color = RED;
+ db_rotate_right(p->parent->parent, root);
+ }
+ } else {
+ struct dbn* y = p->parent->parent->left;
+ if (y && y->color == RED) {
+ p->parent->color = BLACK;
+ y->color = BLACK;
+ p->parent->parent->color = RED;
+ p = p->parent->parent;
+ } else {
+ if (p == p->parent->left) {
+ p = p->parent;
+ db_rotate_right(p, root);
+ }
+ p->parent->color = BLACK;
+ p->parent->parent->color = RED;
+ db_rotate_left(p->parent->parent, root);
+ }
+ }
+ }
+ (*root)->color=BLACK;
+}
+
+static void db_rebalance_erase(struct dbn *z,struct dbn **root)
+{
+ struct dbn *y = z, *x = NULL, *x_parent = NULL;
+
+ if (y->left == NULL)
+ x = y->right;
+ else if (y->right == NULL)
+ x = y->left;
+ else {
+ y = y->right;
+ while (y->left != NULL)
+ y = y->left;
+ x = y->right;
+ }
+ if (y != z) { // 左右が両方埋まっていた時 yをzの位置に持ってきてzを浮かせる
+ z->left->parent = y;
+ y->left = z->left;
+ if (y != z->right) {
+ x_parent = y->parent;
+ if (x) x->parent = y->parent;
+ y->parent->left = x;
+ y->right = z->right;
+ z->right->parent = y;
+ } else
+ x_parent = y;
+ if (*root == z)
+ *root = y;
+ else if (z->parent->left == z)
+ z->parent->left = y;
+ else
+ z->parent->right = y;
+ y->parent = z->parent;
+ { int tmp=y->color; y->color=z->color; z->color=tmp; }
+ y = z;
+ } else { // どちらか空いていた場合 xをzの位置に持ってきてzを浮かせる
+ x_parent = y->parent;
+ if (x) x->parent = y->parent;
+ if (*root == z)
+ *root = x;
+ else if (z->parent->left == z)
+ z->parent->left = x;
+ else
+ z->parent->right = x;
+ }
+ // ここまで色の移動の除いて通常の2分木と同じ
+ if (y->color != RED) { // 赤が消える分には影響無し
+ while (x != *root && (x == NULL || x->color == BLACK))
+ if (x == x_parent->left) {
+ struct dbn* w = x_parent->right;
+ if (w->color == RED) {
+ w->color = BLACK;
+ x_parent->color = RED;
+ db_rotate_left(x_parent, root);
+ w = x_parent->right;
+ }
+ if ((w->left == NULL ||
+ w->left->color == BLACK) &&
+ (w->right == NULL ||
+ w->right->color == BLACK)) {
+ w->color = RED;
+ x = x_parent;
+ x_parent = x_parent->parent;
+ } else {
+ if (w->right == NULL ||
+ w->right->color == BLACK) {
+ if (w->left) w->left->color = BLACK;
+ w->color = RED;
+ db_rotate_right(w, root);
+ w = x_parent->right;
+ }
+ w->color = x_parent->color;
+ x_parent->color = BLACK;
+ if (w->right) w->right->color = BLACK;
+ db_rotate_left(x_parent, root);
+ break;
+ }
+ } else { // same as above, with right <-> left.
+ struct dbn* w = x_parent->left;
+ if (w->color == RED) {
+ w->color = BLACK;
+ x_parent->color = RED;
+ db_rotate_right(x_parent, root);
+ w = x_parent->left;
+ }
+ if ((w->right == NULL ||
+ w->right->color == BLACK) &&
+ (w->left == NULL ||
+ w->left->color == BLACK)) {
+ w->color = RED;
+ x = x_parent;
+ x_parent = x_parent->parent;
+ } else {
+ if (w->left == NULL ||
+ w->left->color == BLACK) {
+ if (w->right) w->right->color = BLACK;
+ w->color = RED;
+ db_rotate_left(w, root);
+ w = x_parent->left;
+ }
+ w->color = x_parent->color;
+ x_parent->color = BLACK;
+ if (w->left) w->left->color = BLACK;
+ db_rotate_right(x_parent, root);
+ break;
+ }
+ }
+ if (x) x->color = BLACK;
+ }
+}
+
+struct dbn* db_insert(struct dbt *table,void* key,void* data)
+{
+ struct dbn *p,*priv;
+ int c,hash;
+
+ hash = table->hash(table,key) % HASH_SIZE;
+ for(c=0,priv=NULL ,p = table->ht[hash];p;){
+ c=table->cmp(table,key,p->key);
+ if(c==0){ // replace
+ if (table->release)
+ table->release(p, 3);
+ p->data=data;
+ p->key=key;
+ return p;
+ }
+ priv=p;
+ if(c<0){
+ p=p->left;
+ } else {
+ p=p->right;
+ }
+ }
+#ifdef MALLOC_DBN
+ p=malloc_dbn();
+#else
+ CREATE(p, struct dbn, 1);
+#endif
+ if(p==NULL){
+ printf("out of memory : db_insert\n");
+ return NULL;
+ }
+ p->parent= NULL;
+ p->left = NULL;
+ p->right = NULL;
+ p->key = key;
+ p->data = data;
+ p->color = RED;
+ if(c==0){ // hash entry is empty
+ table->ht[hash] = p;
+ p->color = BLACK;
+ } else {
+ if(c<0){ // left node
+ priv->left = p;
+ p->parent=priv;
+ } else { // right node
+ priv->right = p;
+ p->parent=priv;
+ }
+ if(priv->color==RED){ // must rebalance
+ db_rebalance(p,&table->ht[hash]);
+ }
+ }
+ return p;
+}
+
+void* db_erase(struct dbt *table,void* key)
+{
+ void *data;
+ struct dbn *p;
+ int c,hash;
+
+ hash = table->hash(table,key) % HASH_SIZE;
+ for(c=0,p = table->ht[hash];p;){
+ c=table->cmp(table,key,p->key);
+ if(c==0)
+ break;
+ if(c<0)
+ p=p->left;
+ else
+ p=p->right;
+ }
+ if(!p)
+ return NULL;
+ data=p->data;
+ db_rebalance_erase(p,&table->ht[hash]);
+#ifdef MALLOC_DBN
+ free_dbn(p);
+#else
+ free(p);
+#endif
+ return data;
+}
+
+void db_foreach(struct dbt *table,int (*func)(void*,void*,va_list),...)
+{
+ int i,sp;
+ // red-black treeなので64個stackがあれば2^32個ノードまで大丈夫
+ struct dbn *p,*pn,*stack[64];
+ va_list ap;
+
+ va_start(ap,func);
+ for(i=0;i<HASH_SIZE;i++){
+ if((p=table->ht[i])==NULL)
+ continue;
+ sp=0;
+ while(1){
+ func(p->key,p->data,ap);
+ if((pn=p->left)!=NULL){
+ if(p->right){
+ stack[sp++]=p->right;
+ }
+ p=pn;
+ } else {
+ if(p->right){
+ p=p->right;
+ } else {
+ if(sp==0)
+ break;
+ p=stack[--sp];
+ }
+ }
+ }
+ }
+ va_end(ap);
+}
+
+void db_final(struct dbt *table,int (*func)(void*,void*,va_list),...)
+{
+ int i,sp;
+ struct dbn *p,*pn,*stack[64];
+ va_list ap;
+
+ va_start(ap,func);
+ for(i=0;i<HASH_SIZE;i++){
+ if((p=table->ht[i])==NULL)
+ continue;
+ sp=0;
+ while(1){
+ if(func)
+ func(p->key,p->data,ap);
+ if((pn=p->left)!=NULL){
+ if(p->right){
+ stack[sp++]=p->right;
+ }
+ } else {
+ if(p->right){
+ pn=p->right;
+ } else {
+ if(sp==0)
+ break;
+ pn=stack[--sp];
+ }
+ }
+#ifdef MALLOC_DBN
+ free_dbn(p);
+#else
+ free(p);
+#endif
+ p=pn;
+ }
+ }
+ free(table);
+ va_end(ap);
+}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-04 05:30:57 +0000