Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1.  
  2. /*=============================================================================
  3.    GNU UnRTF, a command-line program to convert RTF documents to other formats.
  4.    Copyright (C) 2000,2001 Zachary Thayer Smith
  5.  
  6.    This program is free software; you can redistribute it and/or modify
  7.    it under the terms of the GNU General Public License as published by
  8.    the Free Software Foundation; either version 2 of the License, or
  9.    (at your option) any later version.
  10.  
  11.    This program is distributed in the hope that it will be useful,
  12.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.    GNU General Public License for more details.
  15.  
  16.    You should have received a copy of the GNU General Public License
  17.    along with this program; if not, write to the Free Software
  18.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19.  
  20.    The author is reachable by electronic mail at tuorfa@yahoo.com.
  21. =============================================================================*/
  22.  
  23.  
  24. /*----------------------------------------------------------------------
  25.  * Module name:    hash
  26.  * Author name:    Zach Smith
  27.  * Create date:    01 Sep 00
  28.  * Purpose:        Word-hash management. Words are put into a hash and an
  29.  *                 identifier is returned. This is used to save us from
  30.  *                 doing multiple mallocs for recurring strings such as
  31.  *                 'the' and \par. This is not a big issue under Unix,
  32.  *                 but it is under other OSes and anyway, waste not want not.
  33.  *----------------------------------------------------------------------
  34.  * Changes:
  35.  * 08 Apr 01, tuorfa@yahoo.com: check for out of memory after malloc.
  36.  * 21 Apr 01, tuorfa@yahoo.com: signed to conversion unsigned bug
  37.  * 03 Aug 01, tuorfa@yahoo.com: fixes for using 16-bit compiler
  38.  * 22 Sep 01, tuorfa@yahoo.com: added function-level comment blocks
  39.  *--------------------------------------------------------------------*/
  40.  
  41. #include <stdio.h>
  42. #include <string.h>
  43.  
  44. #include "error.h"
  45. #include "main.h"
  46. #include "malloc.h"
  47.  
  48.  
  49. typedef struct _hi {
  50.         struct _hi *next;
  51.         char *str;
  52.         unsigned long value;
  53. }
  54. HashItem;
  55.  
  56.  
  57. /* Index by first char of string */
  58. static HashItem *hash[256];
  59. static unsigned long hash_length[256];
  60. static unsigned long hash_value=0;
  61.  
  62.  
  63.  
  64. /*========================================================================
  65.  * Name:        hash_init
  66.  * Purpose:     Clear the hash table.
  67.  * Args:        None.
  68.  * Returns:     None.
  69.  *=======================================================================*/
  70.  
  71. void
  72. hash_init ()
  73. {
  74.         int i;
  75.         for (i=0; i<256; i++) {
  76.                 hash[i]=NULL;
  77.                 hash_length[i]=0;
  78.         }
  79. }
  80.  
  81.  
  82.  
  83. /*========================================================================
  84.  * Name:        hash_stats
  85.  * Purpose:     Prints to stderr the number of words stored.
  86.  * Args:        None.
  87.  * Returns:     None.
  88.  *=======================================================================*/
  89.  
  90. void
  91. hash_stats ()
  92. {
  93.         int i;
  94.         unsigned long total=0;
  95.         for (i=0; i<256; i++) {
  96.                 total += hash_length[i];
  97.         }
  98.         fprintf (stderr,"%lu words were hashed.\n", total);
  99. }
  100.  
  101.  
  102.  
  103. /*========================================================================
  104.  * Name:        hashitem_new
  105.  * Purpose:     Creates a new linked list item for the hash table.
  106.  * Args:        String.
  107.  * Returns:     HashItem.
  108.  *=======================================================================*/
  109.  
  110. static HashItem *
  111. hashitem_new (char *str)
  112. {
  113.         HashItem *hi;
  114.         unsigned long i;
  115.  
  116.         hi=(HashItem*) my_malloc(sizeof(HashItem));
  117.         if (!hi)
  118.                 error_handler ("out of memory");
  119.         memset ((void*)hi, 0, sizeof (HashItem));
  120.  
  121.         hi->str = my_strdup(str);
  122.  
  123.         i = *str;
  124.         if (i=='\\') i=str[1];
  125.         i <<= 24;
  126.         hi->value = i | (hash_value++ & 0xffffff);
  127.         hi->next = NULL;
  128.  
  129. #if 0
  130.         if (debug_mode) {
  131.                 printf ("<!-- storing val %08lx str %s -->\n",
  132.                         hi->value, hi->str);
  133.         }
  134. #endif
  135.  
  136.         return hi;
  137. }
  138.  
  139.  
  140. /*========================================================================
  141.  * Name:        hash_get_index
  142.  * Purpose:     Given a string, returns the "index" i.e. the word identifier.
  143.  * Args:        String.
  144.  * Returns:     Index.
  145.  *=======================================================================*/
  146.  
  147. unsigned long
  148. hash_get_index (char *str)
  149. {
  150.         unsigned short index;
  151.         HashItem *hi;
  152.         char ch;
  153.  
  154.         ch = *str;
  155.         if (ch=='\\' && *(str+1))
  156.                 ch = *(str+1);
  157.         index = (unsigned) ch;
  158.         hi = hash[index];
  159.         while (hi) {
  160.                 if (!strcmp(hi->str,str))
  161.                         return hi->value;
  162.                 hi=hi->next;
  163.         }
  164.         /* not in hash */
  165.         hi = hashitem_new (str);
  166.         hi->next = hash[index];
  167.         hash [index] = hi;
  168.         ++hash_length [index];
  169.         return hi->value;
  170. }
  171.  
  172.  
  173. /*========================================================================
  174.  * Name:        hash_get_string
  175.  * Purpose:     Given the index (word identifier) returns the word string.
  176.  * Args:        Index.
  177.  * Returns:     String, or NULL if not found.
  178.  *=======================================================================*/
  179.  
  180. char*
  181. hash_get_string (unsigned long value)
  182. {
  183.         int index;
  184.         HashItem *hi;
  185.         index = value >> 24;
  186.         hi = hash[index];
  187.         while (hi) {
  188.                 if (hi->value == value)
  189.                         return hi->str;
  190.                 hi=hi->next;
  191.         }
  192.         warning_handler ("word not in hash");
  193.         return NULL;
  194. }
  195.  
  196.  
  197.  
  198.