sync with rtgui-0.6

6 files changed, 174 insertions, 0 deletions

diff --git a/components/rtgui/utils/perfect_hash/example1-C/Makefile b/components/rtgui/utils/perfect_hash/example1-C/Makefile
new file mode 100644
index 0000000000..59b7ef0d67
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/Makefile
@@ -0,0 +1,31 @@
+
+CC = gcc -Wall
+
+
+lookup: main.o states-code.o
+	$(CC) -o $@ $^
+
+
+main.o: main.c states-code.h states.dat.h
+	$(CC) -c $<
+
+
+states-code.o: states-code.c states-code.h
+	$(CC) -c $<
+
+
+states-code.c: states.dat states-tmpl.c
+	../perfect_hash.py -vvvv --splitby '|' --keycol 2 $^
+
+
+states.dat.h: states.dat
+	./mk_header.py >$@
+
+
+clean:
+	rm lookup *.o states.dat.h states-code.c
+
+
+test:
+	./lookup 'NY'
+	./lookup 'QW'
diff --git a/components/rtgui/utils/perfect_hash/example1-C/main.c b/components/rtgui/utils/perfect_hash/example1-C/main.c
new file mode 100644
index 0000000000..0d36bcea45
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/main.c
@@ -0,0 +1,33 @@
+
+#include <stdio.h>
+
+#include "states-code.h"
+
+struct {
+  char *name;
+  char *abbr;
+  int pop;
+} states[] = {
+#include "states.dat.h"
+};
+
+
+int main (int argc, char *argv[])
+{
+  if (argc != 2) {
+    printf ("Usage: %s <abbreviation>\n", argv[0]);
+    return 2;
+  }
+
+  char *abbr = argv[1];
+  int hashval;
+  
+  if ((hashval = has_key(abbr)) == -1)
+    printf ("'%s' is not an abbreviation for a state.\n", abbr);
+  else
+    printf ("The state of %s has a population of %g million.\n",
+	    states[hashval].name,
+	    1e-6 * states[hashval].pop);
+  
+  return 0;
+}
diff --git a/components/rtgui/utils/perfect_hash/example1-C/mk_header.py b/components/rtgui/utils/perfect_hash/example1-C/mk_header.py
new file mode 100644
index 0000000000..646c0787be
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/mk_header.py
@@ -0,0 +1,10 @@
+#!/usr/bin/env python
+
+for line in file('states.dat'):
+    line = line.strip()
+    if line.startswith('#'):
+        continue
+    
+    row = tuple(entry.strip() for entry in line.split('|'))
+
+    print '  { "%s", "%s", %s },' % row 
diff --git a/components/rtgui/utils/perfect_hash/example1-C/states-code.h b/components/rtgui/utils/perfect_hash/example1-C/states-code.h
new file mode 100644
index 0000000000..5717b92d32
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/states-code.h
@@ -0,0 +1,6 @@
+
+
+/* Return hash value of abbreviation 'abbr' if found, -1 otherwise */
+int has_key (const char *abbr);
+
+
diff --git a/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c b/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c
new file mode 100644
index 0000000000..001ca6e5ce
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c
@@ -0,0 +1,42 @@
+
+#include <string.h>
+
+#include "states-code.h"
+
+
+static int T1[] = { $S1 };
+
+static int T2[] = { $S2 };
+
+static int G[] = { $G };
+
+static char *K[] = { $K };
+
+static int hash_g (const char *key, const int *T)
+{
+  int i, sum = 0;
+  
+  for (i = 0; key[i] != '\0'; i++) {
+    sum += T[i] * key[i];
+    sum %= $NG;
+  }
+  return G[sum];
+}
+
+static int perfect_hash (const char *key)
+{
+  if (strlen (key) > $NS)
+    return 0;
+  
+  return (hash_g (key, T1) + hash_g (key, T2)) % $NG;
+}
+
+int has_key (const char *abbr)
+{
+  int hash_value = perfect_hash (abbr);
+  
+  if (hash_value < $NK && strcmp(abbr, K[hash_value]) == 0)
+    return hash_value;
+  
+  return -1;
+}
diff --git a/components/rtgui/utils/perfect_hash/example1-C/states.dat b/components/rtgui/utils/perfect_hash/example1-C/states.dat
new file mode 100644
index 0000000000..5538309450
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example1-C/states.dat
@@ -0,0 +1,52 @@
+# Name         | Abr  | Population
+#--------------+------+---------
+Alabama        | AL   |  4335400
+Alaska         | AK   |   611500
+Arizona        | AZ   |  4664600
+Arkansas       | AR   |  2531000
+California     | CA   | 33198100
+Colorado       | CO   |  3930700
+Connecticut    | CT   |  3271100
+Delaware       | DE   |   736900
+Florida        | FL   | 15012200
+Georgia        | GA   |  7562200
+Hawaii         | HI   |  1188400
+Idaho          | ID   |  1221500
+Illinois       | IL   | 11981700
+Indiana        | IN   |  5882500
+Iowa           | IA   |  2854700
+Kansas         | KS   |  2603200
+Kentucky       | KY   |  3921000
+Louisiana      | LA   |  4361200
+Maine          | ME   |  1243700
+Maryland       | MD   |  5122400
+Massachusetts  | MA   |  6133500
+Michigan       | MI   |  9825100
+Minnesota      | MN   |  4704200
+Mississippi    | MS   |  2739700
+Missouri       | MO   |  5421400
+Montana        | MT   |   886400
+Nebraska       | NE   |  1661400
+Nevada         | NV   |  1828700
+New Hampshire  | NH   |  1179100
+New Jersey     | NJ   |  8078300
+New Mexico     | NM   |  1738700
+New York       | NY   | 18197800
+North Carolina | NC   |  7483100
+North Dakota   | ND   |   640000
+Ohio           | OH   | 11197900
+Oklahoma       | OK   |  3328100
+Oregon         | OR   |  3266800
+Pennsylvania   | PA   | 12044200
+Rhode Island   | RI   |   987000
+South Carolina | SC   |  3781800
+South Dakota   | SD   |   738500
+Tennessee      | TN   |  5398200
+Texas          | TX   | 19274300
+Utah           | UT   |  2071500
+Vermont        | VT   |   590400
+Virginia       | VA   |  6768400
+Washington     | WA   |  5674900
+West Virginia  | WV   |  1813200
+Wisconsin      | WI   |  5224500
+Wyoming        | WY   |   479500