Quick Search:

Mode

Context

Displaying 3 lines of context. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.49
 
1.50
 
MAIN:ragge:20070805082645
 
cpp.c
_>8888 
 8989 #define MAXARG  250     /* # of args to a macro, limited by char value */
 9090 #define SBSIZE  400000
<>91 -#define SYMSIZ  10000
9291 
 9392 static usch     sbf[SBSIZE];
 9493 /* C command */
     
 !
104103 #endif
 105104 
 106105 static int ofd;
<>107 -struct symtab symtab[SYMSIZ];
108106 static usch outbuf[CPPBUF];
 109107 static int obufp, istty;
 110108 int Cflag;
     
 !
738736 }
 739737 
 740738 /*
<>741 - * Do a symbol lookup.
 742 - * If enterf == ENTER, create a new entry.
 743 - * will return NULL if symbol not found and FIND is given.
 744 - */
 745 -struct symtab *
 746 -lookup(namep, enterf)
 747 -        usch *namep;
 748 -{
 749 -        usch *np;
 750 -        struct symtab *sp;
 751 -        int i, c, around;
 752 -
 753 -        DPRINT(("lookup '%s'\n", namep));
 754 -        np = namep;
 755 -        around = i = 0;
 756 -        while ((c = *np++))
 757 -                i += c;
 758 -        i %= SYMSIZ;
 759 -        sp = &symtab[i];
 760 -
 761 -        while (sp->namep) {
 762 -                if (*sp->namep == *namep &&
 763 -                    strcmp((char *)sp->namep, (char *)namep) == 0)
 764 -                        return sp->value || enterf == ENTER ? sp : NULL;
 765 -                if (++sp >= &symtab[SYMSIZ]) {
 766 -                        if (around++)
 767 -                                error("too many defines");
 768 -                        else
 769 -                                sp = symtab;
 770 -                }
 771 -        }
 772 -        if (enterf == ENTER)
 773 -                sp->namep = savstr(namep), savch('\0'), sp->value = NULL;
 774 -
 775 -        return(sp->namep ? sp : 0);
 776 -}
 777 -
 778 -/*
779739  * substitute namep for sp->value.
 780740  */
 781741 int
     
 !
12931253  *      unsigned char left[3];  offset from base to left element
 12941254  *      unsigned char right[3]; offset from base to right element
 12951255  */
<>1296 -poff ppole;
  1256+#endif
12971257 
<>1298 -poff
 1299 -plookup(usch *str, int type)
  1258+/*
  1259+ * This patricia implementation is more-or-less the same as
  1260+ * used in ccom for string matching.
  1261+ */
  1262+struct tree {
  1263+        int bitno;
  1264+        struct tree *lr[2];
  1265+};
  1266+
  1267+#define BITNO(x)                ((x) & ~(LEFT_IS_LEAF|RIGHT_IS_LEAF))
  1268+#define LEFT_IS_LEAF            0x80000000
  1269+#define RIGHT_IS_LEAF           0x40000000
  1270+#define IS_LEFT_LEAF(x)         (((x) & LEFT_IS_LEAF) != 0)
  1271+#define IS_RIGHT_LEAF(x)        (((x) & RIGHT_IS_LEAF) != 0)
  1272+#define P_BIT(key, bit)         (key[bit >> 3] >> (bit & 7)) & 1
  1273+#define CHECKBITS               8
  1274+
  1275+static struct tree *sympole;
  1276+static int numsyms;
  1277+
  1278+#define getree() malloc(sizeof(struct tree))
  1279+
  1280+/*
  1281+ * Allocate a symtab struct and store the string.
  1282+ */
  1283+static struct symtab *
  1284+getsymtab(usch *str)
13001285 {
<>1301 -        sbf[]
  1286+        struct symtab *sp = malloc(sizeof(struct symtab));
  1287+
  1288+        sp->namep = savstr(str), savch('\0'), sp->value = NULL;
  1289+        return sp;
13021290 }
<_1303 -#endif
  1291+
  1292+/*
  1293+ * Do symbol lookup in a patricia tree.
  1294+ * Only do full string matching, no pointer optimisations.
  1295+ */
  1296+struct symtab *
  1297+lookup(usch *key, int enterf)
  1298+{
  1299+        struct symtab *sp;
  1300+        struct tree *w, *new, *last;
  1301+        int len, cix, bit, fbit, svbit, ix, bitno;
  1302+        usch *k, *m, *sm;
  1303+
  1304+        /* Count full string length */
  1305+        for (k = key, len = 0; *k; k++, len++)
  1306+                ;
  1307+
  1308+        switch (numsyms) {
  1309+        case 0: /* no symbols yet */
  1310+                if (enterf != ENTER)
  1311+                        return NULL;
  1312+                sympole = (struct tree *)getsymtab(key);
  1313+                numsyms++;
  1314+                return (struct symtab *)sympole;
  1315+
  1316+        case 1:
  1317+                w = sympole;
  1318+                break;
  1319+
  1320+        default:
  1321+                w = sympole;
  1322+                bitno = len * CHECKBITS;
  1323+                for (;;) {
  1324+                        bit = BITNO(w->bitno);
  1325+                        fbit = bit > bitno ? 0 : P_BIT(key, bit);
  1326+                        svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
  1327+                            IS_LEFT_LEAF(w->bitno);
  1328+                        w = w->lr[fbit];
  1329+                        if (svbit)
  1330+                                break;
  1331+                }
  1332+        }
  1333+
  1334+        sp = (struct symtab *)w;
  1335+
  1336+        sm = m = sp->namep;
  1337+        k = key;
  1338+
  1339+        /* Check for correct string and return */
  1340+        for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
  1341+                ;
  1342+        if (*m == 0 && *k == 0) {
  1343+                if (enterf != ENTER && sp->value == NULL)
  1344+                        return NULL;
  1345+                return sp;
  1346+        }
  1347+
  1348+        if (enterf != ENTER)
  1349+                return NULL; /* no string found and do not enter */
  1350+
  1351+        ix = *m ^ *k;
  1352+        while ((ix & 1) == 0)
  1353+                ix >>= 1, cix++;
  1354+
  1355+        /* Create new node */
  1356+        new = getree();
  1357+        bit = P_BIT(key, cix);
  1358+        new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
  1359+        new->lr[bit] = (struct tree *)getsymtab(key);
  1360+
  1361+        if (numsyms++ == 1) {
  1362+                new->lr[!bit] = sympole;
  1363+                new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
  1364+                sympole = new;
  1365+                return (struct symtab *)new->lr[bit];
  1366+        }
  1367+
  1368+        w = sympole;
  1369+        last = NULL;
  1370+        for (;;) {
  1371+                fbit = w->bitno;
  1372+                bitno = BITNO(w->bitno);
  1373+                if (bitno == cix)
  1374+                        error("bitno == cix");
  1375+                if (bitno > cix)
  1376+                        break;
  1377+                svbit = P_BIT(key, bitno);
  1378+                last = w;
  1379+                w = w->lr[svbit];
  1380+                if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
  1381+                        break;
  1382+        }
  1383+
  1384+        new->lr[!bit] = w;
  1385+        if (last == NULL) {
  1386+                sympole = new;
  1387+        } else {
  1388+                last->lr[svbit] = new;
  1389+                last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
  1390+        }
  1391+        if (bitno < cix)
  1392+                new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
  1393+        return (struct symtab *)new->lr[bit];
  1394+}
  1395+
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-31 16:05 +0100