Index: core.ops
===================================================================
RCS file: /home/perlcvs/parrot/core.ops,v
retrieving revision 1.130
diff -p -u -b -r1.130 core.ops
--- core.ops	24 Apr 2002 20:31:39 -0000	1.130
+++ core.ops	25 Apr 2002 16:25:25 -0000
@@ -3,14 +3,13 @@
 */
 
 /* This (now even more) convoluted mess avoids costly runtime creation
- * of KEY and KEY_PAIR structures, and can be used in an expression.
+ * of KEY structures, and can be used in an expression.
  */
 
-#define MAKE_KEY(k,k_p,v,c,t) (\
-        k_p.type = c,\
-        k_p.cache.t = v,\
-        k.size = 1,\
-        k.keys = &k_p,\
+#define MAKE_KEY(k,v,c,t) (\
+        k.atom.type = c,\
+        k.atom.val.t = v,\
+        k.next = NULL,\
         &k)
 
 VERSION = PARROT_VERSION;
@@ -599,97 +598,85 @@ inline op set(out INT, in PMC) {
 }
 
 inline op get_keyed(out INT, in PMC, in INT) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_int, int_val);
+  MAKE_KEY(key, $3, enum_key_int, int_val);
   $1 = $2->vtable->get_integer_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out INT, in PMC, in NUM) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_num, num_val);
+  MAKE_KEY(key, $3, enum_key_num, num_val);
   $1 = $2->vtable->get_integer_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out INT, in PMC, in STR) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_string, struct_val);
+  MAKE_KEY(key, $3, enum_key_string, struct_val);
   $1 = $2->vtable->get_integer_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out NUM, in PMC, in INT) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_int, int_val);
+  MAKE_KEY(key, $3, enum_key_int, int_val);
   $1 = $2->vtable->get_number_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out NUM, in PMC, in NUM) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_num, num_val);
+  MAKE_KEY(key, $3, enum_key_num, num_val);
   $1 = $2->vtable->get_number_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out NUM, in PMC, in STR) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_string, struct_val);
+  MAKE_KEY(key, $3, enum_key_string, struct_val);
   $1 = $2->vtable->get_number_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out STR, in PMC, in INT) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_int, int_val);
+  MAKE_KEY(key, $3, enum_key_int, int_val);
   $1 = $2->vtable->get_string_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out STR, in PMC, in NUM) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_num, num_val);
+  MAKE_KEY(key, $3, enum_key_num, num_val);
   $1 = $2->vtable->get_string_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out STR, in PMC, in STR) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_string, struct_val);
+  MAKE_KEY(key, $3, enum_key_string, struct_val);
   $1 = $2->vtable->get_string_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out PMC, in PMC, in INT) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_int, int_val);
+  MAKE_KEY(key, $3, enum_key_int, int_val);
   $1 = $2->vtable->get_pmc_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out PMC, in PMC, in NUM) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_num, num_val);
+  MAKE_KEY(key, $3, enum_key_num, num_val);
   $1 = $2->vtable->get_pmc_keyed(interpreter, $2, &key);
   goto NEXT();
 }
 
 inline op get_keyed(out PMC, in PMC, in STR) {
-  KEY_PAIR key_p;
   KEY key;
-  MAKE_KEY(key, key_p, $3, enum_key_string, struct_val);
+  MAKE_KEY(key, $3, enum_key_string, struct_val);
   $1 = $2->vtable->get_pmc_keyed(interpreter, $2, &key);
   goto NEXT();
 }
@@ -701,11 +688,10 @@ inline op get_keyed(out PMC, in PMC, in 
 =cut
 
 inline op set_keyed (out PMC, in PMC, in PMC, in PMC)  {
-    KEY_PAIR src_key_p, dest_key_p;
     KEY src_key, dest_key;
 
-    MAKE_KEY(src_key, src_key_p, $2, enum_key_pmc, pmc_val);
-    MAKE_KEY(dest_key, dest_key_p, $4, enum_key_pmc, pmc_val);
+    MAKE_KEY(src_key, $2, enum_key_pmc, pmc_val);
+    MAKE_KEY(dest_key, $4, enum_key_pmc, pmc_val);
 
     $1->vtable->set_pmc_keyed(interpreter, 
                     $1, $2 ? &src_key : NULL, $3, $4 ? &dest_key : NULL);
@@ -713,120 +699,108 @@ inline op set_keyed (out PMC, in PMC, in
 }
 
 inline op set_keyed (out PMC, in INT, in INT)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_int, int_val);
+    MAKE_KEY(key, $2, enum_key_int, int_val);
 
     $1->vtable->set_integer_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in NUM, in INT)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_num, num_val);
+    MAKE_KEY(key, $2, enum_key_num, num_val);
 
     $1->vtable->set_integer_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in STR, in INT)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_string, struct_val);
+    MAKE_KEY(key, $2, enum_key_string, struct_val);
 
     $1->vtable->set_integer_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in INT, in NUM)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_int, int_val);
+    MAKE_KEY(key, $2, enum_key_int, int_val);
 
     $1->vtable->set_number_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in NUM, in NUM)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_num, num_val);
+    MAKE_KEY(key, $2, enum_key_num, num_val);
 
     $1->vtable->set_number_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in STR, in NUM)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_string, struct_val);
+    MAKE_KEY(key, $2, enum_key_string, struct_val);
 
     $1->vtable->set_number_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in INT, in STR)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_int, int_val);
+    MAKE_KEY(key, $2, enum_key_int, int_val);
 
     $1->vtable->set_string_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in NUM, in STR)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_num, num_val);
+    MAKE_KEY(key, $2, enum_key_num, num_val);
 
     $1->vtable->set_string_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in STR, in STR)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_string, struct_val);
+    MAKE_KEY(key, $2, enum_key_string, struct_val);
 
     $1->vtable->set_string_keyed(interpreter, $1, &key, $3);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in INT, in PMC)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_int, int_val);
+    MAKE_KEY(key, $2, enum_key_int, int_val);
 
     $1->vtable->set_pmc_keyed(interpreter, $1, &key, $3, NULL);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in NUM, in PMC)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_num, num_val);
+    MAKE_KEY(key, $2, enum_key_num, num_val);
 
     $1->vtable->set_pmc_keyed(interpreter, $1, &key, $3, NULL);
     goto NEXT();
 }
 
 inline op set_keyed (out PMC, in STR, in PMC)  {
-    KEY_PAIR key_p;
     KEY key;
 
-    MAKE_KEY(key, key_p, $2, enum_key_string, struct_val);
+    MAKE_KEY(key, $2, enum_key_string, struct_val);
 
     $1->vtable->set_pmc_keyed(interpreter, $1, &key, $3, NULL);
     goto NEXT();
Index: embed.c
===================================================================
RCS file: /home/perlcvs/parrot/embed.c,v
retrieving revision 1.20
diff -p -u -b -r1.20 embed.c
--- embed.c	2 Apr 2002 20:35:52 -0000	1.20
+++ embed.c	25 Apr 2002 16:25:26 -0000
@@ -167,7 +167,6 @@ Parrot_runcode(struct Parrot_Interp *int
     INTVAL i;
     PMC *userargv;
     KEY key;
-    KEY_PAIR key_p;
 
     if (Interp_flags_TEST(interpreter, PARROT_DEBUG_FLAG)) {
         fprintf(stderr, "*** Parrot VM: Debugging enabled. ***\n");
@@ -201,9 +200,8 @@ Parrot_runcode(struct Parrot_Interp *int
     /* immediately anchor pmc to root set */
     interpreter->pmc_reg.registers[0] = userargv;
 
-    key.size = 1;
-    key.keys = &key_p;
-    key_p.type = enum_key_int;
+    key.atom.type = enum_key_int;
+    key.next = NULL;
 
     for (i = 0; i < argc; i++) {
         STRING* arg = string_make(interpreter, argv[i], strlen(argv[i]),
@@ -213,7 +211,7 @@ Parrot_runcode(struct Parrot_Interp *int
             fprintf(stderr, "\t" INTVAL_FMT ": %s\n", i, argv[i]);
         }
 
-        key_p.cache.int_val = i;
+        key.atom.val.int_val = i;
         userargv->vtable->set_string_keyed(interpreter, userargv, &key, arg);
     }
 
Index: key.c
===================================================================
RCS file: /home/perlcvs/parrot/key.c,v
retrieving revision 1.24
diff -p -u -b -r1.24 key.c
--- key.c	2 Apr 2002 20:35:52 -0000	1.24
+++ key.c	25 Apr 2002 16:25:27 -0000
@@ -14,107 +14,6 @@
 
 #include "parrot/parrot.h"
 
-struct _bucket {
-    KEY_PAIR pair;
-    STRING *key;
-    struct _bucket *next;
-};
-
-typedef struct _bucket BUCKET;
-
-static void
-debug_key(struct Parrot_Interp *interpreter, KEY *key)
-{
-    INTVAL i;
-    fprintf(stderr, " *** key %p\n", key);
-    fprintf(stderr, " *** size " INTVAL_FMT "\n", key->size);
-    for (i = 0; i < key->size; i++) {
-        INTVAL type = key->keys[i].type;
-        if (type == enum_key_bucket) {
-            fprintf(stderr, " *** Bucket " INTVAL_FMT " type " INTVAL_FMT "\n",
-                    i, type);
-        }
-        else if (type != enum_key_undef) {
-            fprintf(stderr, " *** Other " INTVAL_FMT " type " INTVAL_FMT "\n",
-                    i, type);
-        }
-    }
-}
-
-static BUCKET *
-new_bucket(struct Parrot_Interp *interpreter, STRING *key, KEY_PAIR *pair)
-{
-    BUCKET *bucket = mem_sys_allocate(sizeof(BUCKET));
-    if (bucket != NULL) {
-        if (key != NULL) {
-            if (pair != NULL) {
-                bucket->key = string_copy(interpreter, key);
-                memcpy(&bucket->pair, pair, sizeof(KEY_PAIR));
-            }
-            else {
-                fprintf(stderr, "*** new_bucket was given a null pair\n");
-            }
-        }
-        else {
-            fprintf(stderr, "*** new_bucket was given a null key\n");
-        }
-    }
-    else {
-        fprintf(stderr, "*** new_bucket attempted to return a null bucket\n");
-    }
-    return bucket;
-}
-
-static KEY_PAIR *
-find_bucket(struct Parrot_Interp *interpreter, BUCKET *head, STRING *key)
-{
-    KEY_PAIR *pair = NULL;
-    if (head != NULL) {
-        if (key != NULL) {
-            while (head != NULL) {
-                if (string_compare(interpreter, key, head->key) == 0) {
-                    pair = &head->pair;
-                    break;
-                }
-                head = head->next;
-            }
-        }
-        else {
-            fprintf(stderr, "*** find_bucket given a null key\n");
-        }
-    }
-    else {
-        fprintf(stderr, "*** find_bucket given a null bucket\n");
-    }
-    return pair;
-}
-
-/*=for api key key_hash
-
-Return the hashed value of the string
-
-=cut
-*/
-
-static INTVAL
-key_hash(struct Parrot_Interp *interpreter, STRING *value)
-{
-    char *buffptr = value->bufstart;
-    INTVAL len = value->bufused;
-    INTVAL hash = 5893;
-
-    UNUSED(interpreter);
-
-    while (len--) {
-        hash = hash * 33 + *buffptr++;
-    }
-    if (hash < 0) {
-        hash = -hash;
-    }
-    return hash;
-}
-
-
 /*=for api key key_new
 
 Return a pointer to a new KEY structure
@@ -123,14 +22,14 @@ Return a pointer to a new KEY structure
 */
 
 KEY *
-key_new(struct Parrot_Interp *interpreter)
+key_new(Interp *interpreter)
 {
     KEY *key = mem_sys_allocate(sizeof(KEY));
 
     UNUSED(interpreter);
 
-    key->size = 0;
-    key->keys = NULL;
+    key->atom.type = enum_key_undef;
+    key->next = NULL;
 
     return key;
 }
@@ -143,345 +42,15 @@ Return a copy of the KEY <key>.
 */
 
 KEY *
-key_clone(struct Parrot_Interp *interpreter, KEY *key)
+key_clone(Interp *interpreter, KEY *key)
 {
     KEY *new_key = NULL;
-    if (key != NULL) {
+    if (key == NULL) return NULL;
         new_key = key_new(interpreter);
-        memcpy(new_key, key, sizeof(KEY));
-    }
-    else {
-        fprintf(stderr, "*** key_clone attempted to clone a NULL variable\n");
-    }
+    new_key->atom = key->atom;
+    new_key->next = key_clone(interpreter, key->next);
     return new_key;
 }
-
-/*=for api key key_size
-
-return the size of KEY <key>
-
-=cut
-*/
-
-INTVAL
-key_size(struct Parrot_Interp *interpreter, KEY *key)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        return key->size;
-    }
-    else {
-        fprintf(stderr, "*** key_size asked to check a NULL key\n");
-        return 0;
-    }
-}
-
-/*=for api key key_set_size
-
-Set the size of KEY <key> to <size>.
-
-=cut
-*/
-
-void
-key_set_size(struct Parrot_Interp *interpreter, KEY *key, INTVAL size)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if (size < 0) {
-            fprintf(stderr, "*** key_set_size asked to resize below zero\n");
-            return;
-        }
-        if (size > key->size) {
-            KEY_PAIR *pair =
-                (KEY_PAIR *)realloc(key->keys, sizeof(KEY_PAIR *) * size);
-            if (pair != NULL) {
-                INTVAL i;
-                key->keys = pair;
-                for (i = key->size; i < size; i++) {
-                    key->keys[i].type = enum_key_undef;
-                }
-            }
-            else {
-                fprintf(stderr,
-                        "*** key_set_size tried to allocate a NULL pair\n");
-            }
-        }
-        else if (size < key->size) {
-            INTVAL i;
-            for (i = size; i < key->size; i++) {
-                /* Memory leak in the making */
-            }
-            key->keys =
-                (KEY_PAIR *)realloc(key->keys, sizeof(KEY_PAIR *) * size);
-        }
-        key->size = size;
-    }
-    else {
-        fprintf(stderr, "*** key_set_size attempted to resize a NULL key\n");
-    }
-}
-
-/*=for api key key_destroy
-
-Destroy KEY <key>
-
-=cut
-*/
-
-void
-key_destroy(struct Parrot_Interp *interpreter, KEY *key)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        INTVAL i;
-        for (i = 0; i < key->size; i++) {
-            /* Memory leak in the making */
-        }
-        free(key);
-    }
-    else {
-        fprintf(stderr, "*** key_destroy freeing NULL key\n");
-    }
-}
-
-/*=for api key key_element_type
-
-return the type of element <idx> of KEY <key>
-
-=cut
-*/
-
-INTVAL
-key_element_type(struct Parrot_Interp *interpreter, KEY *key, INTVAL idx)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if ((idx >= 0) && (idx < key->size)) {
-            KEY_PAIR *pair = (KEY_PAIR *)&key->keys[idx];
-            return pair->type;
-        }
-        else {
-            fprintf(stderr, "*** key_element_type checking out of bounds\n");
-            return -1;
-        }
-    }
-    fprintf(stderr, "*** key_element_type checking a NULL key\n");
-    return -1;
-}
-
-/*=for api key key_element_value_i
-
-return the value of index <idx> of KEY <key>
-
-=cut
-*/
-
-KEY_PAIR *
-key_element_value_i(struct Parrot_Interp *interpreter, KEY *key, INTVAL idx)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if ((idx >= 0) && (idx < key->size)) {
-            KEY_PAIR *pair = (KEY_PAIR *)&key->keys[idx];
-            if (pair != NULL) {
-                return pair;
-            }
-            else {
-                fprintf(stderr,
-                        "*** key_element_value_i pair returning a null key\n");
-            }
-        }
-        else {
-            fprintf(stderr,
-                    "*** key_element_value_i checking out of bounds\n");
-        }
-    }
-    fprintf(stderr, "*** key_element_value_i checking a NULL key\n");
-    return NULL;
-}
-
-KEY_PAIR *
-key_element_value_s(struct Parrot_Interp *interpreter, KEY *key, STRING *idx)
-{
-    KEY_PAIR *pair = NULL;
-    if (key != NULL) {
-        if (idx != NULL) {
-            INTVAL hash = key_hash(interpreter, idx);
-            hash = hash % NUM_BUCKETS;
-            pair =
-                find_bucket(interpreter,
-                            (BUCKET *)key->keys[hash].cache.struct_val, idx);
-            if (pair == NULL) {
-                internal_exception(KEY_NOT_FOUND,
-                                   "*** key_element_value_s pair returning a null key\n");
-            }
-        }
-        else {
-            internal_exception(KEY_NOT_FOUND,
-                               "*** key_element_value_s given a NULL index\n");
-        }
-    }
-    else {
-        internal_exception(KEY_NOT_FOUND,
-                           "*** key_element_value_s given a NULL key\n");
-    }
-    return pair;
-}
-
-/*=for api key key_set_element_value_i
-
-Set the value of index <idx> of key <key> to integer <value>
-
-=cut
-*/
-
-void
-key_set_element_value_i(struct Parrot_Interp *interpreter, KEY *key,
-                        INTVAL idx, KEY_PAIR *value)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if ((idx >= 0) && (idx < key->size)) {
-            memcpy(&key->keys[idx], value, sizeof(KEY_PAIR));
-        }
-        else {
-            internal_exception(KEY_NOT_FOUND,
-                               "*** key_set_element_value_i setting value out of bounds\n");
-        }
-    }
-    else {
-        internal_exception(KEY_NOT_FOUND,
-                           "*** key_set_element_value_i assigning to a NULL key\n");
-    }
-}
-
-/*=for api key key_set_element_value_s
-
-Set the value of index <idx> of key <key> to string <value>
-
-=cut
-*/
-
-void
-key_set_element_value_s(struct Parrot_Interp *interpreter, KEY *key,
-                        STRING *idx, KEY_PAIR *value)
-{
-    if (key != NULL) {
-        if (idx != NULL) {
-            if (value != NULL) {
-                INTVAL hash = key_hash(interpreter, idx);
-                BUCKET *bucket = new_bucket(interpreter, idx, value);
-                if (bucket != NULL) {
-                    hash = hash % NUM_BUCKETS;
-                    /* Resize the hash here rather than set an initial size. */
-                    if (hash >= key->size) {
-                        key_set_size(interpreter, key, hash + 1);
-                    }
-                    if (key->keys[hash].type != enum_key_undef) {
-                        STRING *tmp = key->keys[hash].cache.struct_val;
-                        bucket->next = (BUCKET *)tmp;
-                    }
-                    else {
-                    }
-                    key->keys[hash].cache.struct_val = (STRING *)bucket;
-                    key->keys[hash].type = enum_key_bucket;
-                }
-                else {
-                    fprintf(stderr,
-                            "*** key_set_element_value_s given a NULL bucket\n");
-                }
-            }
-            else {
-                fprintf(stderr,
-                        "*** key_set_element_value_s given a NULL value\n");
-            }
-        }
-        else {
-            fprintf(stderr,
-                    "*** key_set_element_value_s given a NULL index\n");
-        }
-    }
-    else {
-        fprintf(stderr, "*** key_set_element_value_s given a NULL key\n");
-    }
-}
-
-/*=for api key key_chop
-
-Remove the last element of key <key>
-
-=cut
-*/
-
-void
-key_chop(struct Parrot_Interp *interpreter, KEY *key)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if (key->size > 0) {
-            /* Memory leak in the making */
-            key->size--;
-            key->keys =
-                (KEY_PAIR *)realloc(key->keys,
-                                     sizeof(KEY_PAIR *) * key->size);
-        }
-        else if (key->size == 0) {
-            fprintf(stderr,
-                    "*** key_chop chopping a zero-length key! SHOULD NOT HAPPEN\n");
-        }
-        else {
-            fprintf(stderr,
-                    "*** key_chop chopping before start! SHOULD NOT HAPPEN\n");
-        }
-    }
-    else {
-        fprintf(stderr, "*** key_chop chopping a NULL key\n");
-    }
-}
-
-/*=for api key key_inc
-
-Increment the type of index <idx> of key <key>
-
-=cut
-*/
-
-void
-key_inc(struct Parrot_Interp *interpreter, KEY *key, INTVAL idx)
-{
-    UNUSED(interpreter);
-
-    if (key != NULL) {
-        if ((idx >= 0) && (idx < key->size)) {
-            KEY_PAIR *pair = (KEY_PAIR *)&key->keys[idx];
-            pair->type++;
-        }
-        else {
-            fprintf(stderr,
-                    "*** key_inc attempting to increment an out-of-range index\n");
-        }
-    }
-    else {
-        fprintf(stderr, "*** key_inc working on a NULL key\n");
-    }
-}
-
-/* PMC-KEY
-
-Keyed bits for PMC access. Separate from the hash key stuff but
-sharing a file for the moment, until the hash key bits get moved
-elsewhere.
-
-*/
-
 
 /*
  * Local variables:
Index: rx.ops
===================================================================
RCS file: /home/perlcvs/parrot/rx.ops,v
retrieving revision 1.18
diff -p -u -b -r1.18 rx.ops
--- rx.ops	19 Apr 2002 01:32:40 -0000	1.18
+++ rx.ops	25 Apr 2002 16:25:29 -0000
@@ -372,11 +372,10 @@ Gets the start and end indices of the gr
 =cut
 
 op rx_info_getgroup(in pmc, out int, out int, in int) {
-        KEY_PAIR key_p;
         KEY key;
 	RX_dUNPACK($1);
 
-        MAKE_KEY(key, key_p, $4, enum_key_int, int_val);
+        MAKE_KEY(key, $4, enum_key_int, int_val);
 	$2=rx->groupstart->vtable->get_integer_keyed(interpreter, rx->groupstart, &key);
 	$3=rx->groupend->vtable->get_integer_keyed(interpreter, rx->groupend, &key);
 	
@@ -636,11 +635,10 @@ the second parameter.
 =cut
 
 op rx_startgroup(in pmc, in int) {
-        KEY_PAIR key_p;
         KEY key;
 	RX_dUNPACK($1);
 	
-        MAKE_KEY(key, key_p, $2, enum_key_int, int_val);
+        MAKE_KEY(key, $2, enum_key_int, int_val);
 	rx->groupstart->vtable->set_integer_keyed(interpreter, rx->groupstart, &key, rx->index);
 	
 	goto NEXT();
@@ -656,11 +654,10 @@ the second parameter.
 =cut
 
 op rx_endgroup(in pmc, in int) {
-    KEY_PAIR key_p;
     KEY key;
     RX_dUNPACK($1);
 	
-    MAKE_KEY(key, key_p, $2, enum_key_int, int_val);        
+    MAKE_KEY(key, $2, enum_key_int, int_val);        
     rx->groupend->vtable->set_integer_keyed(interpreter, rx->groupend, &key, rx->index);
 	
     goto NEXT();
Index: string.c
===================================================================
RCS file: /home/perlcvs/parrot/string.c,v
retrieving revision 1.74
diff -p -u -b -r1.74 string.c
--- string.c	23 Apr 2002 19:41:12 -0000	1.74
+++ string.c	25 Apr 2002 16:25:31 -0000
@@ -791,6 +791,21 @@ string_from_int(struct Parrot_Interp * i
                             NULL, 0, NULL);
 }
 
+/* Stolen, with modifications, from perlnum.pmc */
+STRING *
+string_from_num(struct Parrot_Interp * interpreter, FLOATVAL f)
+{
+    char buff[200];
+    STRING* s;
+#ifdef HAS_SNPRINTF
+    snprintf(buff, sizeof(buff), FLOATVAL_FMT, f);
+#else
+    sprintf(buff, FLOATVAL_FMT, f);  /* XXX buffer overflow! */
+#endif
+    s = string_make(interpreter, buff, strlen(buff), NULL, 0, NULL);
+    return s;
+}
+
 const char *
 string_to_cstring(struct Parrot_Interp * interpreter, STRING * s)
 {
Index: classes/array.pmc
===================================================================
RCS file: /home/perlcvs/parrot/classes/array.pmc,v
retrieving revision 1.21
diff -p -u -b -r1.21 array.pmc
--- classes/array.pmc	15 Apr 2002 21:11:00 -0000	1.21
+++ classes/array.pmc	25 Apr 2002 16:25:32 -0000
@@ -12,17 +12,19 @@
 
 #include "parrot/parrot.h"
 
-static INTVAL kp2int(struct Parrot_Interp *interpreter, KEY_PAIR kp) {
-    switch ((int)kp.type) {
+static INTVAL atom2int(Interp *interpreter, KEY_ATOM* atom) {
+    switch ((int)atom->type) {
         case enum_key_undef:
         default:
             return 0;
         case enum_key_int:
-            return kp.cache.int_val;
+            return atom->val.int_val;
         case enum_key_num:
-            return (INTVAL)kp.cache.num_val;
+            return (INTVAL)atom->val.num_val;
         case enum_key_pmc:
-            return kp.cache.pmc_val->vtable->get_integer(interpreter, kp.cache.pmc_val);
+            return atom->val.pmc_val->vtable->get_integer(interpreter, atom->val.pmc_val);
+        case enum_key_string:
+            return string_to_int(atom->val.struct_val);
     }
 }
 
@@ -88,7 +90,7 @@ pmclass Array {
     }
 
     INTVAL get_integer_keyed (KEY * key) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* value;
 
@@ -96,8 +98,8 @@ pmclass Array {
             return 0;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix > SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -112,7 +114,7 @@ pmclass Array {
     }
 
     FLOATVAL get_number_keyed (KEY * key) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* value;
 
@@ -120,8 +122,8 @@ pmclass Array {
             return 0;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix > SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -136,7 +138,7 @@ pmclass Array {
     }
 
     STRING* get_string_keyed (KEY * key) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* value;
 
@@ -144,8 +146,8 @@ pmclass Array {
             return 0;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix > SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -186,7 +188,7 @@ pmclass Array {
     }
 
     void set_integer_keyed (KEY * key, INTVAL value) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* mypmc;
 
@@ -194,8 +196,8 @@ pmclass Array {
             return;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix >= SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -220,7 +222,7 @@ pmclass Array {
     }
 
     void set_number_keyed (KEY * key, FLOATVAL value) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* mypmc;
 
@@ -228,8 +230,8 @@ pmclass Array {
             return;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix >= SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -240,7 +242,7 @@ pmclass Array {
     }
 
     void set_string_keyed (KEY * key, STRING * value) {
-        KEY_PAIR* kp;
+        KEY_ATOM* kp;
         INTVAL ix;
         PMC* mypmc;
 
@@ -248,8 +250,8 @@ pmclass Array {
             return;
         }
 
-        kp = &key->keys[0];
-        ix = kp2int(INTERP, *kp);
+        kp = &key->atom;
+        ix = atom2int(INTERP, kp);
 
         if (ix >= SELF->cache.int_val || ix < 0) {
             internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
@@ -264,7 +266,7 @@ pmclass Array {
             src = src->vtable->get_pmc_keyed(INTERP, src, src_key);
         }
         if (dest_key) {
-            INTVAL ix = kp2int(INTERP, dest_key->keys[0]);
+            INTVAL ix = atom2int(INTERP, &dest_key->atom);
             PMC* dest = ((PMC**)(((Buffer *)SELF->data)->bufstart))[ix];
             dest->vtable->set_pmc(INTERP, dest, src);
         } 
Index: classes/perlarray.pmc
===================================================================
RCS file: /home/perlcvs/parrot/classes/perlarray.pmc,v
retrieving revision 1.28
diff -p -u -b -r1.28 perlarray.pmc
--- classes/perlarray.pmc	23 Apr 2002 17:19:21 -0000	1.28
+++ classes/perlarray.pmc	25 Apr 2002 16:25:36 -0000
@@ -39,19 +39,19 @@ static void resize_array ( struct Parrot
     self->cache.int_val = size;
 }
 
-static INTVAL kp2int(Interp *interpreter, KEY_PAIR* kp) {
-    switch ((int)kp->type) {
+static INTVAL atom2int(Interp *interpreter, KEY_ATOM* atom) {
+    switch ((int)atom->type) {
         case enum_key_undef:
         default:
             return 0;
         case enum_key_int:
-            return kp->cache.int_val;
+            return atom->val.int_val;
         case enum_key_num:
-            return (INTVAL)kp->cache.num_val;
+            return (INTVAL)atom->val.num_val;
         case enum_key_pmc:
-            return kp->cache.pmc_val->vtable->get_integer(interpreter, kp->cache.pmc_val);
+            return atom->val.pmc_val->vtable->get_integer(interpreter, atom->val.pmc_val);
         case enum_key_string:
-            return string_to_int(kp->cache.struct_val);
+            return string_to_int(atom->val.struct_val);
     }
 }
 
@@ -87,7 +87,7 @@ pmclass PerlArray {
     }
 
     void destroy () {
-	key_destroy(INTERP,SELF->data); /* XXX Huh? */
+	/* key_destroy(INTERP,SELF->data); XXX Huh? */
     }
 
     INTVAL get_integer () {
@@ -103,7 +103,7 @@ pmclass PerlArray {
             return 0;
         }
 
-        ix = kp2int(interpreter, &key->keys[0]);
+        ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -131,7 +131,7 @@ pmclass PerlArray {
             return 0;
         }
 
-        ix = kp2int(interpreter, &key->keys[0]);
+        ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -159,7 +159,7 @@ pmclass PerlArray {
             return 0;
         }
 
-        ix = kp2int(interpreter, &key->keys[0]);
+        ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -183,7 +183,7 @@ pmclass PerlArray {
             return 0;
         }
 
-        ix = kp2int(interpreter, &key->keys[0]);
+        ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -241,7 +241,7 @@ pmclass PerlArray {
             return;
         }
 
-	ix = kp2int(interpreter, &key->keys[0]);
+	ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -284,7 +284,7 @@ pmclass PerlArray {
             return;
         }
 
-	ix = kp2int(interpreter, &key->keys[0]);
+	ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -325,7 +325,7 @@ pmclass PerlArray {
             return;
         }
 
-	ix = kp2int(interpreter, &key->keys[0]);
+	ix = atom2int(interpreter, &key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
@@ -351,7 +351,7 @@ pmclass PerlArray {
             return;
         }
 
-	ix = kp2int(interpreter, &dest_key->keys[0]);
+	ix = atom2int(interpreter, &dest_key->atom);
 
         if (ix >= SELF->cache.int_val) {
 	    resize_array(interpreter, SELF, ix+1);
Index: include/parrot/interpreter.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/interpreter.h,v
retrieving revision 1.40
diff -p -u -b -r1.40 interpreter.h
--- include/parrot/interpreter.h	3 Apr 2002 04:01:41 -0000	1.40
+++ include/parrot/interpreter.h	25 Apr 2002 16:25:36 -0000
@@ -38,6 +39,14 @@ typedef enum {
 
 #include "parrot/op.h"
 #include "parrot/oplib.h"
+
+typedef union UnionVal {
+    INTVAL int_val;
+    FLOATVAL num_val;
+    DPOINTER* struct_val;
+    STRING* string_val;
+    PMC* pmc_val;
+} UnionVal;
 
 typedef struct warnings_t {
     Warnings_classes classes;
Index: include/parrot/key.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/key.h,v
retrieving revision 1.10
diff -p -u -b -r1.10 key.h
--- include/parrot/key.h	2 Apr 2002 20:32:48 -0000	1.10
+++ include/parrot/key.h	25 Apr 2002 16:25:36 -0000
@@ -13,8 +13,6 @@
 #if !defined(PARROT_KEY_H_GUARD)
 #define PARROT_KEY_H_GUARD
 
-#define NUM_BUCKETS 128
-
 typedef enum {
     enum_key_undef,
     enum_key_int,
@@ -25,43 +23,19 @@ typedef enum {
     enum_key_max
 } KEY_TYPE;
 
-struct _key_pair {
+typedef struct _key_atom KEY_ATOM;
+
+struct _key_atom {
     KEY_TYPE type;
-    union {
-        INTVAL int_val;
-        FLOATVAL num_val;
-        STRING *struct_val;
-        PMC *pmc_val;
-    } cache;
+    UnionVal val;
 };
 
-typedef struct _key_pair KEY_PAIR;
+typedef struct _key KEY;
 
 struct _key {
-    INTVAL size;
-    KEY_PAIR *keys;
+    KEY_ATOM atom;
+    KEY* next;
 };
-
-typedef struct _key KEY;
-
-/* Prototypes */
-KEY *key_new(struct Parrot_Interp *interpreter);
-KEY *key_clone(struct Parrot_Interp *interpreter, KEY *key);
-INTVAL key_size(struct Parrot_Interp *interpreter, KEY *key);
-void key_set_size(struct Parrot_Interp *interpreter, KEY *key, INTVAL size);
-void key_destroy(struct Parrot_Interp *interpreter, KEY *key);
-INTVAL key_element_type(struct Parrot_Interp *interpreter, KEY *key,
-                        INTVAL idx);
-KEY_PAIR *key_element_value_i(struct Parrot_Interp *interpreter, KEY *key,
-                              INTVAL idx);
-KEY_PAIR *key_element_value_s(struct Parrot_Interp *interpreter, KEY *key,
-                              STRING *idx);
-void key_set_element_value_i(struct Parrot_Interp *interpreter, KEY *key,
-                             INTVAL idx, KEY_PAIR *value);
-void key_set_element_value_s(struct Parrot_Interp *interpreter, KEY *key,
-                             STRING *idx, KEY_PAIR *value);
-void key_chop(struct Parrot_Interp *interpreter, KEY *key);
-void key_inc(struct Parrot_Interp *interpreter, KEY *key, INTVAL idx);
 
 #endif
 
Index: include/parrot/parrot.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/parrot.h,v
retrieving revision 1.30
diff -p -u -b -r1.30 parrot.h
--- include/parrot/parrot.h	4 Mar 2002 03:17:21 -0000	1.30
+++ include/parrot/parrot.h	25 Apr 2002 16:25:36 -0000
@@ -111,6 +111,7 @@ typedef void (*funcptr_t)(void);
 #include "parrot/chartype.h"
 #include "parrot/string.h"
 #include "parrot/key.h"
+#include "parrot/hash.h"
 #include "parrot/vtable.h"
 #include "parrot/register.h"
 #include "parrot/regfuncs.h"
Index: include/parrot/pmc.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/pmc.h,v
retrieving revision 1.28
diff -p -u -b -r1.28 pmc.h
--- include/parrot/pmc.h	9 Apr 2002 03:49:50 -0000	1.28
+++ include/parrot/pmc.h	25 Apr 2002 16:25:36 -0000
@@ -32,11 +32,13 @@ struct PMC {
     VTABLE *vtable;
     INTVAL flags;
     DPOINTER *data;
-    union {                   /* cache.* is intended to just be *shortcuts* to*/
-        INTVAL int_val;       /* commonly-accessed data, *not* pointers to */
-        FLOATVAL num_val;     /* completely different data.  That's why it's */
-        DPOINTER *struct_val; /* referred to as a "cache". */
-    } cache;
+
+    /* cache.* is intended to just be *shortcuts* to*/
+    /* commonly-accessed data, *not* pointers to */
+    /* completely different data.  That's why it's */
+    /* referred to as a "cache". */
+    UnionVal cache;
+    
     SYNC *synchronize;
     /* This flag determines the next PMC in the 'used' list during 
        dead object detection in the GC. It is a linked list, which is 
Index: include/parrot/string_funcs.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/string_funcs.h,v
retrieving revision 1.7
diff -p -u -b -r1.7 string_funcs.h
--- include/parrot/string_funcs.h	14 Apr 2002 18:54:29 -0000	1.7
+++ include/parrot/string_funcs.h	25 Apr 2002 16:25:37 -0000
@@ -35,6 +35,7 @@ INTVAL Parrot_string_ord(const STRING *,
 FLOATVAL Parrot_string_to_num(const STRING *);
 INTVAL Parrot_string_to_int(const STRING *);
 STRING * Parrot_string_from_int(struct Parrot_Interp *, INTVAL i);
+STRING * Parrot_string_from_num(struct Parrot_Interp *, FLOATVAL f);
 STRING * Parrot_string_grow(struct Parrot_Interp *, STRING * s, INTVAL addlen);
 void Parrot_string_destroy(STRING *);
 STRING *Parrot_string_make(struct Parrot_Interp *, const void *buffer,
@@ -65,6 +66,7 @@ const char *Parrot_string_to_cstring(str
 #define string_to_num           Parrot_string_to_num
 #define string_to_int           Parrot_string_to_int
 #define string_from_int         Parrot_string_from_int
+#define string_from_num         Parrot_string_from_num
 #define string_grow             Parrot_string_grow
 #define string_destroy          Parrot_string_destroy
 #define string_make             Parrot_string_make
Index: t/pmc/perlhash.t
===================================================================
RCS file: /home/perlcvs/parrot/t/pmc/perlhash.t,v
retrieving revision 1.9
diff -p -u -b -r1.9 perlhash.t
--- t/pmc/perlhash.t	2 Apr 2002 20:32:52 -0000	1.9
+++ t/pmc/perlhash.t	25 Apr 2002 16:25:37 -0000
@@ -3,7 +3,6 @@
 use Parrot::Test tests => 8;
 use Test::More;
 
-SKIP: { skip("Hashes unimplemented", 8);
 output_is(<<'CODE', <<OUTPUT, "simple set / get");
 	new P0, PerlHash
 	set S0, "one"
@@ -180,7 +179,5 @@ ok 1
 ok 2
 ok 3
 OUTPUT
-
-} # SKIP
 
 1;
Index: MANIFEST
===================================================================
RCS file: /home/perlcvs/parrot/MANIFEST,v
retrieving revision 1.140
diff -u -r1.140 MANIFEST
--- MANIFEST	24 Apr 2002 01:46:29 -0000	1.140
+++ MANIFEST	25 Apr 2002 16:45:47 -0000
@@ -100,6 +100,7 @@
 examples/mops/mops.scheme
 exceptions.c
 global_setup.c
+hash.c
 hints/cygwin.pl
 hints/darwin.pl
 hints/mswin32.pl
@@ -111,6 +112,7 @@
 include/parrot/events.h
 include/parrot/exceptions.h
 include/parrot/global_setup.h
+include/parrot/hash.h
 include/parrot/interp_guts.h
 include/parrot/interpreter.h
 include/parrot/io.h
Index: classes/perlhash.pmc
===================================================================
RCS file: /home/perlcvs/parrot/classes/perlhash.pmc,v
retrieving revision 1.16
diff -u -r1.16 perlhash.pmc
--- classes/perlhash.pmc	2 Apr 2002 20:32:42 -0000	1.16
+++ classes/perlhash.pmc	25 Apr 2002 16:57:57 -0000
@@ -12,6 +12,36 @@
 
 #include "parrot/parrot.h"
 
+static STRING* make_hash_key(Interp* interpreter, KEY * key)
+{
+    if (key == NULL) {
+        internal_exception(OUT_OF_BOUNDS, "Cannot use NULL key for PerlHash!\n");
+        return NULL;
+    }
+
+    if (key->next != NULL) {
+        internal_exception(OUT_OF_BOUNDS, "PerlHash does not support compound keys!\n");
+        return NULL;
+    }
+
+    switch (key->atom.type) {
+    case enum_key_int:
+        return string_from_int(interpreter, key->atom.val.int_val);
+    case enum_key_num:
+        return string_from_num(interpreter, key->atom.val.num_val);
+    case enum_key_pmc: {
+        PMC* pmc = key->atom.val.pmc_val;
+        return pmc->vtable->get_string(interpreter, pmc);
+    }
+    case enum_key_string:
+        return key->atom.val.string_val;
+    default:
+        internal_exception(OUT_OF_BOUNDS, "Cannot make hash key from type %d\n", key->atom.type);
+    }
+
+    return NULL;
+}
+
 pmclass PerlHash {
 
     INTVAL type () {
@@ -23,8 +53,7 @@
     }
 
     void init (INTVAL size) {
-	SELF->data = key_new(INTERP);
-	key_set_size(INTERP,SELF->data,0);
+	SELF->data = new_hash(INTERP);
     }
 
     void clone (PMC* dest) { 
@@ -42,37 +71,20 @@
     }
 
     void destroy () {
-	key_destroy(INTERP,SELF->data);
+  	hash_destroy(INTERP,SELF->data);
     }
 
     INTVAL get_integer () {
-	return SELF->cache.int_val;
+	return hash_size(INTERP, SELF->data);
     }
 
     INTVAL get_integer_keyed (KEY * key) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* value;
-        internal_exception(OUT_OF_BOUNDS, "Hash not implemented yet!\n");
-
-        if (!key) {
-            return 0;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        value = ((PMC**)(SELF->data))[ix];
-        return value->vtable->get_integer(INTERP, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM* atom = hash_get(INTERP, (HASH*) SELF->data, key_string);
+        if (atom->type == enum_key_int) return atom->val.int_val;
+        /* XXX This should convert to an integer if possible */
+        internal_exception(OUT_OF_BOUNDS, "Cannot fetch integer out of non-integer key!\n");
+        return -1;
     }
 
     FLOATVAL get_number () {
@@ -80,29 +92,12 @@
     }
 
     FLOATVAL get_number_keyed (KEY * key) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* value;
-        internal_exception(OUT_OF_BOUNDS, "Hash not implemented yet!\n");
-
-        if (!key) {
-            return 0;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        value = ((PMC**)(SELF->data))[ix];
-        return value->vtable->get_number(INTERP, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM* atom = hash_get(INTERP, (HASH*) SELF->data, key_string);
+        if (atom->type == enum_key_num) return atom->val.num_val;
+        /* XXX This should convert to a number if possible */
+        internal_exception(OUT_OF_BOUNDS, "Cannot fetch number out of non-numeric key!\n");
+        return 0.0;
     }
 
     STRING* get_string () {
@@ -110,29 +105,12 @@
     }
 
     STRING* get_string_keyed (KEY * key) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* value;
-        internal_exception(OUT_OF_BOUNDS, "Hash not implemented yet!\n");
-
-        if (!key) {
-            return 0;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        value = ((PMC**)(SELF->data))[ix];
-        return value->vtable->get_string(INTERP, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM* atom = hash_get(INTERP, (HASH*) SELF->data, key_string);
+        if (atom->type == enum_key_string) return atom->val.string_val;
+        /* XXX This should convert to a string */
+        internal_exception(OUT_OF_BOUNDS, "Cannot fetch string out of non-string key!\n");
+        return NULL;
     }
 
     BOOLVAL get_bool () {
@@ -152,130 +130,83 @@
     }
 
     void set_integer (PMC* value) {
-	INTVAL size = value->vtable->get_integer(INTERP,value);
-	key_set_size(INTERP,SELF->data,size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to int\n");
     }
 
     void set_integer_native (INTVAL size) {
-	key_set_size(INTERP,SELF->data,size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to int\n");
     }
 
     void set_integer_bigint (BIGINT value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to int\n");
     }
 
     void set_integer_same (PMC * value) {
-	INTVAL size = value->cache.int_val;
-	key_set_size(INTERP,SELF->data,size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to int\n");
     }
 
     void set_integer_keyed (KEY * key, INTVAL value) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* pmc2;
-
-        if (!key) {
-            return;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        pmc2 = ((PMC**)(SELF->data))[ix];
-        pmc2->vtable->set_integer_native(INTERP, pmc2, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM atom;
+        atom.type = enum_key_int;
+        atom.val.int_val = value;
+        hash_put(INTERP, SELF->data, key_string, &atom);
     }
 
     void set_number (PMC * value) {
-	INTVAL size = (INTVAL)value->cache.num_val;
-	key_set_size(INTERP,SELF->data,size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to number\n");
     }
 
     void set_number_native (FLOATVAL size) {
-	key_set_size(INTERP,SELF->data,(INTVAL)size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to number\n");
     }
 
     void set_number_bigfloat (BIGFLOAT value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to number\n");
     }
 
     void set_number_same (PMC * value) {
-	INTVAL size = value->cache.int_val;
-	key_set_size(INTERP,SELF->data,size);
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to number\n");
     }
 
     void set_number_keyed (KEY * key, FLOATVAL value) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* pmc2;
-
-        if (!key) {
-            return;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        pmc2 = ((PMC**)(SELF->data))[ix];
-        pmc2->vtable->set_number_native(INTERP, pmc2, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM atom;
+        atom.type = enum_key_num;
+        atom.val.num_val = value;
+        hash_put(INTERP, SELF->data, key_string, &atom);
     }
 
     void set_string (PMC * value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to string\n");
     }
 
     void set_string_native (STRING * value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to string\n");
     }
 
     void set_string_unicode (STRING * value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to string\n");
     }
 
     void set_string_other (STRING * value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to string\n");
     }
 
     void set_string_same (PMC * value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to string\n");
     }
 
     void set_string_keyed (KEY * key, STRING * value) {
-        KEY_PAIR* kp;
-        INTVAL ix;
-        PMC* pmc2;
-
-        if (!key) {
-            return;
-        }
-
-        kp = &key->keys[0];
-        ix = kp->cache.int_val;
-
-        if (ix > SELF->cache.int_val) {
-            /* XXX I don't think this will work quite yet */
-            /* key_set_size(kp,ix); */
-            internal_exception(OUT_OF_BOUNDS, "Array element out of bounds!\n");
-        }
-        if (ix < 0) {
-            ix += SELF->cache.int_val;
-        }
-
-        pmc2 = ((PMC**)(SELF->data))[ix];
-        pmc2->vtable->set_string_native(INTERP, pmc2, value);
+        STRING* key_string = make_hash_key(INTERP, key);
+        KEY_ATOM atom;
+        atom.type = enum_key_string;
+        atom.val.string_val = value;
+        hash_put(INTERP, SELF->data, key_string, &atom);
     }
 
     void set_value (void* value) {
+        internal_exception(INTERNAL_PANIC, "Cannot set hash to value\n");
     }
 
     void add (PMC * value, PMC* dest) {
--- /dev/null	Thu Aug 30 13:30:55 2001
+++ hash.c	Wed Apr 24 22:54:49 2002
@@ -0,0 +1,268 @@
+/* hash.c
+ *  Copyright: (When this is determined...it will go here)
+ *  CVS Info
+ *     $Id: key.c,v 1.24 2002/04/02 20:35:52 sfink Exp $
+ *  Overview:
+ *  Data Structure and Algorithms:
+ *  History:
+ *     Initial version by Jeff G. on 2001.12.05
+ *  Notes:
+ *  References:
+ */
+
+#include "parrot/parrot.h"
+
+#define INITIAL_BUCKETS 16
+
+struct _hashbucket {
+    STRING *key;
+    KEY_ATOM value;
+    HASHBUCKET *next;
+};
+
+struct _hash {
+    UINTVAL num_buckets;
+    UINTVAL entries; /* Number of values stored in hashtable */
+    Buffer* buckets;
+};
+
+static void
+dump_hash(Interp* interpreter, HASH* hash)
+{
+    UINTVAL i;
+    fprintf(stderr, "Hashtable[" INTVAL_FMT "/" INTVAL_FMT "]\n",
+            hash->entries, hash->num_buckets);
+    for (i = 0; i < hash->num_buckets; i++) {
+        HASHBUCKET* bucket = ((HASHBUCKET**) hash->buckets->bufstart)[i];
+        if (bucket == NULL) continue;
+        fprintf(stderr, "  Bucket " INTVAL_FMT ": ", i);
+        while (bucket) {
+            fprintf(stderr, "type(%d)", bucket->value.type);
+            bucket = bucket->next;
+            if (bucket) fprintf(stderr, " -> ");
+        }
+        fprintf(stderr, "\n");
+    }
+}
+
+static HASHBUCKET *
+new_bucket(Interp *interpreter, STRING *key, KEY_ATOM *value)
+{
+    HASHBUCKET *bucket = mem_sys_allocate(sizeof(HASHBUCKET));
+    if (bucket != NULL) {
+        if (key != NULL) {
+            if (value != NULL) {
+                bucket->key = string_copy(interpreter, key);
+                memcpy(&bucket->value, value, sizeof(KEY_ATOM));
+            }
+            else {
+                fprintf(stderr, "*** new_bucket was given a null pair\n");
+            }
+        }
+        else {
+            fprintf(stderr, "*** new_bucket was given a null key\n");
+        }
+    }
+    else {
+        fprintf(stderr, "*** new_bucket attempted to return a null bucket\n");
+    }
+    return bucket;
+}
+
+static HASHBUCKET *
+find_bucket(Interp *interpreter, HASHBUCKET *head, STRING *key)
+{
+    KEY_ATOM *pair = NULL;
+    if (head != NULL) {
+        if (key != NULL) {
+            while (head != NULL) {
+                if (string_compare(interpreter, key, head->key) == 0) {
+                    return head;
+                }
+                head = head->next;
+            }
+        }
+        else {
+            fprintf(stderr, "*** find_bucket given a null key\n");
+        }
+    }
+    return NULL;
+}
+
+/*=for api key key_hash
+
+Return the hashed value of the string
+
+=cut
+*/
+
+static INTVAL
+key_hash(Interp *interpreter, STRING *value)
+{
+    char *buffptr = value->bufstart;
+    INTVAL len = value->bufused;
+    INTVAL hash = 5893;
+
+    UNUSED(interpreter);
+
+    while (len--) {
+        hash = hash * 33 + *buffptr++;
+    }
+    if (hash < 0) {
+        hash = -hash;
+    }
+    return hash;
+}
+
+HASH *
+new_hash(Interp *interpreter)
+{
+    HASH* hash = mem_sys_allocate(sizeof(*hash)); /* XXX Definitely wrong */
+    hash->num_buckets = INITIAL_BUCKETS;
+    hash->entries = 0;
+    hash->buckets = new_buffer_header(interpreter);
+    Parrot_allocate_about(interpreter, hash->buckets,
+                          hash->num_buckets * sizeof(HASHBUCKET*));
+    return hash;
+}
+
+/*=for api key hash_size
+
+return the number of used entries in hashtable
+
+=cut
+*/
+
+INTVAL
+hash_size(Interp *interpreter, HASH *hash)
+{
+    UNUSED(interpreter);
+
+    if (hash != NULL) {
+        return hash->entries;
+    }
+    else {
+        fprintf(stderr, "*** hash_size asked to check a NULL hash\n");
+        return 0;
+    }
+}
+
+/*=for api key hash_set_size
+
+Set the size of HASH <hash> to <size>. SHOULD NOT BE CALLED! It doesn't
+redistribute the entries yet.
+
+=cut
+*/
+
+void
+hash_set_size(Interp *interpreter, HASH *hash, UINTVAL size)
+{
+    fprintf(stderr, "hash_set_size unimplemented.\n");
+    exit(1);
+
+    if (hash == NULL) {
+        fprintf(stderr, "*** hash_set_size attempted to resize a NULL key\n");
+        return;
+    }
+
+    if (size > hash->num_buckets) {
+        hash->buckets = Parrot_reallocate(interpreter, hash->buckets, size);
+        if (hash->buckets != NULL) {
+            memset((HASHBUCKET**)hash->buckets->bufstart + hash->num_buckets,
+                   0,
+                   (size - hash->num_buckets) * sizeof(HASHBUCKET*));
+            hash->num_buckets = size;
+        }
+        else {
+            fprintf(stderr,"*** hash_set_size out of memory\n");
+        }
+    }
+    else if (size < hash->num_buckets) {
+        fprintf(stderr, "*** hash_set_size shrinking unimplented\n");
+    }
+}
+
+/*=for api key hash_destroy
+
+Destroy HASH <hash>
+
+=cut
+*/
+
+void
+hash_destroy(Interp *interpreter, HASH* hash)
+{
+    UNUSED(interpreter);
+    UNUSED(hash);
+
+    /* Garbage collection handles this */
+}
+
+HASHBUCKET*
+hash_lookup(Interp *interpreter, HASH *hash, STRING* key)
+{
+    HASHBUCKET** buckets = (HASHBUCKET**) hash->buckets->bufstart;
+    UINTVAL hashval = key_hash(interpreter, key);
+    HASHBUCKET* chain = buckets[hashval % hash->num_buckets];
+    return find_bucket(interpreter, chain, key);
+}
+
+KEY_ATOM *
+hash_get(Interp *interpreter, HASH *hash, STRING* key)
+{
+    HASHBUCKET* bucket = hash_lookup(interpreter, hash, key);
+    if (bucket == NULL) return NULL; /* Not found */
+    return &bucket->value;
+}
+
+void
+hash_put(Interp *interpreter, HASH *hash, STRING* key, KEY_ATOM* value)
+{
+    HASHBUCKET** buckets = (HASHBUCKET**) hash->buckets->bufstart;
+    UINTVAL hashval = key_hash(interpreter, key);
+    HASHBUCKET* chain = buckets[hashval % hash->num_buckets];
+    HASHBUCKET* bucket = find_bucket(interpreter, chain, key);
+    if (bucket) {
+        /* Replacing old value */
+        memcpy(&bucket->value, value, sizeof(KEY_ATOM));
+    } else {
+        /* Create new bucket */
+        hash->entries++;
+        bucket = new_bucket(interpreter, key, value);
+        bucket->next = chain;
+        buckets[hashval % hash->num_buckets] = bucket;
+    }
+}
+
+void
+hash_delete(Interp *interpreter, HASH *hash, STRING* key)
+{
+    HASHBUCKET** buckets = (HASHBUCKET**) hash->buckets->bufstart;
+    UINTVAL hashval = key_hash(interpreter, key);
+    HASHBUCKET* chain = buckets[hashval % hash->num_buckets];
+    HASHBUCKET* bucket;
+    HASHBUCKET* prev = NULL;
+
+    for (bucket = chain; bucket != NULL; bucket = bucket->next) {
+        if (string_compare(interpreter, key, bucket->key) == 0) {
+            if (prev) prev->next = bucket->next;
+            else buckets[hashval % hash->num_buckets] = bucket->next;
+            hash->entries--;
+            return;
+        }
+        prev = bucket;
+    }
+
+    fprintf(stderr, "*** hash_delete given nonexistent key\n");
+}
+
+/*
+ * Local variables:
+ * c-indentation-style: bsd
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ *
+ * vim: expandtab shiftwidth=4:
+ */
--- /dev/null	Thu Aug 30 13:30:55 2001
+++ include/parrot/hash.h	Wed Apr 24 22:46:34 2002
@@ -0,0 +1,44 @@
+/* hash.h
+ *  Copyright: (When this is determined...it will go here)
+ *  CVS Info
+ *     $Id: key.h,v 1.10 2002/04/02 20:32:48 sfink Exp $
+ *  Overview:
+ *     Hashtable implementation
+ *  Data Structure and Algorithms:
+ *  History:
+ *  Notes:
+ *  References:
+ */
+
+#if !defined(PARROT_HASH_H_GUARD)
+#define PARROT_HASH_H_GUARD
+
+/* Prototypes */
+
+typedef struct _hashbucket HASHBUCKET;
+
+/* HASH is really a hashtable, but 'hash' is standard perl nomenclature. */
+typedef struct _hash HASH;
+
+KEY * key_new(Interp *interpreter);
+KEY * key_clone(Interp *interpreter, KEY *key);
+HASH * new_hash(Interp *interpreter);
+INTVAL hash_size(Interp *interpreter, HASH *hash);
+void hash_set_size(Interp *interpreter, HASH *hash, UINTVAL size);
+void hash_destroy(Interp *interpreter, HASH* hash);
+HASHBUCKET* hash_lookup(Interp *interpreter, HASH *hash, STRING* key);
+KEY_ATOM * hash_get(Interp *interpreter, HASH *hash, STRING* key);
+void hash_put(Interp *interpreter, HASH *hash, STRING* key, KEY_ATOM* value);
+void hash_delete(Interp *interpreter, HASH *hash, STRING* key);
+
+#endif
+
+/*
+ * Local variables:
+ * c-indentation-style: bsd
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil 
+ * End:
+ *
+ * vim: expandtab shiftwidth=4:
+*/
Index: Makefile.in
===================================================================
RCS file: /home/perlcvs/parrot/Makefile.in,v
retrieving revision 1.145
diff -u -r1.145 Makefile.in
--- Makefile.in	2 Apr 2002 06:21:27 -0000	1.145
+++ Makefile.in	25 Apr 2002 17:08:26 -0000
@@ -65,7 +65,7 @@
 $(INC)/memory.h $(INC)/parrot.h $(INC)/stacks.h $(INC)/packfile.h \
 $(INC)/global_setup.h $(INC)/vtable.h $(INC)/oplib/core_ops.h \
 $(INC)/oplib/core_ops_prederef.h $(INC)/runops_cores.h $(INC)/trace.h \
-$(INC)/pmc.h $(INC)/key.h $(INC)/resources.h $(INC)/platform.h ${cg_h} \
+$(INC)/pmc.h $(INC)/key.h $(INC)/hash.h $(INC)/resources.h $(INC)/platform.h ${cg_h} \
 $(INC)/interp_guts.h ${jit_h} $(INC)/rx.h $(INC)/rxstacks.h \
 $(INC)/embed.h $(INC)/warnings.h $(INC)/misc.h
 
@@ -87,7 +87,7 @@
 INTERP_O_FILES = exceptions$(O) global_setup$(O) interpreter$(O) parrot$(O) \
 				 register$(O) core_ops$(O) core_ops_prederef$(O) memory$(O) \
 				 packfile$(O) stacks$(O) string$(O) encoding$(O) \
-				 chartype$(O) runops_cores$(O) trace$(O) pmc$(O) key$(O) \
+				 chartype$(O) runops_cores$(O) trace$(O) pmc$(O) key$(O) hash$(O) \
 				 platform$(O) ${jit_o} resources$(O) rx$(O) rxstacks$(O) \
 				 embed$(O) warnings$(O) misc$(O) ${cg_o}