home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / cake / part03 / table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-14  |  2.2 KB  |  128 lines
  1. /*
  2. **    Table handling module.
  3. **
  4. **    This file supplies data manipulation routines to other modules;
  5. **    it does not store any data itself. Its routines are generic,
  6. **    applicable to the storage of any kind of data structure with
  7. **    primary key and a hash function on it.
  8. */
  9.  
  10. static    char
  11. rcs_id[] = "$Header: /mip/zs/src/sys/cake/RCS/table.c,v 1.15 87/10/05 20:16:28 zs Exp $";
  12.  
  13. #include    "cake.h"
  14.  
  15. /*
  16. **    Initialize a table.
  17. */
  18.  
  19. _init_table(table)
  20. reg    Table    *table;
  21. {
  22.     reg    int    i;
  23.  
  24.     table->ta_store = make_many(List *, table->ta_size);
  25.     for (i = 0; i < table->ta_size; i++)
  26.         table->ta_store[i] = NULL;
  27. }
  28.  
  29. /*
  30. **    Look up and return the entry corresponding to the key
  31. **    in a table.
  32. */
  33.  
  34. Cast
  35. _lookup_table(table, key)
  36. reg    Table    *table;
  37. reg    Cast    key;
  38. {
  39.     reg    List    *ptr;
  40.     reg    int    h;
  41.  
  42.     put_trail("lookup_table", "start");
  43.     h = tablehash(table)(key);
  44.     for_list (ptr, table->ta_store[h])
  45.     {
  46.         if (tableequal(table)(key, tablekey(table)(ldata(ptr))))
  47.         {
  48. #ifdef    EXTRACHECK
  49.             if (ldata(ptr) == NULL)
  50.             {
  51.                 fprintf(stderr, "cake internal error: returning null in lookup_table\n");
  52.                 exit_cake(TRUE);
  53.             }
  54. #endif
  55.             put_trail("lookup_table", "finish");
  56.             return ldata(ptr);
  57.         }
  58.     }
  59.  
  60.     put_trail("lookup_table", "finish");
  61.     return NULL;
  62. }
  63.  
  64. /*
  65. **    Insert a new entry into the table.
  66. **    Return whether it was there before.
  67. */
  68.  
  69. bool
  70. _insert_table(table, entry)
  71. reg    Table    *table;
  72. reg    Cast    entry;
  73. {
  74.     reg    List    *ptr;
  75.     reg    Cast    key;
  76.     reg    int    h;
  77.  
  78.     put_trail("insert_table", "start");
  79.     key = tablekey(table)(entry);
  80.     h   = tablehash(table)(key);
  81.     for_list (ptr, table->ta_store[h])
  82.         if (tableequal(table)(key, tablekey(table)(ldata(ptr))))
  83.         {
  84.             put_trail("insert_table", "finish");
  85.             return TRUE;
  86.         }
  87.  
  88.     table->ta_store[h] = addhead(table->ta_store[h], entry);
  89.     put_trail("insert_table", "finish");
  90.     return FALSE;
  91. }
  92.  
  93. /*
  94. **    Hash str into the range 0 to SIZE-1.
  95. */
  96.  
  97. int
  98. hash(s)
  99. reg    char    *s;
  100. {
  101.     reg    int    h;
  102.  
  103.     for (h = 0; *s != '\0'; s++)
  104.         h = (h << 1) + *s;
  105.  
  106.     return (h >= 0? h: -h) % SIZE;
  107. }
  108.  
  109. /*
  110. **    Return a list of all the entries in a table.
  111. */
  112.  
  113. List *
  114. _contents_table(table)
  115. reg    Table    *table;
  116. {
  117.     reg    List    *all;
  118.     reg    List    *ptr;
  119.     reg    int    i;
  120.  
  121.     all = makelist0();
  122.     for (i = 0; i < table->ta_size; i++)
  123.         for_list (ptr, table->ta_store[i])
  124.             addtail(all, ldata(ptr));    /* na */
  125.  
  126.     return all;
  127. }
  128.