engine/stringbucket.c

   1 /*
   2   stringbucket.c - MaLa stringbucket handling
   3
   4   Copyright (C) 2004, 2005, 2006, Christian Thaeter <chth@gmx.net>
   5
   6   This program is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License version 2 as
   8   published by the Free Software Foundation.
   9
  10   This program is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program; if not, contact me.
  17
  18 */
  19 \f
  20
  21 #include <stdlib.h>
  22 #include <llist.h>
  23 #include <acogc.h>
  24 #include <nobug.h>
  25 #include "stringbucket.h"
  26 #include "strings.h"
  27 #include "action.h"
  28
  29 /* fast simple low quality prng, low bits are random, 2^31-1 cycle */
  30 static inline uint32_t mala_fast_prng ()
  31 {
  32   static uint32_t rnd=0xbabeface;
  33   return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
  34 }
  35
  36 acogc_mark_result
  37 mala_stringbucket_acogc_mark (void * p)
  38 {
  39   TRACE (mala_acogc);
  40
  41   MalaStringBucket bucket = p;
  42   acogc_object_lastmark (bucket->tree);
  43   //acogc_object_mark (bucket->tree);
  44   return ACOGC_KEEP;
  45 }
  46
  47 void
  48 mala_stringbucket_acogc_initize (void * p)
  49 {
  50   TRACE (mala_acogc);
  51
  52   MalaStringBucket self = p;
  53   self->tree = NULL;
  54 }
  55
  56 acogc_mark_result
  57 mala_stringbucketnode_acogc_mark (void * p)
  58 {
  59   TRACE (mala_acogc);
  60
  61   MalaStringBucketNode node = p;
  62   acogc_object_mark (node->left);
  63   acogc_object_lastmark (node->right);
  64   //acogc_object_mark (node->right);
  65
  66   // TODO simpleremove if weakref is empty
  67
  68   return ACOGC_KEEP;
  69 }
  70
  71 void
  72 mala_stringbucketnode_acogc_initize (void * p)
  73 {
  74   TRACE (mala_acogc);
  75
  76   MalaStringBucketNode node = p;
  77   node->left = NULL;
  78   node->right = NULL;
  79   acogc_weakref_init (&node->weak_string);
  80 }
  81
  82 void
  83 mala_stringbucketnode_acogc_finalize (void * p)
  84 {
  85   TRACE (mala_acogc);
  86
  87   MalaStringBucketNode node = p;
  88   acogc_weakref_unlink (&node->weak_string);
  89 }
  90
  91 #ifdef EBUG_ACOGC //TODO
  92 static void
  93 mala_stringbucketnode_dump_ (FILE* g, MalaStringBucketNode_ref n, unsigned depth)
  94 {
  95   if (*n && depth)
  96     {
  97       if ((*n)->left)
  98         {
  99           fprintf(g, "\t\"%p:%s\":sw -> \"%p:%s\":n;\n",
 100                   *n,
 101                   mala_string_cstr ((MalaString)acogc_weakref_get (&(*n)->weak_string)),
 102                   (*n)->left,
 103                   mala_string_cstr ((MalaString)acogc_weakref_get (&(*n)->left->weak_string)));
 104           mala_stringbucketnode_dump_ (g, &(*n)->left, depth-1);
 105         }
 106
 107       if ((*n)->right)
 108         {
 109           fprintf(g, "\t\"%p:%s\":se -> \"%p:%s\":n;\n",
 110                   *n,
 111                   mala_string_cstr ((MalaString)acogc_weakref_get (&(*n)->weak_string)),
 112                   (*n)->right,
 113                   mala_string_cstr ((MalaString)acogc_weakref_get (&(*n)->right->weak_string)));
 114           mala_stringbucketnode_dump_ (g, &(*n)->right, depth-1);
 115         }
 116     }
 117 }
 118
 119 void
 120 mala_stringbucketnode_dump (const char* name, MalaStringBucketNode_ref n, unsigned depth)
 121 {
 122   static int cnt=0;
 123   char cmd[256];
 124   sprintf(cmd,"dot -Tps >/var/tmp/dbg_%d.ps; gv /var/tmp/dbg_%d.ps", cnt, cnt);
 125   FILE * graph = popen(cmd, "w");
 126
 127   fprintf(graph, "digraph \"%s\" { center=true; size=\"6,6\"; node [color=lightblue2, style=filled];", name);
 128   ++cnt;
 129
 130   fprintf(graph, "\t\"root\":s -> \"%p:%s\":n;\n",
 131           *n,
 132           mala_string_cstr ((MalaString)acogc_weakref_get (&(*n)->weak_string)));
 133
 134   mala_stringbucketnode_dump_ (graph, n, depth-1);
 135
 136   fprintf(graph, "}");
 137
 138   pclose(graph);
 139 }
 140 #endif
 141
 142
 143 inline static MalaStringBucketNode
 144 mala_stringbucketnode_new (const char * cstr,
 145                            mala_stringbucket_mode mode,
 146                            int c,
 147                            MalaStringBucketNode p,
 148                            MalaStringBucket bucket)
 149 {
 150   TRACE (mala_stringbucket);
 151
 152   ACOGC_STACK_ENTER (bucket->gcroot);
 153   ACOGC_STACK_PTR (MalaStringBucketNode, n);
 154   ACOGC_STACK_PTR (MalaString, s);
 155
 156   n.ptr = acogc_factory_alloc (bucket->gcfactory_splaynodes);
 157
 158   n.ptr->parent = p;
 159
 160   s.ptr = acogc_factory_alloc (bucket->gcfactory_strings);
 161
 162   s.ptr->len = strlen (cstr);
 163   s.ptr->str_alloc_type = ACOGC_ALLOC;
 164
 165   switch (mode)
 166     {
 167     case MALA_STRINGBUCKET_SEARCH:
 168       s.ptr->str = NULL;
 169       acogc_alloc (&s.ptr->str, s.ptr->len + 1, bucket->gcroot);
 170       strcpy ((char*)s.ptr->str, cstr);
 171       break;
 172     case MALA_STRINGBUCKET_REFERENCE:
 173       s.ptr->str_alloc_type = ACOGC_STATIC;
 174       //nobreak
 175     case MALA_STRINGBUCKET_ATTACH:
 176       s.ptr->str = cstr;
 177       break;
 178     case MALA_STRINGBUCKET_FIND:        // not used, just avoid a gcc warning
 179       break;
 180     }
 181
 182   acogc_weakref_link (&n.ptr->weak_string, s.ptr);
 183
 184   if (!p)
 185     bucket->tree = n.ptr;
 186   else
 187     {
 188       ASSERT (c, "c is 0");
 189       if (c < 0)
 190         p->left = n.ptr;
 191       else if (c > 0)
 192         p->right = n.ptr;
 193     }
 194
 195   INFO_DBG (mala_stringbucket, "create %p", n.ptr);
 196
 197   ASSERT (n.ptr->parent? (n.ptr->parent->left == n.ptr || n.ptr->parent->right == n.ptr): bucket->tree==n.ptr, "PARENT ERROR");
 198   ACOGC_STACK_LEAVE;
 199   return n.ptr;
 200 }
 201
 202 void
 203 mala_stringbucketnode_simpleremove (MalaStringBucketNode_ref n, MalaStringBucket bucket)
 204 {
 205   TRACE (mala_stringbucket);
 206
 207   //mala_stringbucketnode_dump ("remove before", &bucket->tree, 40);
 208   INFO_DBG (mala_stringbucket, "removing %p",*n);
 209   ASSERT ((*n)->parent? ((*n)->parent->left == *n || (*n)->parent->right == *n): bucket->tree==*n, "PARENT ERROR");
 210
 211   MalaStringBucketNode p = (*n)->parent;
 212   int c;
 213
 214   if (p && p->left == *n)
 215     c = -1;
 216   else
 217     c = 1;
 218
 219   if (!(*n)->left)
 220     // only right leaf
 221     *n = (*n)->right;
 222   else if (!(*n)->right)
 223     // only left leaf
 224     *n = (*n)->left;
 225   else
 226     {
 227       MalaStringBucketNode i;
 228       if (mala_fast_prng()&1) /* 50% probability removing left or right wards */
 229         {
 230           //left right
 231           TRACE_DBG (mala_stringbucket, "left right");
 232
 233           //for (i = (*n)->left; i->right; assert(i->right->parent == i),i = i->right);
 234           TODO ("reinst asserts");
 235           for (i = (*n)->left; i->right; i = i->right);
 236
 237           i->right = (*n)->right;
 238           if (i->parent != *n)
 239             {
 240               i->parent->right = i->left;
 241               if (i->left)
 242                 i->left->parent = i->parent;
 243               i->left = (*n)->left;
 244             }
 245         }
 246       else
 247         {
 248           // right left
 249           TRACE_DBG (mala_stringbucket, "right left");
 250
 251           TODO ("reinst asserts");
 252           //for (i = (*n)->right; i->left; assert(i->left->parent == i),i = i->left);
 253           for (i = (*n)->right; i->left; i = i->left);
 254
 255           i->left = (*n)->left;
 256           if (i->parent != *n)
 257             {
 258               i->parent->left = i->right;
 259               if (i->right)
 260                 i->right->parent = i->parent;
 261               i->right = (*n)->right;
 262             }
 263         }
 264       *n = i;
 265     }
 266
 267   if (!p)
 268     bucket->tree = *n;
 269   else
 270     {
 271       if (c < 0)
 272         p->left = *n;
 273       else
 274         p->right = *n;
 275     }
 276
 277   if (*n)
 278     {
 279       (*n)->parent = p;
 280       if((*n)->left)
 281         (*n)->left->parent = *n;
 282       if((*n)->right)
 283         (*n)->right->parent = *n;
 284     }
 285 }
 286
 287
 288 MalaStringBucketNode
 289 mala_stringbucket_node_find (MalaStringBucket bucket,
 290                              const char * cstr,
 291                              mala_stringbucket_mode mode)
 292 {
 293   TRACE (mala_stringbucket);
 294   int c = 1;
 295   MalaStringBucketNode p = NULL;
 296   MalaStringBucketNode n = bucket->tree;
 297
 298   while (1)
 299     {
 300       if (!n)
 301         {
 302           if (mode == MALA_STRINGBUCKET_FIND)
 303             return NULL;
 304
 305           n = mala_stringbucketnode_new (cstr, mode, c, p, bucket);
 306           mala_stringbucketnode_splay (n, bucket);
 307           ASSERT (n->parent? (n->parent->left == n || n->parent->right == n): bucket->tree==n, "PARENT ERROR");
 308           return n;
 309         }
 310
 311       MalaString s = acogc_weakref_get (&n->weak_string);
 312       if (!s)
 313         {
 314           // really freed nodes are removed from the tree
 315           mala_stringbucketnode_simpleremove (&n, bucket);
 316           continue;
 317         }
 318
 319       c = strcmp (cstr, mala_string_cstr (s));
 320
 321       p = n;
 322       if (c < 0)
 323         {
 324           n = n->left;
 325         }
 326       else if (c > 0)
 327         {
 328           n = n->right;
 329         }
 330       else
 331         {
 332           if (mode == MALA_STRINGBUCKET_ATTACH)
 333             // string already exists, so we can free the supplied string
 334             acogc_free (&cstr);
 335
 336           mala_stringbucketnode_splay (n, bucket);
 337           ASSERT (n->parent? (n->parent->left == n || n->parent->right == n): bucket->tree==n, "PARENT ERROR");
 338           return n;
 339         }
 340     }
 341 }
 342
 343 void
 344 mala_stringbucketnode_splay (MalaStringBucketNode n, MalaStringBucket bucket)
 345 {
 346   TRACE (mala_stringbucket);
 347
 348   while (n->parent)
 349     {
 350       MalaStringBucketNode p = n->parent;
 351       MalaStringBucketNode g = p?p->parent:NULL;
 352
 353       TRACE_DBG (mala_stringbucket, "splaying n %p, p %p, g %p",n,p,g);
 354
 355       if (g)
 356         {
 357           if (p == g->left)
 358             {
 359               // zig..
 360               if (n == p->left)
 361                 {
 362                   TRACE_DBG (mala_stringbucket, "zig zig %p",n);
 363                   if ((mala_fast_prng()&0xF) < mala_global_stringbucket_splay_zigzig)
 364                     return;
 365
 366                   g->left = p->right;
 367                   if (g->left) g->left->parent = g;
 368                   p->right = g;
 369
 370                   p->left = n->right;
 371                   if (p->left) p->left->parent = p;
 372                   n->right = p;
 373
 374                   n->parent = g->parent;
 375                   g->parent = p;
 376                 }
 377               else
 378                 {
 379                   TRACE_DBG (mala_stringbucket, "zig zag %p",n);
 380                   if ((mala_fast_prng()&0xF) < mala_global_stringbucket_splay_zigzag)
 381                     return;
 382
 383                   p->right = n->left;
 384                   if (p->right) p->right->parent = p;
 385                   n->left = p;
 386
 387                   g->left = n->right;
 388                   if (g->left) g->left->parent = g;
 389                   n->right = g;
 390
 391                   n->parent = g->parent;
 392                   g->parent = n;
 393                 }
 394             }
 395           else
 396             {
 397               // zag..
 398               if (n == p->left)
 399                 {
 400                   TRACE_DBG (mala_stringbucket, "zag zig %p", n);
 401                   if ((mala_fast_prng()&0xF) < mala_global_stringbucket_splay_zigzag)
 402                     return;
 403
 404                   p->left = n->right;
 405                   if (p->left) p->left->parent = p;
 406                   n->right = p;
 407
 408                   g->right = n->left;
 409                   if (g->right) g->right->parent = g;
 410                   n->left = g;
 411
 412                   n->parent = g->parent;
 413                   g->parent = n;
 414                 }
 415               else
 416                 {
 417                   TRACE_DBG (mala_stringbucket, "zag zag %p", n);
 418                   if ((mala_fast_prng()&0xF) < mala_global_stringbucket_splay_zigzig)
 419                     return;
 420
 421                   g->right = p->left;
 422                   if (g->right) g->right->parent = g;
 423                   p->left = g;
 424
 425                   p->right = n->left;
 426                   if (p->right) p->right->parent = p;
 427                   n->left = p;
 428
 429                   n->parent = g->parent;
 430                   g->parent = p;
 431                 }
 432             }
 433
 434           p->parent = n;
 435           if (n->parent)
 436             {
 437               if (n->parent->left == g)
 438                 n->parent->left = n;
 439               else
 440                 n->parent->right = n;
 441             }
 442           else
 443             {
 444               bucket->tree = n;
 445               return;
 446             }
 447         }
 448       else
 449         {
 450           if (p)
 451             {
 452               if ((mala_fast_prng()&0xF) < mala_global_stringbucket_splay_zig)
 453                 return;
 454
 455               if (n == p->left)
 456                 {
 457                   // ..zig
 458                   TRACE_DBG (mala_stringbucket, "zig %p", n);
 459                   p->left = n->right;
 460                   if (p->left) p->left->parent = p;
 461                   n->right = p;
 462                 }
 463               else
 464                 {
 465                   // ..zag
 466                   TRACE_DBG (mala_stringbucket, "zag %p", n);
 467                   p->right = n->left;
 468                   if (p->right) p->right->parent = p;
 469                   n->left = p;
 470                 }
 471               p->parent = n;
 472               n->parent = NULL;
 473               bucket->tree = n;
 474             }
 475           return;       // simple zig and zag are end-cases
 476         }
 477     }
 478 }
 479
 480
 481 MalaStringBucket
 482 mala_stringbucket_new (mala_string_cmp_fn cmpfn,
 483                        AcogcFactory bucketfactory,
 484                        AcogcFactory gcfactory_strings,
 485                        AcogcFactory gcfactory_splaynodes)
 486 {
 487   TRACE (mala_stringbucket);
 488
 489   ACOGC_STACK_ENTER (bucketfactory->root);
 490   ACOGC_STACK_PTR (MalaStringBucket, self);
 491
 492   self.ptr = acogc_factory_alloc (bucketfactory);
 493   mala_stringbucket_init (self.ptr, cmpfn, bucketfactory->root, gcfactory_strings, gcfactory_splaynodes);
 494
 495   ACOGC_STACK_LEAVE;
 496   return self.ptr;
 497 }
 498
 499
 500 void
 501 mala_stringbucket_init (MalaStringBucket bucket,
 502                         mala_string_cmp_fn cmpfn,
 503                         AcogcRoot gcroot,
 504                         AcogcFactory gcfactory_strings,
 505                         AcogcFactory gcfactory_splaynodes)
 506 {
 507   TRACE (mala_stringbucket);
 508
 509   bucket->tree = NULL;
 510   bucket->cmpfn = cmpfn;
 511   bucket->gcroot = gcroot;
 512   bucket->gcfactory_strings = gcfactory_strings,
 513   bucket->gcfactory_splaynodes = gcfactory_splaynodes;
 514 }
 515
 516
 517 /*
 518 // Local Variables:
 519 // mode: C
 520 // c-file-style: "gnu"
 521 // End:
 522 // arch-tag: 84fbd8ab-4e90-4d04-ab70-d9b955dde41c
 523 // end_of_file
 524 */