libgo/runtime/map.h

   1 /* map.h -- the map type for Go.
   2
   3    Copyright 2009 The Go Authors. All rights reserved.
   4    Use of this source code is governed by a BSD-style
   5    license that can be found in the LICENSE file.  */
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include "go-type.h"
  11
  12 /* A map descriptor is what we need to manipulate the map.  This is
  13    constant for a given map type.  */
  14
  15 struct __go_map_descriptor
  16 {
  17   /* A pointer to the type descriptor for the type of the map itself.  */
  18   const struct __go_map_type *__map_descriptor;
  19
  20   /* A map entry is a struct with three fields:
  21        map_entry_type *next_entry;
  22        key_type key;
  23        value_type value;
  24      This is the size of that struct.  */
  25   uintptr_t __entry_size;
  26
  27   /* The offset of the key field in a map entry struct.  */
  28   uintptr_t __key_offset;
  29
  30   /* The offset of the value field in a map entry struct (the value
  31      field immediately follows the key field, but there may be some
  32      bytes inserted for alignment).  */
  33   uintptr_t __val_offset;
  34 };
  35
  36 struct __go_map
  37 {
  38   /* The constant descriptor for this map.  */
  39   const struct __go_map_descriptor *__descriptor;
  40
  41   /* The number of elements in the hash table.  */
  42   uintptr_t __element_count;
  43
  44   /* The number of entries in the __buckets array.  */
  45   uintptr_t __bucket_count;
  46
  47   /* Each bucket is a pointer to a linked list of map entries.  */
  48   void **__buckets;
  49 };
  50
  51 /* For a map iteration the compiled code will use a pointer to an
  52    iteration structure.  The iteration structure will be allocated on
  53    the stack.  The Go code must allocate at least enough space.  */
  54
  55 struct __go_hash_iter
  56 {
  57   /* A pointer to the current entry.  This will be set to NULL when
  58      the range has completed.  The Go will test this field, so it must
  59      be the first one in the structure.  */
  60   const void *entry;
  61   /* The map we are iterating over.  */
  62   const struct __go_map *map;
  63   /* A pointer to the next entry in the current bucket.  This permits
  64      deleting the current entry.  This will be NULL when we have seen
  65      all the entries in the current bucket.  */
  66   const void *next_entry;
  67   /* The bucket index of the current and next entry.  */
  68   uintptr_t bucket;
  69 };
  70
  71 extern struct __go_map *__go_new_map (const struct __go_map_descriptor *,
  72                                       uintptr_t);
  73
  74 extern uintptr_t __go_map_next_prime (uintptr_t);
  75
  76 extern void *__go_map_index (struct __go_map *, const void *, _Bool);
  77
  78 extern void __go_map_delete (struct __go_map *, const void *);
  79
  80 extern void __go_mapiterinit (const struct __go_map *, struct __go_hash_iter *);
  81
  82 extern void __go_mapiternext (struct __go_hash_iter *);
  83
  84 extern void __go_mapiter1 (struct __go_hash_iter *it, unsigned char *key);
  85
  86 extern void __go_mapiter2 (struct __go_hash_iter *it, unsigned char *key,
  87                            unsigned char *val);