teaching machines

CS 330 Lecture 13 – DIY Malloc

February 21, 2014 by Chris Johnson. Filed under cs330, lectures, spring 2014.

Agenda

• what ?s
• enums in Java
• making a path from a directory and file name
• implementing malloc

TODO

• Read up on scope and bindings in chapter 3 through section 3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3. 1/4 sheet.

Code

Rank.java

package cards;

public enum Rank {
  ACE(1),
  TWO(2),
  THREE(3),
  FOUR(4),
  FIVE(5),
  SIX(6),
  SEVEN(7),
  EIGHT(8),
  NINE(9),
  TEN(10),
  JACK(10),
  QUEEN(10),
  KING(10);

  private int value;

  private Rank(int value) {
    this.value = value;
  }

  public int getValue() {
    return value;
  }
}

CardUtilities.java

package cards;

public class CardUtilities {
  public static void main(String[] args) {
    print(Rank.JACK);
  }

  public static void print(Rank r) {
    System.out.println(r.getValue());
  }
}

file_stuff.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *file_mehwage(const char *directory, const char *file) {
  char *mehwage = (char *) malloc(sizeof(char) * (strlen(directory) + strlen(file) + 1 + 1));

  strcpy(mehwage, directory);
  strcat(mehwage, "/");
  strcat(mehwage, file);

  return mehwage;
}

int main() {
  char *path = file_mehwage("/home/johnch", "manifesto.txt");
  printf("%s\n", path);
  return 0;
}

jmalloc.h

#ifndef JMALLOC_H
#define JMALLOC_H

void *jmalloc(int nbytes_requested);
void jfree(void *p);

#endif

jmalloc.c

#include <stdio.h>
#include <string.h>

#include "jmalloc.h"

#define HEAP_SIZE 8192
char heap[HEAP_SIZE];

struct block_t {
  int size;
  struct block_t *next;
  struct block_t *prev;
};

struct block_t *head = NULL;

void *jmalloc(int nbytes_requested) {
  // One-time startup costs of initializing free list.
  if (!head) {
    head = (struct block_t *) heap;
    head->size = HEAP_SIZE;
    head->next = NULL;
    head->prev = NULL;
  }

  // Find a block that has enough capacity to satisfy the request.
  struct block_t *big_enough_block = head;
  while (big_enough_block != NULL && big_enough_block->size < nbytes_requested) {
    big_enough_block = big_enough_block->next;
  }

  // Hey, fellas. This doesn't look good. No block satisfies.
  if (!big_enough_block) {
    return NULL;
  } else {

    // Either the block was exactly the right size.
    if (big_enough_block->size == nbytes_requested) {
      if (big_enough_block->prev) {
        big_enough_block->prev->next = big_enough_block->next;
      } else {
        head = big_enough_block->next;
      }

      if (big_enough_block->next) {
        big_enough_block->next->prev = big_enough_block->prev;
      }
    }

    // Or it had some extra space.

  }
}

void jfree(void *p) {
}

Haiku