home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / geneal / part02 / index.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-08  |  7.0 KB  |  253 lines
  1. /* index - index handler for large pseudo-arrays
  2.  * Written by Jim McBeath (jimmc) at SCI
  3.  *
  4.  * Revision history:
  5.  * 24-Jan-85    Jim McBeath    Add enumIndex function
  6.  *  8-Mar-85    Jim McBeath    remove unused var numentries from enumIndex
  7.  * 17-Apr-86    Jim McBeath    Add field nzcount
  8.  * 19.Jan.87    J. McBeath    Add freeIndex
  9.  * 13.Feb.87    J. McBeath    Set nzcount to 0 on init
  10.  *  8.Jan.99  jimmc  Lint cleanup
  11.  */
  12.  
  13. /* This module implements a very large pseudo-array.  There are four
  14.    entry points: to initialize a pseudo-array, to insert an item,
  15.    to read an item, and to enumerate the entries in an array.  The
  16.    array contains integers (which could of course be used for another
  17.    purpose, such as pointers to something else).
  18.  
  19.    Structure of a table:
  20.    A table is a recursive structure which contains 2 words of size
  21.    information and n words of pointers.  The first word of size
  22.    information tells how many entries are represented by this and
  23.    all lower tables; the second word of size information tells how
  24.    many entries are actually in this table.  If the two numbers are
  25.    the same, then the table is an end node which actually has the
  26.    data entries in it.
  27. */
  28.  
  29. /*..........*/
  30.  
  31. #include "index.h"
  32.  
  33. extern char *malloc(), *calloc();
  34.  
  35. int indexDebug=0;        /* a debugging flag */
  36.  
  37. /*..........*/
  38.  
  39. struct toplevel *    /* pointer to the structure for future calls */
  40. initIndex()            /* init a new index table */
  41. {
  42.     struct toplevel *tt;
  43.     struct tblblock *dd;
  44.  
  45.     tt = (struct toplevel *)calloc((unsigned)sizeof(struct toplevel),1);
  46.     /* get space for top level block */
  47.     if (!tt) return 0;
  48.     dd = (struct tblblock *)calloc((unsigned)sizeof(struct tblblock),1);
  49.     /* get space for top level table */
  50.     if (!dd) {
  51.         free((char *)tt);
  52.         return 0;
  53.     }
  54.     tt->data = dd;            /* save pointer in our block */
  55.     tt->numlevs = 1;        /* we always start with one level */
  56.     tt->nzcount = 0;
  57.     dd->repnum = TBLSIZ;
  58.     dd->count = TBLSIZ;
  59.     return tt;            /* return pointer to top level block */
  60. }
  61.  
  62. /*..........*/
  63.  
  64. freeIndex(tt)
  65. struct toplevel *tt;
  66. {
  67.     freeBlock(tt->data);
  68.     free((char *)tt);
  69. }
  70.  
  71. static freeBlock(dd)
  72. struct tblblock *dd;
  73. {
  74.     int i;
  75.     if (dd->repnum > dd->count) {    /* not at lowest level */
  76.         for (i=0; i<dd->count; i++)
  77.             if (dd->tdata[i].p)
  78.                 freeBlock(dd->tdata[i].p);
  79.         /* free lower level tables */
  80.     }
  81.     free((char *)dd);
  82. }
  83.  
  84. /*..........*/
  85.  
  86. setIndex(tt,ix,num)        /* put index value into table */
  87. struct toplevel *tt;        /* table to use */
  88. int ix;                /* the index where it goes */
  89. long num;            /* the value to put there */
  90. {
  91.     struct tblblock *dd, *dd0;
  92.  
  93.     if (indexDebug) {
  94.         printf("setIndex: index=%d, value=%d\n", ix, num);
  95.         if (!tt) printf("setIndex: no table index\n");
  96.         else if (!(tt->numlevs)) printf("setIndex: no numlevs\n");
  97.         else if (!(tt->data)) printf("setIndex: no data array\n");
  98.     }
  99.     if (!tt) return -1;        /* check for errors */
  100.     if (!(tt->numlevs)) return -1;
  101.     if (!(tt->data)) return -1;
  102.     dd = tt->data;            /* get data pointer */
  103.     while (ix >= dd->repnum) {    /* create a higher level */
  104.         if (indexDebug)
  105.             printf("setIndex: %d(ix) > %d(repnum)\n",
  106.                 ix, dd->repnum);
  107.         dd0 = (struct tblblock *)calloc(
  108.             (unsigned)sizeof(struct tblblock),1);
  109.         /* get space for a higher level */
  110.         if (!dd0) return -1;        /* error */
  111.         dd0->repnum = dd->repnum*TBLSIZ;
  112.         dd0->count = TBLSIZ;
  113.         dd0->tdata[0].p = dd;
  114.             /* put in pointer to next level down */
  115.         tt->data = dd0;        /* put in new top-level pointer */
  116.         tt->numlevs++;
  117.         if (indexDebug)
  118.             printf("setIndex: numlevs=%d\n", tt->numlevs);
  119.         dd = dd0;
  120.     }
  121.     while (dd->repnum > dd->count) {
  122.         /* scan down to the last level */
  123.         if (indexDebug) printf("setIndex: %d(repnum) > %d(count)\n",
  124.             dd->repnum, dd->count);
  125.         dd0 = dd->tdata[ix/dd->count].p;
  126.         /* get pointer to next table lower */
  127.         if (!dd0) {
  128.             /* if no table there, have to make one */
  129.             dd0 = (struct tblblock *)calloc(
  130.                 (unsigned)sizeof(struct tblblock),1);
  131.             if (!dd0) return -1;        /* error */
  132.             dd0->repnum = dd->repnum/dd->count;
  133.             dd0->count = TBLSIZ;
  134.             dd->tdata[ix/dd->count].p = dd0;
  135.                 /* save pointer to it */
  136.         }
  137.         ix %= dd->count;        /* lower the index */
  138.         dd = dd0;
  139.     }
  140.     if (dd->tdata[ix].n) tt->nzcount--;
  141.     dd->tdata[ix].n = num;        /* put it in */
  142.     if (num) tt->nzcount++;
  143.     if (indexDebug)
  144.         printf("setIndex: table %X, index %d, value %d\n", dd,ix,num);
  145.     return ix;
  146. }
  147.  
  148. /*..........*/
  149.  
  150. long                /* return value out of table */
  151.                 /*  returns 0 if no entry */
  152. getIndex(tt,ix)
  153. struct toplevel *tt;
  154. int ix;                /* the index to look for */
  155. {
  156.     struct tblblock *dd, *dd0;
  157.  
  158.     if (indexDebug) {
  159.         printf("getIndex: index=%d\n", ix);
  160.         if (!tt) printf("getIndex: no table\n");
  161.         else if (!tt->data) printf("getIndex: no data array\n");
  162.         else if (!tt->numlevs) printf("genIndex: no numlevs\n");
  163.     }
  164.     if (!tt) return 0;        /* check for errors */
  165.     if (!tt->data) return 0;
  166.     if (!tt->numlevs) return 0;
  167.     dd = tt->data;
  168.     if (ix >= dd->repnum) {
  169.         if (indexDebug)
  170.             printf("getIndex: index %d > repnum %d\n",
  171.                 ix,dd->repnum);
  172.         return 0;    /* we don't have them that high */
  173.     }
  174.     while (dd->repnum > dd->count) {    /* scan down to bottom level */
  175.         if (indexDebug) printf("getIndex: %d(repnum) > %d(count)\n",
  176.             dd->repnum, dd->count);
  177.         dd0 = dd->tdata[ix/dd->count].p;
  178.             /* get pointer to next level */
  179.         if (!dd0) {
  180.             if (indexDebug) printf("getIndex: no table\n");
  181.             return 0;        /* nothing there */
  182.         }
  183.         ix %= dd->count;
  184.         dd = dd0;
  185.     }
  186.     if (indexDebug)
  187.         printf("getIndex: table %X, index %d, value %d\n",
  188.             dd, ix, dd->tdata[ix].n);
  189.     return dd->tdata[ix].n;        /* this is the data entry */
  190. }
  191.  
  192. /*..........*/
  193.  
  194. /* the enumerate function scans throught the table and calls (*f)(x,d) for
  195.  * each non-zero entry n in the table.  If f returns <>0, the enum routine
  196.  * stops scanning and returns an error.  (x is the index number, d is its
  197.  * value.)
  198.  */
  199. int            /* returns number of entries or <0 on error */
  200. enumIndex(tt,f)        /* enumerate the table */
  201. struct toplevel *tt;        /* the table to enumerate */
  202. int (*f)();            /* the function to call for each item */
  203. {
  204.  
  205.     if (indexDebug) {
  206.         if (!tt) printf("enumIndex: no table index\n");
  207.         else if (!(tt->numlevs)) printf("enumIndex: no numlevs\n");
  208.         else if (!(tt->data)) printf("enumIndex: no data array\n");
  209.     }
  210.     if (!tt) return -1;        /* check for errors */
  211.     if (!(tt->numlevs)) return -1;
  212.     if (!(tt->data)) return -1;
  213.     return enum1(tt->data,tt->numlevs,0,f);
  214.         /* do the enumeration recursively */
  215. }
  216.  
  217. static int
  218. enum1(dd,levs,b,f)
  219. struct tblblock *dd;        /* the datablock to enumerate */
  220. int levs;            /* the number of levels left to descend */
  221. int b;                /* the base number for this segment */
  222. int (*f)();            /* the function to call */
  223. {
  224.     int count=0;
  225.     int i, n;
  226.     int binc;
  227.  
  228.     if (levs<=1) {
  229.         for (i=0; i<TBLSIZ; i++) {    /* scan through the table */
  230.             if (dd->tdata[i].n) {
  231.                 n = (*f)(b+i,dd->tdata[i].n);
  232.                 if (n!=0) return -1;    /* error */
  233.                 count++;
  234.             }
  235.         }
  236.         return count;
  237.             /* return the number of entries processed */
  238.     }
  239.     else {        /* not yet at the bottom, keep descending */
  240.         binc = dd->repnum/TBLSIZ;
  241.         for (i=0; i<TBLSIZ; i++, b+=binc) {
  242.             if (dd->tdata[i].p) {
  243.                 n = enum1(dd->tdata[i].p,levs-1,b,f);
  244.                 if (n<0) return n;
  245.                 count += n;
  246.             }
  247.         }
  248.     }
  249.     return count;
  250. }
  251.  
  252. /* end */
  253.