Page 1 of 1

Microsoft : Implementing an Indexed Table : Part III Rate Topic: -----

#1 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 545
  • View blog
  • Posts: 1,420
  • Joined: 22-August 09

Posted 27 July 2017 - 10:40 AM

Introduction

In the previous two tutorials, we have looked at implementing an indexed table in memory. This has many advantages over alternative mechanisms as it provides an incredibly fast insertion rate and a very fast search for an individual key regardless of the number of entries held within the table.

In this part, we are going to unleash the power of this mechanism by implementing two additional routines. A routine for returning a pointer to an item given a key (find_item), and a routine for returning an item at a given index (find_entry).

find_item

This routine takes root node as it's first parameter, the key of the item we are searching for (in our test scenario they are the same thing!) and a pointer to the routine to be used for the comparison.

void * __stdcall find_item(NODE * node, void * item, COMPARE_ITEM compare_item) {
   if (node->node_type == INDEX_NODE) {
        INT node_index;
        for (node_index = 0; node_index < node->entry_count; node_index++) {
            if (compare_item(node->entry[node_index].item, item) >= 0) {
                return find_item(reinterpret_cast<NODE *>(node->entry[node_index].node), item, compare_item);
            }
        }
    }
    else {
        LEAF * leaf = reinterpret_cast<LEAF *>(node);
        INT node_index;
        for (node_index = 0; node_index < leaf->entry_count; node_index++) {
            if (compare_item(leaf->entry[node_index], item) > 0) break;
            if (compare_item(leaf->entry[node_index], item) == 0) {
                return leaf->entry[node_index];
            }
        }
    }
    return nullptr;
}



Now those of you that are awake may have spotted the fact that the code for this routine is almost exactly the same as the code for adding an item. The difference is of course that when we are dealing with the leaf node that is supposed to contain the key we are searching for, if we find a match we return the item otherwise if the key is not found then we return a nullptr.

find_entry and find_entry_internal

void * __stdcall find_entry_internal(NODE * node, DWORD& internal_entry_number) {
    if (node->node_type == INDEX_NODE) {
        INT node_index;
        for (node_index = 0; node_index < node->entry_count; node_index++) {
            void * this_item = find_entry_internal(reinterpret_cast<NODE *>(node->entry[node_index].node), internal_entry_number);
            if (this_item) return this_item;
        }
    }
    else {
        LEAF * leaf = reinterpret_cast<LEAF *>(node);
        INT node_index;
        if (internal_entry_number > leaf->entry_count) {
            internal_entry_number -= leaf->entry_count;
            return nullptr;
        }
        return leaf->entry[internal_entry_number - 1];
    }
    return nullptr;
}

void * __stdcall find_entry(NODE * node, DWORD entry_number) {
    DWORD internal_entry_number = entry_number;
    if (node->node_type == INDEX_NODE) {
        INT node_index;
        for (node_index = 0; node_index < node->entry_count; node_index++) {
            void * this_item = find_entry_internal(reinterpret_cast<NODE *>(node->entry[node_index].node), internal_entry_number);
            if (this_item) return this_item;
        }
    }
    return nullptr;
}



The find_entry routine is a bit of a sledgehammer to crack a nut routine as it runs through all the nodes reducing the entry number being sought until it reaches zero and that is the item returned. Personally I think it serves no useful purpose and is only included here to show that it can be done.

Extending the Capabilities

I had started working on the next and previous items and decided that it was way to complex (compared to the rest of the code). So what we are going to do is modify the headers to introduce next and previous node pointers.

typedef struct LEAF {
    NODE_TYPE     node_type;
    __int32       entry_count;
    struct NODE * parent_node;
    struct LEAF * next_leaf;
    struct LEAF * previous_leaf;
    void *        entry[508];
} LEAF;

typedef struct LOCATION {
    LEAF *        leaf;
    __int32       index;
} LOCATION;




As you can see, the LEAF structure now contains a <next_leaf> and <previous_leaf> field. These will be used (as the name suggests) to point to the next and previous data node blocks. Also note the leaf table entries have been reduced from 510 to 508 (the remainder of the code has been modified to take this into account).

The LOCATION structure is used to retain the current leaf and index in the routines find_item, next_item and previous_item detailed below.

The find_item Routine

void * __stdcall find_item(NODE * node, void * item, COMPARE_ITEM compare_item, LOCATION& location) {
    if (node->node_type == INDEX_NODE) {
        INT node_index;
        for (node_index = 0; node_index < node->entry_count; node_index++) {
            if (compare_item(node->entry[node_index].item, item) >= 0) {
                return find_item(reinterpret_cast<NODE *>(node->entry[node_index].node), item, compare_item, location);
            }
        }
    }
    else {
        LEAF * leaf = reinterpret_cast<LEAF *>(node);
        INT node_index;
        for (node_index = 0; node_index < leaf->entry_count; node_index++) {
            if (compare_item(leaf->entry[node_index], item) > 0) break;
            if (compare_item(leaf->entry[node_index], item) == 0) {
                location.leaf = leaf;
                location.index = node_index;
                return leaf->entry[node_index];
            }
        }
        location.leaf = leaf;
        location.index = node_index;
    }
    return nullptr;
}



The changes here are the addition of the LOCATION& location parameter, and the two additional lines

                location.leaf = leaf;
                location.index = node_index;



prior to returning the found item. Also note that we still set up the location structure even if we did not find the item. The location then represents the place where the item would go.

The next_item and previous_item Routines

void * __stdcall next_item(LOCATION& location) {
    if (location.leaf == nullptr) return nullptr;
    location.index++;
    if (location.leaf->entry_count == location.index) {
        location.leaf =  location.leaf->next_leaf;
        location.index = 0;
    }
    return location.leaf->entry[location.index];
}

void * __stdcall previous_item(LOCATION& location) {
    if (location.leaf == nullptr) return nullptr;
    location.index--;
    if (location.index == -1) {
        location.leaf = location.leaf->previous_leaf;
        location.index = location.leaf->entry_count - 1;
    }
    return location.leaf->entry[location.index];
}



These two routines return the next item and previous item based on the location.

This post has been edited by Martyn.Rae: 27 July 2017 - 12:00 PM


Is This A Good Question/Topic? 0
  • +

Page 1 of 1