home *** CD-ROM | disk | FTP | other *** search
/ Super Net 1 / SUPERNET_1.iso / PC / OTROS / EXTRAS / UUCODE / UUPC / TEST / UPC12ES4.ZIP / RNEWS / idx.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-20  |  7.4 KB  |  389 lines
  1. /* idx.c
  2.  *
  3.  * simple index manager for UUPC news
  4.  *
  5.  * Author:  Kai Uwe Rommel <rommel@ars.muc.de>
  6.  * Created: Sun Aug 15 1993
  7.  */
  8.  
  9. static char *rcsid = "$Id: idx.c 1.3 1993/11/20 13:47:06 rommel Exp $";
  10. static char *rcsrev = "$Revision: 1.3 $";
  11.  
  12. /* $Log: idx.c $
  13.  * Revision 1.3  1993/11/20  13:47:06  rommel
  14.  * Truncate keys at 80 characters
  15.  *
  16.  * Revision 1.2  1993/11/06  17:54:55  rhg
  17.  * Drive Drew nuts by submitting cosmetic changes mixed in with bug fixes
  18.  *
  19.  * Revision 1.1  1993/09/05  10:56:49  rommel
  20.  * Initial revision
  21.  * */
  22.  
  23. #include <stdio.h>
  24. #include <stdlib.h>
  25. #include <io.h>
  26. #include <string.h>
  27.  
  28. #include "idx.h"
  29.  
  30. /* page level primitives */
  31.  
  32. static long idx_new_page(IDX *idx)
  33. {
  34.   long offset;
  35.  
  36.   if ((offset = lseek(idx -> file, 0, SEEK_END)) == -1)
  37.     return -1;
  38.  
  39.   if (chsize(idx -> file, offset + sizeof(PAGE)) == -1)
  40.     return -1;
  41.  
  42.   idx -> page_dirty = 0;
  43.   idx -> page_number = offset / sizeof(PAGE);
  44.  
  45.   return idx -> page_number;
  46. }
  47.  
  48. static int idx_get_page(IDX *idx, long number)
  49. {
  50.   long offset;
  51.  
  52.   idx -> page_dirty = 0;
  53.   idx -> page_number = number;
  54.   offset = idx -> page_number * sizeof(PAGE);
  55.  
  56.   if (lseek(idx -> file, offset, SEEK_SET) == -1)
  57.     return -1;
  58.  
  59.   if (read(idx -> file, &idx -> page, sizeof(PAGE)) != sizeof(PAGE))
  60.     return -1;
  61.  
  62.   return 0;
  63. }
  64.  
  65. static int idx_flush_page(IDX *idx)
  66. {
  67.   long offset;
  68.  
  69.   if (idx -> page_dirty)
  70.   {
  71.     idx -> page_dirty = 0;
  72.     offset = idx -> page_number * sizeof(PAGE);
  73.  
  74.     if (lseek(idx -> file, offset, SEEK_SET) == -1)
  75.       return -1;
  76.  
  77.     if (write(idx -> file, &idx -> page, sizeof(PAGE)) != sizeof(PAGE))
  78.       return -1;
  79.   }
  80.  
  81.   return 0;
  82. }
  83.  
  84. static int idx_push_page(IDX *idx, long number)
  85. {
  86.   idx_flush_page(idx);
  87.  
  88.   if (idx -> page_stacksize == IDX_MAXSTACK)
  89.     return -1;
  90.  
  91.   idx -> page_stack[idx -> page_stacksize++] = idx -> page_number;
  92.  
  93.   return idx_get_page(idx, number);
  94. }
  95.  
  96. static int idx_pop_page(IDX *idx)
  97. {
  98.   idx_flush_page(idx);
  99.  
  100.   if (idx -> page_stacksize == 0)
  101.     return -1;
  102.  
  103.   return idx_get_page(idx, idx -> page_stack[--idx -> page_stacksize]);
  104. }
  105.  
  106. /* the workhorses */
  107.  
  108. static int idx_search(IDX *idx, char *key)
  109. {
  110.   int n, cmp;
  111.  
  112.   for (;;)
  113.   {
  114.     for (n = idx -> page.items - 1; n >= 0 ; n--)
  115.     {
  116.       cmp = strcmp(key, idx -> page.item[n].key);
  117.  
  118.       if (cmp == 0)
  119.     return n;
  120.       else if (cmp > 0)
  121.       {
  122.     if (idx -> page.item[n].child)
  123.     {
  124.       idx_push_page(idx, idx -> page.item[n].child);
  125.       break;
  126.     }
  127.     else
  128.       return -1;
  129.       }
  130.     }
  131.  
  132.     if (n < 0)
  133.       if (idx -> page.child_0)
  134.     idx_push_page(idx, idx -> page.child_0);
  135.       else
  136.     return -1;
  137.   }
  138. }
  139.  
  140. static int idx_add(IDX *idx, ITEM new)
  141. {
  142.   int i, n;
  143.  
  144.   for (;;)
  145.   {
  146.     for (n = idx -> page.items; n > 0; n--)
  147.       if ( strcmp(new.key, idx -> page.item[n - 1].key) > 0 )
  148.     break;
  149.  
  150.     if (idx -> page.items < IDX_MAXITEM)
  151.     {
  152.       /* we are lucky */
  153.  
  154.       for (i = idx -> page.items; i > n; i--)
  155.       {
  156.     idx -> page.item[i] = idx -> page.item[i - 1];
  157.     idx -> page.item[i] = idx -> page.item[i - 1];
  158.       }
  159.  
  160.       idx -> page.items++;
  161.       idx -> page.item[n] = new;
  162.       idx -> page_dirty = 1;
  163.  
  164.       idx_flush_page(idx);
  165.  
  166.       return 0;
  167.     }
  168.     else
  169.     {
  170.       /* split page */
  171.  
  172.       ITEM up;
  173.       PAGE newpage;
  174.       long child_0;
  175.  
  176.       if (n <= IDX_MINITEM)
  177.       {
  178.     if (n != IDX_MINITEM)
  179.     {
  180.       up = idx -> page.item[IDX_MINITEM - 1];
  181.  
  182.       for (i = IDX_MINITEM - 1; i > n; i--)
  183.         idx -> page.item[i] = idx -> page.item[i - 1];
  184.  
  185.       idx -> page.item[n] = new;
  186.       new = up;
  187.     }
  188.  
  189.     for (i = 0; i < IDX_MINITEM; i++)
  190.       newpage.item[i] = idx -> page.item[IDX_MINITEM + i];
  191.       }
  192.       else
  193.       {
  194.     up = idx -> page.item[IDX_MINITEM];
  195.     n -= IDX_MINITEM;
  196.  
  197.     for (i = 0; i < n - 1; i++)
  198.       newpage.item[i] = idx -> page.item[IDX_MINITEM + i + 1];
  199.  
  200.     newpage.item[n - 1] = new;
  201.  
  202.     for (i = n; i < IDX_MINITEM; i++)
  203.       newpage.item[i] = idx -> page.item[IDX_MINITEM + i];
  204.  
  205.     new = up;
  206.       }
  207.   
  208.       newpage.child_0 = new.child;
  209.       idx -> page.items = newpage.items = IDX_MINITEM;
  210.  
  211.       if (idx -> page_stacksize == 0)
  212.       {
  213.     /* grow tree height */
  214.  
  215.     /* write both pieces onto new pages */
  216.  
  217.     child_0 = idx_new_page(idx);
  218.  
  219.     idx -> page_dirty = 1;
  220.     idx_flush_page(idx);
  221.  
  222.     new.child = idx_new_page(idx);
  223.     memcpy(&idx -> page, &newpage, sizeof(PAGE));
  224.  
  225.     idx -> page_dirty = 1;
  226.     idx_flush_page(idx);
  227.  
  228.     /* and keep the root on page zero */
  229.  
  230.     idx -> page.items = 1;
  231.     idx -> page.item[0] = new;
  232.     idx -> page.child_0 = child_0;
  233.  
  234.     idx -> page_number = 0;
  235.     idx -> page_dirty = 1;
  236.     idx_flush_page(idx);
  237.  
  238.     return 0;
  239.       }
  240.       else
  241.       {
  242.     /* write lower half onto old page */
  243.  
  244.     idx -> page_dirty = 1;
  245.     idx_flush_page(idx);
  246.  
  247.     /* and upper one onto new one */
  248.  
  249.     new.child = idx_new_page(idx);
  250.     memcpy(&idx -> page, &newpage, sizeof(PAGE));
  251.  
  252.     idx -> page_dirty = 1;
  253.     idx_flush_page(idx);
  254.  
  255.     /* and insert middle key into parent page */
  256.  
  257.     idx_pop_page(idx);
  258.       }
  259.     }
  260.   }
  261. }
  262.  
  263. /* interface functions */
  264.  
  265. IDX *idx_init(int file)
  266. {
  267.   IDX *idx;
  268.   long size;
  269.  
  270.   if ((idx = (IDX *) malloc(sizeof(IDX))) == NULL)
  271.     return NULL;
  272.  
  273.   idx -> magic = IDX_MAGIC;
  274.   idx -> file = file;
  275.  
  276.   if ((size = lseek(idx -> file, 0, SEEK_END)) == -1)
  277.     return free(idx), (IDX *) NULL;
  278.  
  279.   if (size % sizeof(PAGE) != 0)
  280.     return free(idx), (IDX *) NULL; /* consistency check */
  281.  
  282.   idx -> size = size / sizeof(PAGE);
  283.  
  284.   if (idx -> size == 0) /* new (empty) index needs initialization */
  285.   {
  286.     if (idx_new_page(idx) != 0)
  287.       return free(idx), (IDX *) NULL;
  288.  
  289.     idx -> size++;
  290.   }
  291.  
  292.   if (lseek(idx -> file, 0, SEEK_SET) == -1)
  293.     return free(idx), (IDX *) NULL;
  294.  
  295.   memset(&idx -> page, 0, sizeof(PAGE));
  296.   idx -> page_number = -1;
  297.   idx -> page_stacksize = 0;
  298.  
  299.   return idx;
  300. }
  301.  
  302. void idx_exit(IDX *idx)
  303. {
  304.   if (idx == NULL || idx -> magic != IDX_MAGIC)
  305.     return;
  306.  
  307.   idx_flush_page(idx);
  308.  
  309.   free(idx);
  310. }
  311.  
  312. int idx_addkey(IDX *idx, char *key, long offset, int size)
  313. {
  314.   int pos;
  315.   ITEM new;
  316.  
  317.   if (idx == NULL || idx -> magic != IDX_MAGIC)
  318.     return -1;
  319.  
  320.   idx_get_page(idx, 0);
  321.   idx -> page_stacksize = 0;
  322.  
  323.   if ((pos = idx_search(idx, key)) != -1)
  324.     return -1;
  325.  
  326.   strncpy(new.key, key, IDX_MAXKEY - 1);
  327.   new.key[IDX_MAXKEY - 1] = 0;
  328.   new.offset = offset;
  329.   new.size   = (short) size;
  330.   new.child  = 0;
  331.  
  332.   if (idx_add(idx, new) == -1)
  333.     return -1;
  334.  
  335.   return 0;
  336. }
  337.  
  338. int idx_getkey(IDX *idx, char *key, long *offset, int *size)
  339. {
  340.   int pos;
  341.  
  342.   if (idx == NULL || idx -> magic != IDX_MAGIC)
  343.     return -1;
  344.  
  345.   idx_get_page(idx, 0);
  346.   idx -> page_stacksize = 0;
  347.  
  348.   if ((pos = idx_search(idx, key)) == -1)
  349.     return -1;
  350.  
  351.   if (idx -> page.item[pos].offset == -1L)
  352.     return -1;
  353.  
  354.   *offset = idx -> page.item[pos].offset;
  355.   *size   = idx -> page.item[pos].size;
  356.  
  357.   return 0;
  358. }
  359.  
  360. int idx_delkey(IDX *idx, char *key, long *offset, int *size)
  361. {
  362.   int pos;
  363.  
  364.   if (idx == NULL || idx -> magic != IDX_MAGIC)
  365.     return -1;
  366.  
  367.   idx_get_page(idx, 0);
  368.   idx -> page_stacksize = 0;
  369.  
  370.   if ((pos = idx_search(idx, key)) == -1)
  371.     return -1;
  372.  
  373.   if (idx -> page.item[pos].offset == -1L)
  374.     return -1;
  375.  
  376.   *offset = idx -> page.item[pos].offset;
  377.   *size   = idx -> page.item[pos].size;
  378.  
  379.   idx -> page.item[pos].offset = -1L;
  380.   idx -> page.item[pos].size   = 0;
  381.  
  382.   idx -> page_dirty = 1;
  383.   idx_flush_page(idx);
  384.  
  385.   return 0;
  386. }
  387.  
  388. /* end of idx.c */
  389.