home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Kernel / Em / map.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-17  |  9.2 KB  |  452 lines
  1. /* Copyright 1986 Norm Hutchinson.     May not be used for any         *
  2.  * purpose without written permission from the author.               */
  3.  
  4. #include "Kernel/h/assert.h"
  5. #include "Kernel/h/system.h"
  6. #include "Kernel/h/map.h"
  7.  
  8. #define DEBUGMAP
  9. #define INITIALSIZE 16
  10.  
  11. #define HASH(key, map) ((((key)<< 1) ^ ((key) >> 6)) & map->maxIndex)
  12. static void CheckOutHashTable();
  13.  
  14. #define MAXMAPSTANDBY 20
  15. int              nextFreeMap = 0;
  16. Map              standbyMaps[MAXMAPSTANDBY];
  17.  
  18. #ifdef DEBUGMAP
  19. int inhibitCheck = 0;
  20. #endif
  21.  
  22. Map Map_Create()
  23. {
  24. #ifdef xkernel
  25.   int x = spl7();
  26. #endif xkernel
  27.   register int i;
  28.   register Map m;
  29.   register TEPtr    entryPtr;
  30.   register int myNil = NIL;
  31.   if (nextFreeMap > 0) {
  32.     /* Grab one from standby stack */
  33.     m           = standbyMaps[--nextFreeMap];
  34. #ifdef xkernel
  35.     splx(x);
  36. #endif xkernel
  37.     return m;
  38.   }
  39.  
  40.   /* Allocate a new one */
  41.   m = (Map) malloc(sizeof(MapRecord));
  42.   m->table = (TEPtr) malloc(INITIALSIZE * sizeof(TE));
  43.   m->maxIndex = INITIALSIZE - 1;
  44.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  45.   m->count = 0;
  46.   i = m->maxIndex;
  47.   entryPtr = &m->table[i+1];
  48.   do {
  49.       (--entryPtr)->key = myNil;
  50.   } while (--i >= 0);
  51. #ifdef DEBUGMAP
  52.       CheckOutHashTable(m);
  53. #endif DEBUGMAP
  54. #ifdef xkernel
  55.   splx(x);
  56. #endif xkernel
  57.   return(m);
  58. }
  59.  
  60. Map Map_CreateSized(fCount)
  61. int fCount;
  62. {
  63. #ifdef xkernel
  64.   int x = spl7();
  65. #endif xkernel
  66.   register int i;
  67.   register Map m;
  68.   register TEPtr    entryPtr;
  69.   register int myNil = NIL;
  70.   
  71.   assert(fCount > 0);
  72.   m = (Map) malloc(sizeof(MapRecord));
  73.   /* Make i the first power of two greater than fCount */
  74.   for (i = 1; i <= fCount; i += i);
  75.   i--;
  76.   m->maxIndex = i;
  77.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  78.   m->count = 0;
  79.   m->table = (TEPtr) malloc((unsigned)((m->maxIndex+1) * sizeof(TE)));
  80.   entryPtr = &m->table[i+1];
  81.   do {
  82.       (--entryPtr)->key = myNil;
  83.   } while (--i >= 0);
  84. # ifdef lint
  85.   CheckOutHashTable(m);
  86. #endif  
  87. #ifdef DEBUGMAP
  88.   CheckOutHashTable(m);
  89. #endif DEBUGMAP
  90. #ifdef xkernel
  91.   splx(x);
  92. #endif xkernel
  93.   return(m);
  94. }
  95.  
  96. void Map_Clear(m)
  97. register Map m;
  98. {
  99.   register int i;
  100.   register TEPtr entryPtr;
  101.   register int myNil = NIL;
  102.   
  103.   m->count      = 0;
  104.   i             = m->maxIndex;
  105.   entryPtr      = &m->table[i+1];
  106.   do {
  107.       (--entryPtr)->key = myNil;
  108.   } while (--i >= 0);
  109. }
  110.  
  111. void Map_Destroy(m)
  112. register Map m;
  113. {
  114.   register int i;
  115.   register TEPtr entryPtr;
  116.   register int myNil = NIL;
  117. #ifdef xkernel
  118.   int x;
  119. #endif xkernel
  120.   
  121.   if (m == (Map) NULL) return;
  122. #ifdef xkernel
  123.   x = spl7();
  124. #endif xkernel
  125.   if ((nextFreeMap < MAXMAPSTANDBY)
  126.     && (m->maxIndex == INITIALSIZE - 1)
  127.   ) {
  128.       if (m->count != 0) {
  129.       /* Reinitialize it */
  130.           m->count = 0;
  131.           i = m->maxIndex;
  132.       entryPtr = &m->table[i+1];
  133.       do {
  134.           (--entryPtr)->key = myNil;
  135.       } while (--i >= 0);
  136.       }
  137.       
  138.       /* Nice map, recycle it */
  139.       standbyMaps[nextFreeMap++] = m;
  140. #ifdef DEBUGMAP
  141.       CheckOutHashTable(m);
  142. #endif DEBUGMAP
  143. #ifdef xkernel
  144.       splx(x);
  145. #endif xkernel
  146.       return;
  147.   }
  148. #ifdef DEBUGMAP
  149.   CheckOutHashTable(m);
  150. #endif DEBUGMAP
  151.   free((char *)m->table);
  152.   free((char *)m);
  153. #ifdef xkernel
  154.   splx(x);
  155. #endif xkernel
  156. }
  157.  
  158. static void ExpandHashTable(m)
  159. register Map m;
  160. {
  161.   register TE *nh, *oe, *ne;
  162.   register int oldHashTableSize = m->maxIndex + 1, i;
  163.   register int key;
  164.   int index;
  165.  
  166.   m->maxIndex = oldHashTableSize * 2 - 1;
  167.   m->maxCount = m->maxIndex - (m->maxIndex >> 2);
  168.   nh = (TEPtr) malloc((unsigned)(oldHashTableSize * 2 * sizeof(TE)));
  169.   for (i = 0; i <= m->maxIndex; i++) nh[i].key = NIL;
  170.   for (i = 0; i < oldHashTableSize; i++) {
  171.     oe = &m->table[i];
  172.     key = oe->key;
  173.     if (key == NIL) continue;
  174.     index = HASH(key, m);
  175.     while (1) {
  176.       ne = &nh[index];
  177.       if (ne->key == NIL) {
  178.     ne->key = oe->key;
  179.     ne->value = oe->value;
  180.     break;
  181.       } else {
  182.     assert(ne->key !=key);
  183.     index++;
  184.     if (index > m->maxIndex) index = 0;
  185.       }
  186.     }
  187.   }
  188.   free((char *)m->table);
  189.   m->table = nh;
  190. #ifdef DEBUGMAP
  191.   CheckOutHashTable(m);
  192. #endif DEBUGMAP
  193. }
  194.  
  195. int Map_Lookup(m, key)
  196. register Map m;
  197. register int key;
  198. {
  199.   register int index = HASH(key, m);
  200.   register TEPtr e;
  201.   register int myNil = NIL;
  202.   register int limit = m->maxIndex;
  203.   
  204. #ifdef DEBUGMAP
  205.   CheckOutHashTable(m);
  206. #endif DEBUGMAP
  207.   e = &m->table[index];
  208.   while (1) {
  209.     if (e->key == myNil) {        /* we did not find it */
  210.       return (myNil);
  211.     } else if (e->key == key) {
  212.       return (e->value);
  213.     }
  214.     e++;
  215.     if (++index > limit) {
  216.     index = 0;
  217.         e = &m->table[0];
  218.     }
  219.   }
  220. }
  221.  
  222. int Map_InverseLookup(m, value)
  223. register Map m;
  224. register int value;
  225. /* do the inverse mapping; if ambiguous return any one of possible values */
  226. /* WARNING: Highly inefficient -- linear search */
  227. {
  228.   register TEPtr e, last;
  229.  
  230. #ifdef DEBUGMAP
  231.   CheckOutHashTable(m);
  232. #endif DEBUGMAP
  233.   for (last = &m->table[m->maxIndex+1], e = &m->table[0]; e != last; e++) {
  234.       if ((e->key != NIL) && (e->value == value)) return (e->key);
  235.   }
  236.   return ((int) NIL);
  237. }
  238.  
  239. void Map_Delete(m, key)
  240. register Map m;
  241. register int key;
  242. /* Remove the entry, if it is there */
  243. {
  244. #ifdef xkernel
  245.   int x = spl7();
  246. #endif xkernel
  247.   register int index = HASH(key, m);
  248.   register int value;
  249.   register TEPtr e;
  250.  
  251.   while (1) {
  252.     e = &m->table[index];
  253.     if (e->key == NIL) {        /* we did not find it */
  254. #ifdef DEBUGMAP
  255.       CheckOutHashTable(m);
  256. #endif DEBUGMAP
  257. #ifdef xkernel
  258.       splx(x);
  259. #endif xkernel
  260.       return;
  261.     }
  262.     if (e->key == key) {
  263.       /* Found it, now remove it */
  264.       m->count--;
  265.       e->key = NIL;
  266.       e->value = NIL;
  267. #ifdef DEBUGMAP
  268.       inhibitCheck = 1;
  269. #endif
  270.       while (1) {
  271.     /* rehash until we reach nil again */
  272.     if (++index > m->maxIndex) index = 0;
  273.     e = & m->table[index];
  274.     key = e->key;
  275.     if (key == NIL) {
  276. #ifdef DEBUGMAP
  277.         inhibitCheck = 0;
  278.         CheckOutHashTable(m);
  279. #endif DEBUGMAP
  280. #ifdef xkernel
  281.         splx(x);
  282. #endif xkernel
  283.         return;
  284.     }
  285.     /* rehashing is done by removing then reinserting */
  286.     value = e->value;
  287.     e->key = e->value = NIL;
  288.     m->count--;
  289.     Map_Insert(m, key, value);
  290.       }
  291.     }
  292.     if (++index > m->maxIndex) index = 0;
  293.   }
  294. }
  295.  
  296. void Map_Insert(m, key, value)
  297. register Map m;
  298. register int key, value;
  299. {
  300.   register int index;
  301.   register TEPtr e;
  302. #ifdef xkernel
  303.   int x = spl7();
  304. #endif xkernel
  305.   assert(key != NIL);
  306. #ifdef DEBUGMAP
  307.   CheckOutHashTable(m);
  308. #endif
  309.   if (m->count >= m->maxCount) ExpandHashTable(m);
  310.   index = HASH(key, m);
  311.   while (1) {
  312.     e = &m->table[index];
  313.     if (e->key == NIL) {        /* put it here */
  314.       e->key = key;
  315.       e->value = value;
  316.       m->count++;
  317. #ifdef DEBUGMAP
  318.       CheckOutHashTable(m);
  319. #endif DEBUGMAP
  320. #ifdef xkernel
  321.       splx(x);
  322. #endif xkernel
  323.       return;
  324.     } else if (e->key == key) {
  325.       e->value = value;
  326. #ifdef DEBUGMAP
  327.       CheckOutHashTable(m);
  328. #endif DEBUGMAP
  329. #ifdef xkernel
  330.       splx(x);
  331. #endif xkernel
  332.       return;
  333.     }
  334.     if (++index > m->maxIndex) index = 0;
  335.   }
  336. }
  337.  
  338. int Map_FindNext(m, startIndex, keyPtr, valuePtr)
  339. register Map m;
  340. int *startIndex;
  341. int *keyPtr, *valuePtr;
  342. {
  343.   register int i;
  344.   register TEPtr e;
  345. #ifdef xkernel
  346.   int x = spl7();
  347. #endif xkernel
  348.  
  349. #ifdef DEBUGMAP
  350.   CheckOutHashTable(m);
  351. #endif
  352.   for (i = *startIndex; i <= m->maxIndex; i++) {
  353.     e = &m->table[i];
  354.     if (e->key != NIL) {
  355.       *keyPtr = e->key;
  356.       *valuePtr = e->value;
  357.       *startIndex = i + 1;
  358. #ifdef xkernel
  359.       splx(x);
  360. #endif xkernel
  361.       return(1);
  362.     }
  363.   }
  364.   *keyPtr = NIL;
  365.   *valuePtr = NIL;
  366.   *startIndex = -1;
  367. #ifdef xkernel
  368.   splx(x);
  369. #endif xkernel
  370.   return(0);
  371. }
  372.  
  373. void Map_Print(m)
  374. register Map m;
  375. {
  376.     int key, value, index;
  377.     printf(
  378.     "\nDump of map @ 0x%05x, %d entr%s, max %d, maxIndex %d\nIndex\tKey\t\tValue\n",
  379.     m, m->count, m->count == 1 ? "y" : "ies",  m->maxCount, m->maxIndex);
  380.     for (index = 0; index <= m->maxIndex; index++) {
  381.     key = m->table[index].key;
  382.     value = m->table[index].value;
  383.     printf("%3d\t0x%08.8x\t0x%08.8x\n", index, key, value);
  384.     }
  385. }
  386.  
  387. #define isReasonable(x) ((int)(x) > 0 && (int)(x) < 0x1000000)
  388.  
  389. static void CheckOutHashTable(m)
  390. register Map m;
  391. {
  392.   register int i;
  393.   register TEPtr realElement, e;
  394.   register int index, firstIndex, count;
  395.   count = 0;
  396.  
  397. #ifdef DEBUGMAP
  398.   if (inhibitCheck) return;
  399. #endif
  400.   if (!isReasonable(m)) {
  401.     printf("Invalid map pointer 0x%x\n", m);
  402.     assert(0);
  403.   }
  404.   if (!isReasonable(m->table)) {
  405.     printf("Invalid map table pointer 0x%x\n", m->table);
  406.     assert(0);
  407.   }
  408.   for (i = 1; i < m->maxIndex; i <<= 1) ;
  409.   if (i != m->maxIndex + 1) {
  410.     printf("Weird maxindex = %d\n", m->maxIndex);
  411.     assert(0);
  412.   }
  413.   for (i = 0; i <= m->maxIndex; i++) {
  414.     realElement = &m->table[i];
  415.     if (realElement->key != NIL) {
  416.       count++;
  417.       index = HASH(realElement->key, m);
  418.       firstIndex = index;
  419.       while (1) {
  420.     e = &m->table[index];
  421.     if (e->key == NIL) {        /* we did not find it */
  422.       break;
  423.     } else if (e->key == realElement->key) {
  424.       break;
  425.     } else {
  426.       index++;
  427.       if (index > m->maxIndex) index = 0;
  428.       if (index == firstIndex) {
  429.         index = -1;
  430.         break;
  431.       }
  432.     }
  433.       }
  434.       
  435.       if (index == -1 || e->key != realElement->key) {
  436.       printf(
  437.         "Map problem: Key 0x%x, rightIndex %d, realIndex %d value 0x%x\n",
  438.         realElement->key, firstIndex, i, realElement->value);
  439.       Map_Print(m);
  440.       assert(0);
  441.       }
  442.     }
  443.   }  
  444.   if (count != m->count) {
  445.     printf("Map problem: Should have %d entries, but found %d.\n",
  446.        m->count, count);
  447.     Map_Print(m);
  448.     assert(0);
  449.   }
  450. }
  451.  
  452.