Changeset 184 for trunk/thune/context.c

Timestamp:

06/12/06 01:58:22 (3 years ago)

Author:

krobillard

Message:

Thune -

Word lookup now uses an ordered binary search.
Renamed ur_setType as ur_initType.
Some error reporting improvements in eval.

Files:

• trunk/thune/context.c (modified) (8 diffs)

trunk/thune/context.c

@@ -48 +48 @@
             rec->nameLen );
     str->used += rec->nameLen;
+}
+
+
+const char* ur_atomCStr( UAtom atom )
+{
+    UBinary* names;
+    AtomRec* rec;
+
+    rec = ((AtomRec*) ur_env->atoms.ptr.v) + atom;
+    names = ur_binPtr( BIN_ATOM_NAMES );
+    return names->ptr.c + rec->nameIndex;
 }
 
@@ -124 +135 @@
 
     ur_arrayReserve( names, sizeof(char), names->used + len );
-    memCpy( names->ptr.c + names->used, buf, len );
-    names->used += len;
+    cp = names->ptr.c + names->used;
+    memCpy( cp, buf, len );
+    cp[len] = '\0';
+    names->used += len + 1;
 
 done:
@@ -131 +144 @@
     return rec - ((AtomRec*) atoms->ptr.v);
 }
+
+
+static int _binarySearch( UCell* words, int count, UAtom atom );
 
 
@@ -151 +167 @@
 
     wblk = ur_blockPtr( ctx->ctx.wordBlk );
-    it  = wblk->ptr.cells;
-    end = it + wblk->used;
-
-    while( it != end )
-    {
-        if( it->word.atom == atom )
-            return it - wblk->ptr.cells;
-        ++it;
+    it = wblk->ptr.cells;
+
+    if( (wblk->used < 6) || (it->word.sel == UR_CTX_UNORDERED) )
+    {
+        end = it + wblk->used;
+        while( it != end )
+        {
+            if( it->word.atom == atom )
+                return it - wblk->ptr.cells;
+            ++it;
+        }
+    }
+    else
+    {
+        wrdN = _binarySearch( it, wblk->used, atom );
+        if( wrdN > -1 )
+            return wrdN;
     }
 
@@ -167 +192 @@
     UR_EXPAND_1( UCell, wblk, it );
 
-    ur_setType( it, UT_WORD );
-    it->word.wordBlk = 0;       //ctx->ctx.wordBlk;
+    ur_initType( it, UT_WORD );
+    it->word.atom    = atom;
+    it->word.wordBlk = 0;
     it->word.valBlk  = ctx->ctx.valBlk;
-    it->word.index   = wrdN;
-    it->word.atom    = atom;
-
+    it->word.index   = 0;
+    it->word.sel     = 0;
+
+    wblk->ptr.cells->word.sel = UR_CTX_UNORDERED;
 
     vblk = ur_blockPtr( ctx->ctx.valBlk );
@@ -181 +208 @@
 
         it = vblk->ptr.cells + wrdN;
-        ur_setType( it, UT_UNSET );
+        ur_initType( it, UT_UNSET );
     }
 
     return wrdN;
+}
+
+
+#define QS_VAL(a)   cells[a].word.sel
+
+// Using series.end to swap word.index & word.sel together.
+#define QS_SWAP(a,b) \
+    stmp = cells[a].series.end; \
+    cells[a].series.end = cells[b].series.end; \
+    cells[b].series.end = stmp
+
+static void _quickSort( UCell* cells, int low, int high )
+{
+    int i, j;
+    UAtom val;
+    UIndex stmp;
+
+    if( low >= high )
+        return;
+
+    val = QS_VAL(low);
+    i = low;
+    j = high+1;
+    for(;;)
+    {
+        do i++; while( i <= high && QS_VAL(i) < val );
+        do j--; while( QS_VAL(j) > val );
+        if( i > j )
+            break;
+        QS_SWAP( i, j );
+    }
+    QS_SWAP( low, j );
+    _quickSort( cells, low, j-1 );
+    _quickSort( cells, j+1, high );
+}
+
+
+static void _orderWords( UCell* words, int count )
+{
+    UCell* it;
+    UCell* end;
+    int index = 0;
+
+    it  = words;
+    end = words + count;
+
+    while( it != end )
+    {
+        it->word.index = index++;
+        it->word.sel   = ur_atom(it);
+        ++it;
+    }
+
+    _quickSort( words, 0, count - 1 );
+}
+
+
+/*
+   Returns index of atom in word block or -1 if not found.
+*/
+static int _binarySearch( UCell* words, int count, UAtom atom )
+{
+    int sAtom;
+    int mid;
+    int low = 0;
+    int high = count - 1;
+
+    while( low <= high )
+    {
+        mid = ((unsigned int) (low + high)) >> 1;
+        sAtom = words[ mid ].word.sel;
+
+        if( sAtom < atom )
+            low = mid + 1;
+        else if( sAtom > atom )
+            high = mid - 1;
+        else
+            return words[ mid ].word.index;
+    }
+
+    // Atom not found.
+    return -1;
 }
 
@@ -198 +307 @@
     UCell* end;
 
-    /* There is unused space in wblk->ptr.cells which could be used to speed
-       up word search.  Some ideas:
-        - Min/max atom to fail early.
-        - Hash.
-        - Also store atoms in order and use binary search.
-     */
-
     wblk = ur_blockPtr( ctx->ctx.wordBlk );
-    it  = wblk->ptr.cells;
-    end = it + wblk->used;
-
-    while( it != end )
-    {
-        if( it->word.atom == atom )
-            return it - wblk->ptr.cells;
-        ++it;
-    }
-    return -1;
+    it = wblk->ptr.cells;
+
+    if( wblk->used < 6 )
+    {
+        end = it + wblk->used;
+        while( it != end )
+        {
+            if( it->word.atom == atom )
+                return it - wblk->ptr.cells;
+            ++it;
+        }
+        return -1;
+    }
+    else
+    {
+        if( it->word.sel == UR_CTX_UNORDERED )
+        {
+            _orderWords( it, wblk->used );
+        }
+        return _binarySearch( it, wblk->used, atom );
+    }
 }
 
@@ -270 +383 @@
 
 
-#if 0
-/*
-   Returns true if block contains does or func.
-*/
-int orClosureRequired( OIndex blkN )
-{
-    OBlock* blk = orBlockPtr( blkN );
-    UCell* it  = blk->values;
-    UCell* end = it + blk->used;
-
-    while( it != end )
-    {
-        if( (it->type == OT_WORD) ||
-            (it->type == OT_SETWORD) ||
-            (it->type == OT_GETWORD) )
-        {
-            if( (it->word.atom == orEnv->atom_func) ||
-                (it->word.atom == orEnv->atom_does) )
-                return 1;
-        }
-        else if( (it->type == OT_BLOCK) || (it->type == OT_PAREN) )
-        {
-            if( orClosureRequired( it->index ) )
-                return 1;
-        }
-
-        ++it;
-    }
-    return 0;
-}
-
-
-void orRebind( OIndex blkN, OIndex from, OIndex to )
-{
-    OBlock* blk = orBlockPtr( blkN );
-    UCell* it  = blk->values;
-    UCell* end = it + blk->used;
-
-    while( it != end )
-    {
-        if( (it->type == OT_WORD) ||
-            (it->type == OT_SETWORD) ||
-            (it->type == OT_GETWORD) )
-        {
-            if( it->word.context == from )
-                it->word.context = to;
-        }
-#if 0
-        else if( (it->type == OT_PATH) || (it->type == OT_SETPATH) )
-        {
-            UCell* path1 = orBLOCK( it )->values;
-            if( (path1->type == OT_WORD) ||
-                (path1->type == OT_SETWORD) ||
-                (path1->type == OT_GETWORD) )
-            {
-                if( path1->word.context == from )
-                    path1->word.context = to;
-            }
-        }
-#endif
-        else if( (it->type == OT_BLOCK) || (it->type == OT_PAREN) )
-        {
-            orRebind( it->index, from, to );
-        }
-
-        ++it;
-    }
-}
-#endif
-
-
-/*
-   (block context -- block)
-*/
-UR_CALL_PUB( uc_bind )
-{
-    UCell* bc;
-
-    UR_S_DROP;
-    bc = UR_TOS;
-
-    if( ur_is(tos, UT_LITWORD) || ur_is(tos, UT_CONTEXT) )
-    {
-        if( ur_is(bc, UT_BLOCK) )
-        {
-            ur_bind( bc->series.n, tos );
-            return;
-        }
-    }
-
-    ur_throwErr( ur_thread, UR_EX_DATATYPE, "Invalid bind values" );
-}
-
-
-#if 0
-void orProtectNative( UCell* a1 )
-{
-    OBlock* vblk;
-    OContext ctx;
-    int wrdN;
-
-    orGlobalCtx( ctx );
-    vblk = orBlockPtr( ctx.wblkN );
-
-    if( a1->type == OT_WORD )
-    {
-        wrdN = orLookup( &ctx, a1->word.atom );
-        if( wrdN > -1 )
-        {
-            vblk->values[ wrdN ].flags |= OR_WORD_PROT;
-        }
-    }
-    else if( a1->type == OT_BLOCK )
-    {
-        OBlock* blk = orBLOCK( a1 );
-        UCell* it  = blk->values;
-        UCell* end = it + blk->used;
-        while( it != end )
-        {
-            if( it->type == OT_WORD )
-            {
-                wrdN = orLookup( &ctx, a1->word.atom );
-                if( wrdN > -1 )
-                {
-                    vblk->values[ wrdN ].flags |= OR_WORD_PROT;
-                }
-            }
-            ++it;
-        }
-    }
-    orResultUNSET;
-}
-
-
-/*
-   object [object!]
-   word   [word!]
-*/
-void orInNative( UCell* a1 )
-{
-    UCell* a2 = a1 + 1;
-    OIndex wrdN;
-
-    wrdN = orLookup( &a1->ctx, a2->word.atom );
-    if( wrdN < 0 )
-    {
-        orResultNONE;
-    }
-    else
-    {
-        orSetTF( a1, OT_WORD );
-        // a1->context remains unchanged.
-        a1->word.index = wrdN;
-        a1->word.atom  = a2->word.atom;
-    }
-}
-
-
-/*
-   words [block! word!]
-   body  [block!]
-*/
-void orUseNative( UCell* a1 )
-{
-    OContext ctx;
-    OBlock* blk;
-    UCell* it;
-    UCell* end;
-    UCell* a2 = a1 + 1;
-
-
-    orRefPush( OT_BLOCK, a2->index );
-
-    if( a1->type == OT_WORD )
-    {
-        orMakeContext( &ctx, 1 );
-        orInternA( orBlockPtr( ctx.wblkN ), a1->word.atom );
-    }
-    else
-    {
-        orRefPush( OT_BLOCK, a1->index );
-
-        blk = orBLOCK( a1 );
-        it  = blk->values + a1->series.index;
-        end = blk->values + blk->used;
-
-        orMakeContext( &ctx, end - it );
-        blk = orBlockPtr( ctx.wblkN );
-
-        while( it != end )
-        {
-            if( it->type == OT_WORD )
-                orInternA( blk, it->word.atom );
-            ++it;
-        }
-
-        orRefPop( 1 );
-    }
-
-    blk = orBlockPtr( ctx.vblkN );
-    it  = blk->values;
-    end = it + blk->used;
-    while( it != end )
-    {
-        orSetTF( it, OT_UNSET );
-        ++it;
-    }
-
-    orBind( orBlockPtr( a2->index ), &ctx );
-
-    orRefPop( 1 );
-
-    orEvalBlock( orBlockPtr( a2->index ), a2->series.index );
-}
-#endif
-
-
 /*EOF*/