#!/usr/bin/env python

import collections

QUEUE_SIZE = 1000
CACHE_LINE_SIZE = 64

def compute_fs(trace_file):
    recent = collections.deque(maxlen=QUEUE_SIZE)
    fs_fields = dict()
    with open(trace_file, 'r') as trace:
        for op in trace:
            if not (op.startswith('r:') or op.startswith('w:')):
                continue
            op = op.split
            op = { 'type': op[0],
                   'field': op[1],
                   'cacheline': int(op[2], 16) / CACHE_LINE_SIZE,
                   'offset': int(op[2], 16) % CACHE_LINE_SIZE,
                   'thread': op[3],
                   'is_ts': False,
                   'is_fs': False }
            check_ts(op, recent)
            check_fs(op, recent)
            recent.appendleft(op)
            # Check the element that is to be popped, if any.
            if len(recent) == QUEUE_SIZE and recent[-1]['is_fs']:
                try:
                    fs_fields[recent[-1]['field']] += 1
                except KeyError:
                    fs_fields[recent[-1]['field']] = 0
    # Check all the elements remaining in queue.
    for op in recent:
        if op['is_fs']:
            try:
                fs_fields[op['field']] += 1
            except KeyError:
                fs_fields[op['field']] = 0
    return fs_fields

def check_ts(new_op, trace):
    if new_op['type'] != 'r':
        return
    for op in trace:
        if op['type'] == 'w' and same_field(new_op, op):
            if op['thread'] != new_op['thread']:
                op['is_ts'] = True
            return
    return

def check_fs_case1(new_op, trace):
    for op in trace:
        if op['type'] == 'w' and same_field(new_op, op):
            return
        if op['thread'] == new_op['thread'] and \
                op['cacheline'] == new_op['cacheline']:
            return
        if op['type'] == 'w' and not op['is_ts'] and \
                op['thread'] != new_op['thread'] and \
                op['offset'] != new_op['offset'] and \
                op['cacheline'] == new_op['cacheline']:
            op['is_fs'] = True
            return
    return

def check_fs_case2(new_op, trace):
    reading_threads = set()
    for op in trace:
        if same_field(new_op, op):
            if op['type'] == 'r':
                reading_threads.add(op['thread'])
                continue
            elif op['thread'] != new_op['thread'] and not op['is_ts']:
                if not reading_threads - set([op['thread']]):
                    op['is_fs'] = True
                return

def check_fs_case3(new_op, trace):
    read_seen = False
    for op in trace:
        if op['thread'] == new_op['thread'] and \
                op['cacheline'] == new_op['cacheline']:
            return
        if same_field(new_op, op) and op['thread'] != new_op['thread']:
            if op['type'] == 'r':
                read_seen = True
            elif read_seen and not op['is_ts']:
                op['is_fs'] = True
                return
    return

def check_fs(new_op, trace):
    check_fs_case1(new_op, trace)
    if new_op['type'] == 'w':
        check_fs_case2(new_op, trace)
        check_fs_case3(new_op, trace)
    return

def same_field(op1, op2):
    return op1['offset'] == op2['offset'] and \
            op1['cacheline'] == op2['cacheline']

if __name__ == '__main__':
    d = compute_fs('trace.txt')
    for f, c in d.iteritems():
        print "%s: %d" % (f, c)