Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

I have created a test perl script which uses Inline::C and a heavily modified version of dict.c you have linked. Changes were necessary to make Inline::C understand the code. For example it seems to me that it dislikes function pointers inside struct. So I have set all function pointers to void*. One should typecast when necessary. It also seemed to me it had problems with enums within struct. I have replaced them with #define and integers.

beautyfulman, it is now your call. Provide C code to test the functionality within C of dict.c. For example: create dictionary, add items, delete items, find items.

EDIT: Important: in order for this code to work, I have made a change to Inline/Struct.pm. The original code I posted here needs that change in order to "work". Because I don't have test code I do not know whether my change will work or not, I know it compiles the code. That's all. So, I am now modifying the code below in order not to rely on Inline::Struct. The new code below will work with Inline::C (I have put comments where I did the changes).

bw, bliako

#!/usr/bin/perl # by bliako # for https://perlmonks.org/?node_id=11138654 # 11.11.2021 # Incorporates dict.c from # https://rubygems.org/gems/rbtree # extract using # tar xvf rbtree-0.4.4.gem && tar xvzf data.tar.gz # bliako has modified the C code in order to compile under Inline::C # it still remains to be seen if modifications have any side effects # as there is no test code yet. # it requires Inline::C and Inline::Struct (to "enable => 'structs'") # this uses Inline::Struct to export C structs # comment it out because Inline::Struct has a problem with # self-referencing C structs (among the other problems listed above) #use Inline C => <<'END', enable => 'structs'; use Inline C => <<'END'; #include <stdlib.h> #include <stddef.h> #include <assert.h> #include <limits.h> #define DICT_IMPLEMENTATION typedef unsigned long dictcount_t; #define DICTCOUNT_T_MAX ULONG_MAX #define dnode_red 0 #define dnode_black 1 struct DNode { struct DNode *dict_left; struct DNode *dict_right; struct DNode *dict_parent; int dict_color; const void *dict_key; void *dict_data; }; struct Dict { struct DNode dict_nilnode; dictcount_t dict_nodecount; void *dict_compare; void *dict_allocnode; void *dict_freenode; void *dict_context; int dict_dupes; }; struct Dict_load { struct Dict *dict_dictptr; struct DNode dict_nilnode; }; //xxx struct Dict *dict_create(int (*dict_comp)(const void *, const void *, + void *)); void dict_set_allocator(struct Dict *, struct DNode *(*dnode_alloc_t) +(void *), void (*dnode_free_t)(struct DNode *, void *), void *); void dict_destroy(struct Dict *); void dict_free_nodes(struct Dict *); void dict_free(struct Dict *); struct Dict *dict_init(struct Dict *, int (*dict_comp)(const void *, +const void *, void *)); void dict_init_like(struct Dict *, const struct Dict *); int dict_verify(struct Dict *); int dict_similar(const struct Dict *, const struct Dict *); struct DNode *dict_lookup(struct Dict *, const void *); struct DNode *dict_lower_bound(struct Dict *, const void *); struct DNode *dict_upper_bound(struct Dict *, const void *); int dict_insert(struct Dict *, struct DNode *, const void *); struct DNode *dict_delete(struct Dict *, struct DNode *); int dict_alloc_insert(struct Dict *, const void *, void *); void dict_delete_free(struct Dict *, struct DNode *); struct DNode *dict_first(struct Dict *); struct DNode *dict_last(struct Dict *); struct DNode *dict_next(struct Dict *, struct DNode *); struct DNode *dict_prev(struct Dict *, struct DNode *); dictcount_t dict_count(struct Dict *); int dict_isempty(struct Dict *); int dict_isfull(struct Dict *); int dict_contains(struct Dict *, struct DNode *); void dict_allow_dupes(struct Dict *); int dnode_is_in_a_dict(struct DNode *); struct DNode *dnode_create(void *); struct DNode *dnode_init(struct DNode *, void *); void dnode_destroy(struct DNode *); void *dnode_get(struct DNode *); const void *dnode_getkey(struct DNode *); void dnode_put(struct DNode *, void *); void dict_process(struct Dict *, void *, void (*dnode_process_t)(stru +ct Dict *, struct DNode *, void *)); void dict_load_begin(struct Dict_load *, struct Dict *); void dict_load_next(struct Dict_load *, struct DNode *, const void *) +; void dict_load_end(struct Dict_load *); void dict_merge(struct Dict *, struct Dict *); #define dict_isfull(D) ((D)->dict_nodecount == DICTCOUNT_T_MAX) #define dict_count(D) ((D)->dict_nodecount) #define dict_isempty(D) ((D)->dict_nodecount == 0) #define dnode_get(N) ((N)->dict_data) #define dnode_getkey(N) ((N)->dict_key) #define dnode_put(N, X) ((N)->dict_data = (X)) #ifdef KAZLIB_RCSID static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:4 +4 kaz Exp $"; #endif /* * These macros provide short convenient names for structure members, * which are embellished with dict_ prefixes so that they are * properly confined to the documented namespace. It's legal for a * program which uses dict to define, for instance, a macro called ``p +arent''. * Such a macro would interfere with the struct DNode struct definitio +n. * In general, highly portable and reusable C modules which expose the +ir * structures need to confine structure member names to well-defined s +paces. * The resulting identifiers aren't necessarily convenient to use, nor * readable, in the implementation, however! */ #define left dict_left #define right dict_right #define parent dict_parent #define color dict_color #define key dict_key #define data dict_data #define nilnode dict_nilnode #define nodecount dict_nodecount #define compare dict_compare #define allocnode dict_allocnode #define freenode dict_freenode #define context dict_context #define dupes dict_dupes #define dictptr dict_dictptr #define dict_root(D) ((D)->nilnode.left) #define dict_nil(D) (&(D)->nilnode) #define DICT_DEPTH_MAX 64 static struct DNode *dnode_alloc(void *context); static void dnode_free(struct DNode *node, void *context); /* * Perform a ``left rotation'' adjustment on the tree. The given node + P and * its right child C are rearranged so that the P instead becomes the +left * child of C. The left subtree of C is inherited as the new right s +ubtree * for P. The ordering of the keys within the tree is thus preserved. */ static void rotate_left(struct DNode *upper) { struct DNode *lower, *lowleft, *upparent; lower = upper->right; upper->right = lowleft = lower->left; lowleft->parent = upper; lower->parent = upparent = upper->parent; /* don't need to check for root node here because root->parent is the sentinel nil node, and root->parent->left points back to ro +ot */ if (upper == upparent->left) { upparent->left = lower; } else { assert (upper == upparent->right); upparent->right = lower; } lower->left = upper; upper->parent = lower; } /* * This operation is the ``mirror'' image of rotate_left. It is * the same procedure, but with left and right interchanged. */ static void rotate_right(struct DNode *upper) { struct DNode *lower, *lowright, *upparent; lower = upper->left; upper->left = lowright = lower->right; lowright->parent = upper; lower->parent = upparent = upper->parent; if (upper == upparent->right) { upparent->right = lower; } else { assert (upper == upparent->left); upparent->left = lower; } lower->right = upper; upper->parent = lower; } /* * Do a postorder traversal of the tree rooted at the specified * node and free everything under it. Used by dict_free(). */ static void free_nodes(struct Dict *dict, struct DNode *node, struct D +Node *nil) { if (node == nil) return; free_nodes(dict, node->left, nil); free_nodes(dict, node->right, nil); void (*dict_freenode)(struct DNode *, void *) = dict->freenode; dict_freenode(node, dict->context); } /* * This procedure performs a verification that the given subtree is a +binary * search tree. It performs an inorder traversal of the tree using the * dict_next() successor function, verifying that the key of each node + is * strictly lower than that of its successor, if duplicates are not al +lowed, * or lower or equal if duplicates are allowed. This function is used + for * debugging purposes. */ static int verify_bintree(struct Dict *dict) { struct DNode *first, *next; first = dict_first(dict); int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; if (dict->dupes) { while (first && (next = dict_next(dict, first))) { if (dict_compare(first->key, next->key, dict->context) > 0) return 0; first = next; } } else { while (first && (next = dict_next(dict, first))) { if (dict_compare(first->key, next->key, dict->context) >= 0) return 0; first = next; } } return 1; } /* * This function recursively verifies that the given binary subtree sa +tisfies * three of the red black properties. It checks that every red node ha +s only * black children. It makes sure that each node is either red or black +. And it * checks that every path has the same count of black nodes from root +to leaf. * It returns the blackheight of the given subtree; this allows blackh +eights to * be computed recursively and compared for left and right siblings fo +r * mismatches. It does not check for every nil node being black, becau +se there * is only one sentinel nil node. The return value of this function is + the * black height of the subtree rooted at the node ``root'', or zero if + the * subtree is not red-black. */ static unsigned int verify_redblack(struct DNode *nil, struct DNode *r +oot) { unsigned height_left, height_right; if (root != nil) { height_left = verify_redblack(nil, root->left); height_right = verify_redblack(nil, root->right); if (height_left == 0 || height_right == 0) return 0; if (height_left != height_right) return 0; if (root->color == dnode_red) { if (root->left->color != dnode_black) return 0; if (root->right->color != dnode_black) return 0; return height_left; } if (root->color != dnode_black) return 0; return height_left + 1; } return 1; } /* * Compute the actual count of nodes by traversing the tree and * return it. This could be compared against the stored count to * detect a mismatch. */ static dictcount_t verify_node_count(struct DNode *nil, struct DNode * +root) { if (root == nil) return 0; else return 1 + verify_node_count(nil, root->left) + verify_node_count(nil, root->right); } /* * Verify that the tree contains the given node. This is done by * traversing all of the nodes and comparing their pointers to the * given pointer. Returns 1 if the node is found, otherwise * returns zero. It is intended for debugging purposes. */ static int verify_dict_has_node(struct DNode *nil, struct DNode *root, + struct DNode *node) { if (root != nil) { return root == node || verify_dict_has_node(nil, root->left, node) || verify_dict_has_node(nil, root->right, node); } return 0; } /* * Dynamically allocate and initialize a dictionary object. */ struct Dict *dict_create(int (*comp)(const void *, const void *, void +*)) { struct Dict *new = malloc(sizeof *new); if (new) { new->compare = comp; new->allocnode = dnode_alloc; new->freenode = dnode_free; new->context = NULL; new->nodecount = 0; new->nilnode.left = &new->nilnode; new->nilnode.right = &new->nilnode; new->nilnode.parent = &new->nilnode; new->nilnode.color = dnode_black; new->dupes = 0; } return new; } /* * Select a different set of node allocator routines. */ void dict_set_allocator(struct Dict *dict, struct DNode *(*al)(void *) +, void (*fr)(struct DNode *, void *), void *context) { assert (dict_count(dict) == 0); assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); dict->allocnode = al ? al : dnode_alloc; dict->freenode = fr ? fr : dnode_free; dict->context = context; } /* * Free a dynamically allocated dictionary object. Removing the nodes * from the tree before deleting it is required. */ void dict_destroy(struct Dict *dict) { assert (dict_isempty(dict)); free(dict); } /* * Free all the nodes in the dictionary by using the dictionary's * installed free routine. The dictionary is emptied. */ void dict_free_nodes(struct Dict *dict) { struct DNode *nil = dict_nil(dict), *root = dict_root(dict); free_nodes(dict, root, nil); dict->nodecount = 0; dict->nilnode.left = &dict->nilnode; dict->nilnode.right = &dict->nilnode; dict->nilnode.parent = &dict->nilnode; } /* * Obsolescent function, equivalent to dict_free_nodes */ void dict_free(struct Dict *dict) { #ifdef KAZLIB_OBSOLESCENT_DEBUG assert ("call to obsolescent function dict_free()" && 0); #endif dict_free_nodes(dict); } /* * Initialize a user-supplied dictionary object. */ struct Dict *dict_init(struct Dict *dict, int (*comp)(const void *, co +nst void *, void *)) { dict->compare = comp; dict->allocnode = dnode_alloc; dict->freenode = dnode_free; dict->context = NULL; dict->nodecount = 0; dict->nilnode.left = &dict->nilnode; dict->nilnode.right = &dict->nilnode; dict->nilnode.parent = &dict->nilnode; dict->nilnode.color = dnode_black; dict->dupes = 0; return dict; } /* * Initialize a dictionary in the likeness of another dictionary */ void dict_init_like(struct Dict *dict, const struct Dict *template) { dict->compare = template->compare; dict->allocnode = template->allocnode; dict->freenode = template->freenode; dict->context = template->context; dict->nodecount = 0; dict->nilnode.left = &dict->nilnode; dict->nilnode.right = &dict->nilnode; dict->nilnode.parent = &dict->nilnode; dict->nilnode.color = dnode_black; dict->dupes = template->dupes; assert (dict_similar(dict, template)); } /* * Remove all nodes from the dictionary (without freeing them in any w +ay). */ static void dict_clear(struct Dict *dict) { dict->nodecount = 0; dict->nilnode.left = &dict->nilnode; dict->nilnode.right = &dict->nilnode; dict->nilnode.parent = &dict->nilnode; assert (dict->nilnode.color == dnode_black); } /* * Verify the integrity of the dictionary structure. This is provided + for * debugging purposes, and should be placed in assert statements. Ju +st because * this function succeeds doesn't mean that the tree is not corrupt. C +ertain * corruptions in the tree may simply cause undefined behavior. */ int dict_verify(struct Dict *dict) { struct DNode *nil = dict_nil(dict), *root = dict_root(dict); /* check that the sentinel node and root node are black */ if (root->color != dnode_black) return 0; if (nil->color != dnode_black) return 0; if (nil->right != nil) return 0; /* nil->left is the root node; check that its parent pointer is ni +l */ if (nil->left->parent != nil) return 0; /* perform a weak test that the tree is a binary search tree */ if (!verify_bintree(dict)) return 0; /* verify that the tree is a red-black tree */ if (!verify_redblack(nil, root)) return 0; if (verify_node_count(nil, root) != dict_count(dict)) return 0; return 1; } /* * Determine whether two dictionaries are similar: have the same compa +rison and * allocator functions, and same status as to whether duplicates are a +llowed. */ int dict_similar(const struct Dict *left, const struct Dict *right) { if (left->compare != right->compare) return 0; if (left->allocnode != right->allocnode) return 0; if (left->freenode != right->freenode) return 0; if (left->context != right->context) return 0; return 1; } /* * Locate a node in the dictionary having the given key. * If the node is not found, a null a pointer is returned (rather than + * a pointer that dictionary's nil sentinel node), otherwise a pointer + to the * located node is returned. */ struct DNode *dict_lookup(struct Dict *dict, const void *key) { struct DNode *root = dict_root(dict); struct DNode *nil = dict_nil(dict); struct DNode *saved; int result; /* simple binary search adapted for trees that contain duplicate k +eys */ int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; while (root != nil) { result = dict_compare(key, root->key, dict->context); if (result < 0) root = root->left; else if (result > 0) root = root->right; else { if (!dict->dupes) { /* no duplicates, return match * +/ return root; } else { /* could be dupes, find leftmost one */ do { saved = root; root = root->left; while (root != nil && dict_compare(key, root->key, dict->c +ontext)) root = root->right; } while (root != nil); return saved; } } } return NULL; } /* * Look for the node corresponding to the lowest key that is equal to +or * greater than the given key. If there is no such node, return null. */ struct DNode *dict_lower_bound(struct Dict *dict, const void *key) { struct DNode *root = dict_root(dict); struct DNode *nil = dict_nil(dict); struct DNode *tentative = 0; int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; while (root != nil) { int result = dict_compare(key, root->key, dict->context); if (result > 0) { root = root->right; } else if (result < 0) { tentative = root; root = root->left; } else { if (!dict->dupes) { return root; } else { tentative = root; root = root->left; } } } return tentative; } /* * Look for the node corresponding to the greatest key that is equal t +o or * lower than the given key. If there is no such node, return null. */ struct DNode *dict_upper_bound(struct Dict *dict, const void *key) { struct DNode *root = dict_root(dict); struct DNode *nil = dict_nil(dict); struct DNode *tentative = 0; int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; while (root != nil) { int result = dict_compare(key, root->key, dict->context); if (result < 0) { root = root->left; } else if (result > 0) { tentative = root; root = root->right; } else { if (!dict->dupes) { return root; } else { tentative = root; root = root->right; } } } return tentative; } /* * Insert a node into the dictionary. The node should have been * initialized with a data field. All other fields are ignored. * The behavior is undefined if the user attempts to insert into * a dictionary that is already full (for which the dict_isfull() * function returns true). */ int dict_insert(struct Dict *dict, struct DNode *node, const void *key +) { struct DNode *where = dict_root(dict), *nil = dict_nil(dict); struct DNode *parent = nil, *uncle, *grandpa; int result = -1; node->key = key; assert (!dict_isfull(dict)); assert (!dict_contains(dict, node)); assert (!dnode_is_in_a_dict(node)); /* basic binary tree insert */ int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; while (where != nil) { parent = where; result = dict_compare(key, where->key, dict->context); if (!dict->dupes && result == 0) { where->data = node->data; return 0; } else if (result < 0) { where = where->left; } else { where = where->right; } } assert (where == nil); if (result < 0) parent->left = node; else parent->right = node; node->parent = parent; node->left = nil; node->right = nil; dict->nodecount++; /* red black adjustments */ node->color = dnode_red; while (parent->color == dnode_red) { grandpa = parent->parent; if (parent == grandpa->left) { uncle = grandpa->right; if (uncle->color == dnode_red) { /* red parent, red uncle * +/ parent->color = dnode_black; uncle->color = dnode_black; grandpa->color = dnode_red; node = grandpa; parent = grandpa->parent; } else { /* red parent, black uncle */ if (node == parent->right) { rotate_left(parent); parent = node; assert (grandpa == parent->parent); /* rotation between parent and child preserves grandpa */ } parent->color = dnode_black; grandpa->color = dnode_red; rotate_right(grandpa); break; } } else { /* symmetric cases: parent == parent->parent->right * +/ uncle = grandpa->left; if (uncle->color == dnode_red) { parent->color = dnode_black; uncle->color = dnode_black; grandpa->color = dnode_red; node = grandpa; parent = grandpa->parent; } else { if (node == parent->left) { rotate_right(parent); parent = node; assert (grandpa == parent->parent); } parent->color = dnode_black; grandpa->color = dnode_red; rotate_left(grandpa); break; } } } dict_root(dict)->color = dnode_black; assert (dict_verify(dict)); return 1; } /* * Delete the given node from the dictionary. If the given node does n +ot belong * to the given dictionary, undefined behavior results. A pointer to +the * deleted node is returned. */ struct DNode *dict_delete(struct Dict *dict, struct DNode *delete) { struct DNode *nil = dict_nil(dict), *child, *delparent = delete->p +arent; /* basic deletion */ assert (!dict_isempty(dict)); assert (dict_contains(dict, delete)); /* * If the node being deleted has two children, then we replace it +with its * successor (i.e. the leftmost node in the right subtree.) By doi +ng this, * we avoid the traditional algorithm under which the successor's +key and * value *only* move to the deleted node and the successor is spli +ced out * from the tree. We cannot use this approach because the user may + hold * pointers to the successor, or nodes may be inextricably tied to + some * other structures by way of embedding, etc. So we must splice ou +t the * node we are given, not some other node, and must not move conte +nts from * one node to another behind the user's back. */ if (delete->left != nil && delete->right != nil) { struct DNode *next = dict_next(dict, delete); struct DNode *nextparent = next->parent; int nextcolor = next->color; assert (next != nil); assert (next->parent != nil); assert (next->left == nil); /* * First, splice out the successor from the tree completely, by * moving up its right child into its place. */ child = next->right; child->parent = nextparent; if (nextparent->left == next) { nextparent->left = child; } else { assert (nextparent->right == next); nextparent->right = child; } /* * Now that the successor has been extricated from the tree, insta +ll it * in place of the node that we want deleted. */ next->parent = delparent; next->left = delete->left; next->right = delete->right; next->left->parent = next; next->right->parent = next; next->color = delete->color; delete->color = nextcolor; if (delparent->left == delete) { delparent->left = next; } else { assert (delparent->right == delete); delparent->right = next; } } else { assert (delete != nil); assert (delete->left == nil || delete->right == nil); child = (delete->left != nil) ? delete->left : delete->right; child->parent = delparent = delete->parent; if (delete == delparent->left) { delparent->left = child; } else { assert (delete == delparent->right); delparent->right = child; } } delete->parent = NULL; delete->right = NULL; delete->left = NULL; dict->nodecount--; assert (verify_bintree(dict)); /* red-black adjustments */ if (delete->color == dnode_black) { struct DNode *parent, *sister; dict_root(dict)->color = dnode_red; while (child->color == dnode_black) { parent = child->parent; if (child == parent->left) { sister = parent->right; assert (sister != nil); if (sister->color == dnode_red) { sister->color = dnode_black; parent->color = dnode_red; rotate_left(parent); sister = parent->right; assert (sister != nil); } if (sister->left->color == dnode_black && sister->right->color == dnode_black) { sister->color = dnode_red; child = parent; } else { if (sister->right->color == dnode_black) { assert (sister->left->color == dnode_red); sister->left->color = dnode_black; sister->color = dnode_red; rotate_right(sister); sister = parent->right; assert (sister != nil); } sister->color = parent->color; sister->right->color = dnode_black; parent->color = dnode_black; rotate_left(parent); break; } } else { /* symmetric case: child == child->parent->right * +/ assert (child == parent->right); sister = parent->left; assert (sister != nil); if (sister->color == dnode_red) { sister->color = dnode_black; parent->color = dnode_red; rotate_right(parent); sister = parent->left; assert (sister != nil); } if (sister->right->color == dnode_black && sister->left->color == dnode_black) { sister->color = dnode_red; child = parent; } else { if (sister->left->color == dnode_black) { assert (sister->right->color == dnode_red); sister->right->color = dnode_black; sister->color = dnode_red; rotate_left(sister); sister = parent->left; assert (sister != nil); } sister->color = parent->color; sister->left->color = dnode_black; parent->color = dnode_black; rotate_right(parent); break; } } } child->color = dnode_black; dict_root(dict)->color = dnode_black; } assert (dict_verify(dict)); return delete; } /* * Allocate a node using the dictionary's allocator routine, give it * the data item. */ int dict_alloc_insert(struct Dict *dict, const void *key, void *data) { struct DNode *(*dict_allocnode)(void *) = dict_allocnode; struct DNode *node = dict_allocnode(dict->context); void (*dict_freenode)(struct DNode *, void *) = dict->freenode; if (node) { dnode_init(node, data); if (!dict_insert(dict, node, key)) dict_freenode(node, dict->context); return 1; } return 0; } void dict_delete_free(struct Dict *dict, struct DNode *node) { dict_delete(dict, node); void (*dict_freenode)(struct DNode *, void *) = dict->freenode; dict_freenode(node, dict->context); } /* * Return the node with the lowest (leftmost) key. If the dictionary i +s empty * (that is, dict_isempty(dict) returns 1) a null pointer is returned. */ struct DNode *dict_first(struct Dict *dict) { struct DNode *nil = dict_nil(dict), *root = dict_root(dict), *left +; if (root != nil) while ((left = root->left) != nil) root = left; return (root == nil) ? NULL : root; } /* * Return the node with the highest (rightmost) key. If the dictionary + is empty * (that is, dict_isempty(dict) returns 1) a null pointer is returned. */ struct DNode *dict_last(struct Dict *dict) { struct DNode *nil = dict_nil(dict), *root = dict_root(dict), *righ +t; if (root != nil) while ((right = root->right) != nil) root = right; return (root == nil) ? NULL : root; } /* * Return the given node's successor node---the node which has the * next key in the the left to right ordering. If the node has * no successor, a null pointer is returned rather than a pointer to * the nil node. */ struct DNode *dict_next(struct Dict *dict, struct DNode *curr) { struct DNode *nil = dict_nil(dict), *parent, *left; if (curr->right != nil) { curr = curr->right; while ((left = curr->left) != nil) curr = left; return curr; } parent = curr->parent; while (parent != nil && curr == parent->right) { curr = parent; parent = curr->parent; } return (parent == nil) ? NULL : parent; } /* * Return the given node's predecessor, in the key order. * The nil sentinel node is returned if there is no predecessor. */ struct DNode *dict_prev(struct Dict *dict, struct DNode *curr) { struct DNode *nil = dict_nil(dict), *parent, *right; if (curr->left != nil) { curr = curr->left; while ((right = curr->right) != nil) curr = right; return curr; } parent = curr->parent; while (parent != nil && curr == parent->left) { curr = parent; parent = curr->parent; } return (parent == nil) ? NULL : parent; } void dict_allow_dupes(struct Dict *dict) { dict->dupes = 1; } #undef dict_count #undef dict_isempty #undef dict_isfull #undef dnode_get #undef dnode_put #undef dnode_getkey dictcount_t dict_count(struct Dict *dict) { return dict->nodecount; } int dict_isempty(struct Dict *dict) { return dict->nodecount == 0; } int dict_isfull(struct Dict *dict) { return dict->nodecount == DICTCOUNT_T_MAX; } int dict_contains(struct Dict *dict, struct DNode *node) { return verify_dict_has_node(dict_nil(dict), dict_root(dict), node) +; } static struct DNode *dnode_alloc(void *context) { return malloc(sizeof *dnode_alloc(NULL)); } static void dnode_free(struct DNode *node, void *context) { free(node); } struct DNode *dnode_create(void *data) { struct DNode *new = malloc(sizeof *new); if (new) { new->data = data; new->parent = NULL; new->left = NULL; new->right = NULL; } return new; } struct DNode *dnode_init(struct DNode *dnode, void *data) { dnode->data = data; dnode->parent = NULL; dnode->left = NULL; dnode->right = NULL; return dnode; } void dnode_destroy(struct DNode *dnode) { assert (!dnode_is_in_a_dict(dnode)); free(dnode); } void *dnode_get(struct DNode *dnode) { return dnode->data; } const void *dnode_getkey(struct DNode *dnode) { return dnode->key; } void dnode_put(struct DNode *dnode, void *data) { dnode->data = data; } int dnode_is_in_a_dict(struct DNode *dnode) { return (dnode->parent && dnode->left && dnode->right); } void dict_process(struct Dict *dict, void *context, void (*function)(s +truct Dict *, struct DNode *, void *)) { struct DNode *node = dict_first(dict), *next; while (node != NULL) { /* check for callback function deleting */ /* the next node from under us */ assert (dict_contains(dict, node)); next = dict_next(dict, node); function(dict, node, context); node = next; } } static void load_begin_internal(struct Dict_load *load, struct Dict *d +ict) { load->dictptr = dict; load->nilnode.left = &load->nilnode; load->nilnode.right = &load->nilnode; } void dict_load_begin(struct Dict_load *load, struct Dict *dict) { assert (dict_isempty(dict)); load_begin_internal(load, dict); } void dict_load_next(struct Dict_load *load, struct DNode *newnode, con +st void *key) { struct Dict *dict = load->dictptr; struct DNode *nil = &load->nilnode; assert (!dnode_is_in_a_dict(newnode)); assert (dict->nodecount < DICTCOUNT_T_MAX); int (*dict_compare)(const void *, const void *, void *) = dict->compar +e; #ifndef NDEBUG if (dict->nodecount > 0) { if (dict->dupes) assert (dict_compare(nil->left->key, key, dict->context) <= 0) +; else assert (dict_compare(nil->left->key, key, dict->context) < 0); } #endif newnode->key = key; nil->right->left = newnode; nil->right = newnode; newnode->left = nil; dict->nodecount++; } void dict_load_end(struct Dict_load *load) { struct Dict *dict = load->dictptr; struct DNode *tree[DICT_DEPTH_MAX] = { 0 }; struct DNode *curr, *dictnil = dict_nil(dict), *loadnil = &load->n +ilnode, *next; struct DNode *complete = 0; dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecou +nt; dictcount_t botrowcount; unsigned baselevel = 0, level = 0, i; assert (dnode_red == 0 && dnode_black == 1); while (fullcount >= nodecount && fullcount) fullcount >>= 1; botrowcount = nodecount - fullcount; for (curr = loadnil->left; curr != loadnil; curr = next) { next = curr->left; if (complete == NULL && botrowcount-- == 0) { assert (baselevel == 0); assert (level == 0); baselevel = level = 1; complete = tree[0]; if (complete != 0) { tree[0] = 0; complete->right = dictnil; while (tree[level] != 0) { tree[level]->right = complete; complete->parent = tree[level]; complete = tree[level]; tree[level++] = 0; } } } if (complete == NULL) { curr->left = dictnil; curr->right = dictnil; curr->color = level % 2; complete = curr; assert (level == baselevel); while (tree[level] != 0) { tree[level]->right = complete; complete->parent = tree[level]; complete = tree[level]; tree[level++] = 0; } } else { curr->left = complete; curr->color = (level + 1) % 2; complete->parent = curr; tree[level] = curr; complete = 0; level = baselevel; } } if (complete == NULL) complete = dictnil; for (i = 0; i < DICT_DEPTH_MAX; i++) { if (tree[i] != 0) { tree[i]->right = complete; complete->parent = tree[i]; complete = tree[i]; } } dictnil->color = dnode_black; dictnil->right = dictnil; complete->parent = dictnil; complete->color = dnode_black; dict_root(dict) = complete; assert (dict_verify(dict)); } void dict_merge(struct Dict *dest, struct Dict *source) { struct Dict_load load; struct DNode *leftnode = dict_first(dest), *rightnode = dict_first +(source); assert (dict_similar(dest, source)); if (source == dest) return; dest->nodecount = 0; load_begin_internal(&load, dest); int (*dest_compare)(const void *, const void *, void *) = dest->compar +e; for (;;) { if (leftnode != NULL && rightnode != NULL) { if (dest_compare(leftnode->key, rightnode->key, dest->context) + < 0) goto copyleft; else goto copyright; } else if (leftnode != NULL) { goto copyleft; } else if (rightnode != NULL) { goto copyright; } else { assert (leftnode == NULL && rightnode == NULL); break; } copyleft: { struct DNode *next = dict_next(dest, leftnode); #ifndef NDEBUG leftnode->left = NULL; /* suppress assertion in dict_load_n +ext */ #endif dict_load_next(&load, leftnode, leftnode->key); leftnode = next; continue; } copyright: { struct DNode *next = dict_next(source, rightnode); #ifndef NDEBUG rightnode->left = NULL; #endif dict_load_next(&load, rightnode, rightnode->key); rightnode = next; continue; } } dict_clear(source); dict_load_end(&load); } END # Commented out Inline::Struct, so this will not work now. #my $node = Inline::Struct::DNode->new; #my $dict = Inline::Struct::Dict->new;

In reply to Re: Anyone with XS experience willing to create a high performance data type for Perl? (Updated) by bliako
in thread Anyone with XS experience willing to create a high performance data type for Perl? by beautyfulman

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (5)
As of 2024-03-28 14:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found