CODEWITHSUNDEEP
c#performancedictionaryhashtable
Tono Nam
Tono Nam

Reputation: 36058

Create dictionary(hash table) maintaining order

I have the following class:

    private class NodeTemp
    {            
        public string Content;
        public NodeTemp Next;
        public NodeTemp Prev;
    }

as you can see I have NodeTemp Next in order to be able to have a reference to the next element on the hash table just like the NodeTemp Prev will have a reference to the previos element on the hash table.

So I have a very large "xml" like text file that I have to parse. I looks something like:

<1><a5>: Abbrev Number: 2 (DW_TAG_base_type)
    <a6>   DW_AT_name        : unsigned short   
    <b5>   DW_AT_byte_size   : 2    
    <b6>   DW_AT_encoding    : 7    (unsigned)
 <1><b7>: Abbrev Number: 2 (DW_TAG_base_type)
    <b8>   DW_AT_name        : unsigned int 
    <c5>   DW_AT_byte_size   : 4    
    <c6>   DW_AT_encoding    : 7    (unsigned)
 <1><c7>: Abbrev Number: 2 (DW_TAG_base_type)
    <c8>   DW_AT_name        : unsigned char    
    <d6>   DW_AT_byte_size   : 1    
    <d7>   DW_AT_encoding    : 8    (unsigned char)
 <1><d8>: Abbrev Number: 4 (DW_TAG_pointer_type)
    <d9>   DW_AT_type        : DW_FORM_ref4 <0x552> 
 <1><de>: Abbrev Number: 2 (DW_TAG_base_type)
    <df>   DW_AT_name        : void 
    <e4>   DW_AT_byte_size   : 0    
    <e5>   DW_AT_encoding    : 5    (signed)
 <1><e6>: Abbrev Number: 4 (DW_TAG_pointer_type)
    <e7>   DW_AT_type        : DW_FORM_ref_udata <0xde> 
 <1><ea>: Abbrev Number: 4 (DW_TAG_pointer_type)
    <eb>   DW_AT_type        : DW_FORM_ref4 <0x180> 
 <1><f0>: Abbrev Number: 4 (DW_TAG_pointer_type)
    <f1>   DW_AT_type        : DW_FORM_ref4 <0x4cb> 
 <1><f6>: Abbrev Number: 4 (DW_TAG_pointer_type)
    <f7>   DW_AT_type        : DW_FORM_ref4 <0x4efb>    
 <1><fc>: Abbrev Number: 2 (DW_TAG_base_type)
    <fd>   DW_AT_name        : char 
    <102>   DW_AT_byte_size   : 1   
    <103>   DW_AT_encoding    : 8   (unsigned char)
.....
....

I have a method that will search through it and return me one chunk at a time. The reason why I am creating a Dictionary<string, NodeTemp> instead of a List<NodeTemp> is for performance cause I have to make several queries in order to look for the node that I need.

so what I have right now is:

var mtch = Regex.Match(GetUnparsedDebugInfo(), @"(?s)<\d+><\w+>.*?(?=\n <)");

int ctr = 0; // counter                       
NodeTemp[] nodes = new NodeTemp[3]; // circular array

while (mtch.Success)
{

    /*  mtch.value should = something like:

              <1><a5>: Abbrev Number: 2 (DW_TAG_base_type)
                <a6>   DW_AT_name        : unsigned short   
                <b5>   DW_AT_byte_size   : 2    
                <b6>   DW_AT_encoding    : 7    (unsigned)

    */

    var index = ctr % 3; // current possition in circular array

    //get key
    var k = Regex.Match(mtch.Value, @"><(\w+)>").Groups[1].Value;

    var cNode = new NodeTemp() { Content = mtch.Value };                           

    dictionary.Add(k, cNode);

    nodes[index] = cNode;

    if (ctr > 0)
    {
        var lastIndex = index - 1;
        if (lastIndex < 0)
        lastIndex = 2;

        nodes[lastIndex].Next = cNode;
        cNode.Prev = nodes[lastIndex];
    }

    ctr++;

    mtch = mtch.NextMatch();
}

This is not working because nodes[index] contains a reference to a object and at the end if I change it it will change all. How can I fix this while loop? I don't want to create a List then convert that large list to a dictionary. I think that will not be efficient.

Or maybe I can create some other type of data sctucture that will enable me to query quickly for the node that I need and I will also be able to maintain the order.

Upvotes: 0

Views: 1862

Answers (1)

Blueberry
Blueberry

Reputation: 2231

I think what you may need is an OrderedDictionary. Take a look at: http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx

Looks like theres also one which uses generics, havent tried it though. http://www.codeproject.com/Articles/18615/OrderedDictionary-T-A-generic-implementation-of-IO

Upvotes: 1

Related Questions