home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume25 / trash / part01 / diblock.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-22  |  2.2 KB  |  145 lines
  1. #include    <stdio.h>
  2. #include    "entry.h"
  3. #include    "diblock.h"
  4. #include    "talloc.h"
  5. #include    "nels.h"
  6.  
  7. #define    TABZ    127
  8.  
  9. #define    abs(n)    (((n) < 0) ? -(n) : (n))
  10.  
  11. static entry    *hash_table[TABZ];
  12.  
  13. static
  14. entry    *
  15. mkent(dipc, key, data)
  16. dinstrn        *dipc;
  17. unsigned long    key;
  18. unsigned long    data;
  19. {
  20.     entry    *p;
  21.  
  22.     if ((p = talloc(entry)) == (entry *)0)
  23.     {
  24.         GLOBALdipc = dipc;
  25.         vcouldnot("allocate %d bytes for hash entry", sizeof(entry));
  26.         return (entry *)0;
  27.     }
  28.  
  29.     p->ent_key = key;
  30.     p->ent_data = data;
  31.     p->ent_right = (entry *)0;
  32.     p->ent_left = (entry *)0;
  33.  
  34.     return p;
  35. }
  36.  
  37. /*
  38.  * Given a key, return a pointer to the entry
  39.  * in the table corresponding to that key - or
  40.  * a pointer to the entry where it should be if
  41.  * it is not there.
  42.  */
  43. static
  44. entry    **
  45. lookup(key)
  46. unsigned long    key;
  47. {
  48.     entry    **pp;
  49.     int    flag;
  50.  
  51.     pp = &hash_table[abs(key) % nels(hash_table)];
  52.  
  53.     while
  54.     (
  55.         *pp != (entry *)0
  56.         &&
  57.         (flag = (key - (*pp)->ent_key)) != 0
  58.     )
  59.         pp = (flag > 0) ? &((*pp)->ent_right) : &((*pp)->ent_left);
  60.  
  61.     return pp;
  62. }
  63.  
  64. /*
  65.  * Delete an entry with the given key.
  66.  * If not there, return 0, else 1.
  67.  */
  68. static
  69. int
  70. del(key)
  71. unsigned long    key;
  72. {
  73.     entry    **p;
  74.     entry    *l;
  75.     entry    *r;
  76.  
  77.     if (*(p = lookup(key)) == (entry *)0)
  78.         return 0;
  79.  
  80.     l = (*p)->ent_left;
  81.     r = (*p)->ent_right;
  82.     (void)free(*p);
  83.  
  84.     if (l == (entry *)0)
  85.     {
  86.         *p = r;
  87.         return 1;
  88.     }
  89.  
  90.     if (r == (entry *)0)
  91.     {
  92.         *p = l;
  93.         return 1;
  94.     }
  95.  
  96.     *p = l;
  97.     while (l->ent_right != (entry *)0)
  98.         l = l->ent_right;
  99.     l->ent_right = r;
  100.  
  101.     return 1;
  102. }
  103.  
  104. diblock    *
  105. addr_to_decoded_block(dipc, addr)
  106. dinstrn        *dipc;
  107. unsigned long    addr;
  108. {
  109.     static unsigned long    lastaddr;
  110.     static diblock        *lastdiblockp;
  111.     entry            **pp;
  112.     entry            *p;
  113.  
  114.     addr /= SIMULATED_PAGE_SIZE;
  115.  
  116.     if (addr == lastaddr)
  117.         return lastdiblockp;
  118.  
  119.     lastaddr = addr;
  120.  
  121.     if ((p = *(pp = lookup(addr))) == (entry *)0)
  122.     {
  123.         diblock    *diblockp;
  124.  
  125.         if ((diblockp = talloc(diblock)) == (diblock *)0)
  126.         {
  127.             GLOBALdipc = dipc;
  128.             vcouldnot("allocate %d bytes for diblock", sizeof(diblock));
  129.             return (diblock *)0;
  130.         }
  131.  
  132.         diblockp->dib_want_init = 1;
  133.         diblockp->dib_first_addr = addr * SIMULATED_PAGE_SIZE;
  134.  
  135.         if ((p = mkent(dipc, addr, (unsigned long)diblockp)) == (entry *)0)
  136.             return (diblock *)0;
  137.  
  138.         *pp = p;
  139.     }
  140.  
  141.     lastdiblockp = (diblock *)p->ent_data;
  142.  
  143.     return lastdiblockp;
  144. }
  145.