Playing around with types in llvm-hs

BTree.hs

{-# LANGUAGE RecursiveDo #-}

module Eclair.Data.BTree
  ( Meta(..)
  , SearchIndex
, SearchType(..)
  , codegen
  ) where

import Protolude hiding ( Type, Meta )
import Protolude.Unsafe ( unsafeFromJust )
import qualified Data.Map as Map
import LLVM.Pretty
import qualified LLVM.AST.Constant as Constant
import qualified LLVM.AST.Name as Name
import qualified LLVM.AST.IntegerPredicate as IP
import LLVM.AST.Type
import LLVM.AST.Operand ( Operand )
import LLVM.IRBuilder.Module
import LLVM.IRBuilder.Monad
import LLVM.IRBuilder.Constant
import LLVM.IRBuilder.Instruction


codegen :: Meta -> ModuleBuilder ()
codegen meta = do
  generateTypes meta

generateTypes :: Meta -> ModuleBuilder ()
generateTypes meta = mdo
  valueTy <- mkType "value_t" $ ArrayType (fromIntegral $ numColumns meta) i32
  positionTy <- mkType "position_t" i16
  nodeSizeTy <- mkType "node_size_t" i16  -- Note: used to be size_t/i64
  nodeDataTy <- mkType "node_data_t" $
    struct [ ptr nodeTy  -- parent
           , positionTy  -- position_in_parent
           , nodeSizeTy  -- num_elements
           ]
  nodeTypeTy <- mkType "node_type_t" i8
  let numKeys' = numKeys nodeDataTy valueTy
  nodeTy <- mkType "node_t" $
    struct [ nodeTypeTy                 -- type
           , nodeDataTy                 -- meta
           , ArrayType numKeys' valueTy  -- values
           ]
  leafNodeTy <- mkType "leaf_node_t" nodeTy
  innerNodeTy <- mkType "inner_node_t" $
    struct [ nodeTy                                 -- base
           , ArrayType (numKeys' + 1) (ptr nodeTy)  -- children
           ]
  btreeIteratorTy <- mkType "btree_iterator_t" $
    struct [ ptr nodeTy  -- current
           , positionTy  -- value pos
           ]
  btreeTy <- mkType "btree_t" $
    struct [ ptr nodeTy  -- root
           , ptr nodeTy  -- first
           ]
  pure ()
  where
    mkType name ty = typedef name (Just ty)
    struct = StructureType False
    numKeys nodeDataTy valueTy = 42  -- TODO

btree_generated.ll

; ModuleID = 'btree'


 


%value_t = type [4 x i32]


%position_t = type i16


%node_size_t = type i16


%node_data_t = type {%node_t*, %position_t, %node_size_t}


%node_type_t = type i8


%node_t = type {%node_type_t, %node_data_t, [42 x %value_t]}


%leaf_node_t = type %node_t


%inner_node_t = type {%node_t, [43 x %node_t*]}


%btree_iterator_t = type {%node_t*, %position_t}


%btree_t = type {%node_t*, %node_t*}

btree_types.h

#pragma once

// A small excerpt of a larger C file

#define VALUE_SIZE 4
#define BLOCK_SIZE 256

typedef struct
{
    uint32_t columns[VALUE_SIZE];
} value;

typedef enum
{
    LT = -1,  // a < b
    EQ = 0,   // a == b
    GT = 1    // a > b
} compare_result;

typedef enum
{
    INNER_NODE,
    LEAF_NODE
} node_type;

typedef struct node node;

typedef uint16_t position_t;
typedef uint16_t node_size_t;  // NOTE: used to be size_t

struct node_data
{
    node *parent;
    position_t position_in_parent;
    node_size_t num_elements;
};

// TODO: should include size of node_type?
#define DESIRED_NUM_KEYS \
    (((BLOCK_SIZE > sizeof(struct node_data)) \
        ? BLOCK_SIZE - sizeof(struct node_data) \
        : 0) / sizeof(value))

#define NUM_KEYS (DESIRED_NUM_KEYS > 3 ? DESIRED_NUM_KEYS : 3)

typedef struct node
{
    node_type type;
    struct node_data meta;
    value values[NUM_KEYS];
} node;

typedef struct node leaf_node;

typedef struct inner_node
{
    struct node base;
    node *children[NUM_KEYS + 1];
} inner_node;

struct btree_iterator
{
    node *current;
    position_t value_pos;  // position inside current node
};

struct btree
{
    struct node *root;
    struct node *first;
};