astobj2_hash.c

Go to the documentation of this file.
00001 /*
00002  * astobj2_hash - Hash table implementation for astobj2.
00003  *
00004  * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
00005  *
00006  * See http://www.asterisk.org for more information about
00007  * the Asterisk project. Please do not directly contact
00008  * any of the maintainers of this project for assistance;
00009  * the project provides a web site, mailing lists and IRC
00010  * channels for your use.
00011  *
00012  * This program is free software, distributed under the terms of
00013  * the GNU General Public License Version 2. See the LICENSE file
00014  * at the top of the source tree.
00015  */
00016 
00017 /*! \file
00018  *
00019  * \brief Hash table functions implementing astobj2 containers.
00020  *
00021  * \author Richard Mudgett <rmudgett@digium.com>
00022  */
00023 
00024 #include "asterisk.h"
00025 
00026 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 416807 $")
00027 
00028 #include "asterisk/_private.h"
00029 #include "asterisk/astobj2.h"
00030 #include "astobj2_private.h"
00031 #include "astobj2_container_private.h"
00032 #include "asterisk/dlinkedlists.h"
00033 #include "asterisk/utils.h"
00034 
00035 /*!
00036  * A structure to create a linked list of entries,
00037  * used within a bucket.
00038  */
00039 struct hash_bucket_node {
00040    /*!
00041     * \brief Items common to all container nodes.
00042     * \note Must be first in the specific node struct.
00043     */
00044    struct ao2_container_node common;
00045    /*! Next node links in the list. */
00046    AST_DLLIST_ENTRY(hash_bucket_node) links;
00047    /*! Hash bucket holding the node. */
00048    int my_bucket;
00049 };
00050 
00051 struct hash_bucket {
00052    /*! List of objects held in the bucket. */
00053    AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list;
00054 #if defined(AO2_DEBUG)
00055    /*! Number of elements currently in the bucket. */
00056    int elements;
00057    /*! Maximum number of elements in the bucket. */
00058    int max_elements;
00059 #endif   /* defined(AO2_DEBUG) */
00060 };
00061 
00062 /*!
00063  * A hash container in addition to values common to all
00064  * container types, stores the hash callback function, the
00065  * number of hash buckets, and the hash bucket heads.
00066  */
00067 struct ao2_container_hash {
00068    /*!
00069     * \brief Items common to all containers.
00070     * \note Must be first in the specific container struct.
00071     */
00072    struct ao2_container common;
00073    ao2_hash_fn *hash_fn;
00074    /*! Number of hash buckets in this container. */
00075    int n_buckets;
00076    /*! Hash bucket array of n_buckets.  Variable size. */
00077    struct hash_bucket buckets[0];
00078 };
00079 
00080 /*! Traversal state to restart a hash container traversal. */
00081 struct hash_traversal_state {
00082    /*! Active sort function in the traversal if not NULL. */
00083    ao2_sort_fn *sort_fn;
00084    /*! Saved comparison callback arg pointer. */
00085    void *arg;
00086    /*! Starting hash bucket */
00087    int bucket_start;
00088    /*! Stopping hash bucket */
00089    int bucket_last;
00090    /*! Saved search flags to control traversing the container. */
00091    enum search_flags flags;
00092    /*! TRUE if it is a descending search */
00093    unsigned int descending:1;
00094 };
00095 
00096 struct hash_traversal_state_check {
00097    /*
00098     * If we have a division by zero compile error here then there
00099     * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
00100     */
00101    char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))];
00102 };
00103 
00104 /*!
00105  * \internal
00106  * \brief Create an empty copy of this container.
00107  * \since 12.0.0
00108  *
00109  * \param self Container to operate upon.
00110  *
00111  * \retval empty-clone-container on success.
00112  * \retval NULL on error.
00113  */
00114 static struct ao2_container *hash_ao2_alloc_empty_clone(struct ao2_container_hash *self)
00115 {
00116    if (!is_ao2_object(self)) {
00117       return NULL;
00118    }
00119 
00120    return ao2_t_container_alloc_hash(ao2_options_get(self), self->common.options, self->n_buckets,
00121       self->hash_fn, self->common.sort_fn, self->common.cmp_fn, "Clone hash container");
00122 }
00123 
00124 /*!
00125  * \internal
00126  * \brief Create an empty copy of this container. (Debug version)
00127  * \since 12.0.0
00128  *
00129  * \param self Container to operate upon.
00130  * \param tag used for debugging.
00131  * \param file Debug file name invoked from
00132  * \param line Debug line invoked from
00133  * \param func Debug function name invoked from
00134  * \param ref_debug TRUE if to output a debug reference message.
00135  *
00136  * \retval empty-clone-container on success.
00137  * \retval NULL on error.
00138  */
00139 static struct ao2_container *hash_ao2_alloc_empty_clone_debug(struct ao2_container_hash *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
00140 {
00141    if (!is_ao2_object(self)) {
00142       return NULL;
00143    }
00144 
00145    return __ao2_container_alloc_hash_debug(ao2_options_get(self), self->common.options,
00146       self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn,
00147       tag, file, line, func, ref_debug);
00148 }
00149 
00150 /*!
00151  * \internal
00152  * \brief Destroy a hash container list node.
00153  * \since 12.0.0
00154  *
00155  * \param v_doomed Container node to destroy.
00156  *
00157  * \details
00158  * The container node unlinks itself from the container as part
00159  * of its destruction.  The node must be destroyed while the
00160  * container is already locked.
00161  *
00162  * \note The container must be locked when the node is
00163  * unreferenced.
00164  *
00165  * \return Nothing
00166  */
00167 static void hash_ao2_node_destructor(void *v_doomed)
00168 {
00169    struct hash_bucket_node *doomed = v_doomed;
00170 
00171    if (doomed->common.is_linked) {
00172       struct ao2_container_hash *my_container;
00173       struct hash_bucket *bucket;
00174 
00175       /*
00176        * Promote to write lock if not already there.  Since
00177        * adjust_lock() can potentially release and block waiting for a
00178        * write lock, care must be taken to ensure that node references
00179        * are released before releasing the container references.
00180        *
00181        * Node references held by an iterator can only be held while
00182        * the iterator also holds a reference to the container.  These
00183        * node references must be unreferenced before the container can
00184        * be unreferenced to ensure that the node will not get a
00185        * negative reference and the destructor called twice for the
00186        * same node.
00187        */
00188       my_container = (struct ao2_container_hash *) doomed->common.my_container;
00189       __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
00190 
00191 #if defined(AO2_DEBUG)
00192       if (!my_container->common.destroying
00193          && ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
00194          ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
00195       }
00196 #endif   /* defined(AO2_DEBUG) */
00197       bucket = &my_container->buckets[doomed->my_bucket];
00198       AST_DLLIST_REMOVE(&bucket->list, doomed, links);
00199       AO2_DEVMODE_STAT(--my_container->common.nodes);
00200    }
00201 
00202    /*
00203     * We could have an object in the node if the container is being
00204     * destroyed or the node had not been linked in yet.
00205     */
00206    if (doomed->common.obj) {
00207       __container_unlink_node(&doomed->common, AO2_UNLINK_NODE_UNLINK_OBJECT);
00208    }
00209 }
00210 
00211 /*!
00212  * \internal
00213  * \brief Create a new container node.
00214  * \since 12.0.0
00215  *
00216  * \param self Container to operate upon.
00217  * \param obj_new Object to put into the node.
00218  * \param tag used for debugging.
00219  * \param file Debug file name invoked from
00220  * \param line Debug line invoked from
00221  * \param func Debug function name invoked from
00222  *
00223  * \retval initialized-node on success.
00224  * \retval NULL on error.
00225  */
00226 static struct hash_bucket_node *hash_ao2_new_node(struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
00227 {
00228    struct hash_bucket_node *node;
00229    int i;
00230 
00231    node = __ao2_alloc(sizeof(*node), hash_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK);
00232    if (!node) {
00233       return NULL;
00234    }
00235 
00236    i = abs(self->hash_fn(obj_new, OBJ_SEARCH_OBJECT));
00237    i %= self->n_buckets;
00238 
00239    if (tag) {
00240       __ao2_ref_debug(obj_new, +1, tag, file, line, func);
00241    } else {
00242       ao2_t_ref(obj_new, +1, "Container node creation");
00243    }
00244    node->common.obj = obj_new;
00245    node->common.my_container = (struct ao2_container *) self;
00246    node->my_bucket = i;
00247 
00248    return node;
00249 }
00250 
00251 /*!
00252  * \internal
00253  * \brief Insert a node into this container.
00254  * \since 12.0.0
00255  *
00256  * \param self Container to operate upon.
00257  * \param node Container node to insert into the container.
00258  *
00259  * \return enum ao2_container_insert value.
00260  */
00261 static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self,
00262    struct hash_bucket_node *node)
00263 {
00264    int cmp;
00265    struct hash_bucket *bucket;
00266    struct hash_bucket_node *cur;
00267    ao2_sort_fn *sort_fn;
00268    uint32_t options;
00269 
00270    bucket = &self->buckets[node->my_bucket];
00271    sort_fn = self->common.sort_fn;
00272    options = self->common.options;
00273 
00274    if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
00275       if (sort_fn) {
00276          AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) {
00277             cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
00278             if (cmp > 0) {
00279                continue;
00280             }
00281             if (cmp < 0) {
00282                AST_DLLIST_INSERT_AFTER_CURRENT(node, links);
00283                return AO2_CONTAINER_INSERT_NODE_INSERTED;
00284             }
00285             switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
00286             default:
00287             case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
00288                break;
00289             case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
00290                /* Reject all objects with the same key. */
00291                return AO2_CONTAINER_INSERT_NODE_REJECTED;
00292             case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
00293                if (cur->common.obj == node->common.obj) {
00294                   /* Reject inserting the same object */
00295                   return AO2_CONTAINER_INSERT_NODE_REJECTED;
00296                }
00297                break;
00298             case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
00299                SWAP(cur->common.obj, node->common.obj);
00300                ao2_t_ref(node, -1, "Discard the new node.");
00301                return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
00302             }
00303          }
00304          AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
00305       }
00306       AST_DLLIST_INSERT_HEAD(&bucket->list, node, links);
00307    } else {
00308       if (sort_fn) {
00309          AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) {
00310             cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
00311             if (cmp < 0) {
00312                continue;
00313             }
00314             if (cmp > 0) {
00315                AST_DLLIST_INSERT_BEFORE_CURRENT(node, links);
00316                return AO2_CONTAINER_INSERT_NODE_INSERTED;
00317             }
00318             switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
00319             default:
00320             case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
00321                break;
00322             case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
00323                /* Reject all objects with the same key. */
00324                return AO2_CONTAINER_INSERT_NODE_REJECTED;
00325             case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
00326                if (cur->common.obj == node->common.obj) {
00327                   /* Reject inserting the same object */
00328                   return AO2_CONTAINER_INSERT_NODE_REJECTED;
00329                }
00330                break;
00331             case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
00332                SWAP(cur->common.obj, node->common.obj);
00333                ao2_t_ref(node, -1, "Discard the new node.");
00334                return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
00335             }
00336          }
00337          AST_DLLIST_TRAVERSE_SAFE_END;
00338       }
00339       AST_DLLIST_INSERT_TAIL(&bucket->list, node, links);
00340    }
00341    return AO2_CONTAINER_INSERT_NODE_INSERTED;
00342 }
00343 
00344 /*!
00345  * \internal
00346  * \brief Find the first hash container node in a traversal.
00347  * \since 12.0.0
00348  *
00349  * \param self Container to operate upon.
00350  * \param flags search_flags to control traversing the container
00351  * \param arg Comparison callback arg parameter.
00352  * \param state Traversal state to restart hash container traversal.
00353  *
00354  * \retval node-ptr of found node (Reffed).
00355  * \retval NULL when no node found.
00356  */
00357 static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state)
00358 {
00359    struct hash_bucket_node *node;
00360    int bucket_cur;
00361    int cmp;
00362 
00363    memset(state, 0, sizeof(*state));
00364    state->arg = arg;
00365    state->flags = flags;
00366 
00367    /* Determine traversal order. */
00368    switch (flags & OBJ_ORDER_MASK) {
00369    case OBJ_ORDER_POST:
00370    case OBJ_ORDER_DESCENDING:
00371       state->descending = 1;
00372       break;
00373    case OBJ_ORDER_PRE:
00374    case OBJ_ORDER_ASCENDING:
00375    default:
00376       break;
00377    }
00378 
00379    /*
00380     * If lookup by pointer or search key, run the hash and optional
00381     * sort functions.  Otherwise, traverse the whole container.
00382     */
00383    switch (flags & OBJ_SEARCH_MASK) {
00384    case OBJ_SEARCH_OBJECT:
00385    case OBJ_SEARCH_KEY:
00386       /* we know hash can handle this case */
00387       bucket_cur = abs(self->hash_fn(arg, flags & OBJ_SEARCH_MASK));
00388       bucket_cur %= self->n_buckets;
00389       state->sort_fn = self->common.sort_fn;
00390       break;
00391    case OBJ_SEARCH_PARTIAL_KEY:
00392       /* scan all buckets for partial key matches */
00393       bucket_cur = -1;
00394       state->sort_fn = self->common.sort_fn;
00395       break;
00396    default:
00397       /* don't know, let's scan all buckets */
00398       bucket_cur = -1;
00399       state->sort_fn = NULL;
00400       break;
00401    }
00402 
00403    if (state->descending) {
00404       /*
00405        * Determine the search boundaries of a descending traversal.
00406        *
00407        * bucket_cur downto state->bucket_last
00408        */
00409       if (bucket_cur < 0) {
00410          bucket_cur = self->n_buckets - 1;
00411          state->bucket_last = 0;
00412       } else {
00413          state->bucket_last = bucket_cur;
00414       }
00415       state->bucket_start = bucket_cur;
00416 
00417       /* For each bucket */
00418       for (; state->bucket_last <= bucket_cur; --bucket_cur) {
00419          /* For each node in the bucket. */
00420          for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
00421             node;
00422             node = AST_DLLIST_PREV(node, links)) {
00423             if (!node->common.obj) {
00424                /* Node is empty */
00425                continue;
00426             }
00427 
00428             if (state->sort_fn) {
00429                /* Filter node through the sort_fn */
00430                cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
00431                if (cmp > 0) {
00432                   continue;
00433                }
00434                if (cmp < 0) {
00435                   /* No more nodes in this bucket are possible to match. */
00436                   break;
00437                }
00438             }
00439 
00440             /* We have the first traversal node */
00441             __ao2_ref(node, +1);
00442             return node;
00443          }
00444       }
00445    } else {
00446       /*
00447        * Determine the search boundaries of an ascending traversal.
00448        *
00449        * bucket_cur to state->bucket_last-1
00450        */
00451       if (bucket_cur < 0) {
00452          bucket_cur = 0;
00453          state->bucket_last = self->n_buckets;
00454       } else {
00455          state->bucket_last = bucket_cur + 1;
00456       }
00457       state->bucket_start = bucket_cur;
00458 
00459       /* For each bucket */
00460       for (; bucket_cur < state->bucket_last; ++bucket_cur) {
00461          /* For each node in the bucket. */
00462          for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
00463             node;
00464             node = AST_DLLIST_NEXT(node, links)) {
00465             if (!node->common.obj) {
00466                /* Node is empty */
00467                continue;
00468             }
00469 
00470             if (state->sort_fn) {
00471                /* Filter node through the sort_fn */
00472                cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
00473                if (cmp < 0) {
00474                   continue;
00475                }
00476                if (cmp > 0) {
00477                   /* No more nodes in this bucket are possible to match. */
00478                   break;
00479                }
00480             }
00481 
00482             /* We have the first traversal node */
00483             __ao2_ref(node, +1);
00484             return node;
00485          }
00486       }
00487    }
00488 
00489    return NULL;
00490 }
00491 
00492 /*!
00493  * \internal
00494  * \brief Find the next hash container node in a traversal.
00495  * \since 12.0.0
00496  *
00497  * \param self Container to operate upon.
00498  * \param state Traversal state to restart hash container traversal.
00499  * \param prev Previous node returned by the traversal search functions.
00500  *    The ref ownership is passed back to this function.
00501  *
00502  * \retval node-ptr of found node (Reffed).
00503  * \retval NULL when no node found.
00504  */
00505 static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
00506 {
00507    struct hash_bucket_node *node;
00508    void *arg;
00509    enum search_flags flags;
00510    int bucket_cur;
00511    int cmp;
00512 
00513    arg = state->arg;
00514    flags = state->flags;
00515    bucket_cur = prev->my_bucket;
00516    node = prev;
00517 
00518    /*
00519     * This function is structured the same as hash_ao2_find_first()
00520     * intentionally.  We are resuming the search loops from
00521     * hash_ao2_find_first() in order to find the next node.  The
00522     * search loops must be resumed where hash_ao2_find_first()
00523     * returned with the first node.
00524     */
00525    if (state->descending) {
00526       goto hash_descending_resume;
00527 
00528       /* For each bucket */
00529       for (; state->bucket_last <= bucket_cur; --bucket_cur) {
00530          /* For each node in the bucket. */
00531          for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
00532             node;
00533             node = AST_DLLIST_PREV(node, links)) {
00534             if (!node->common.obj) {
00535                /* Node is empty */
00536                continue;
00537             }
00538 
00539             if (state->sort_fn) {
00540                /* Filter node through the sort_fn */
00541                cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
00542                if (cmp > 0) {
00543                   continue;
00544                }
00545                if (cmp < 0) {
00546                   /* No more nodes in this bucket are possible to match. */
00547                   break;
00548                }
00549             }
00550 
00551             /* We have the next traversal node */
00552             __ao2_ref(node, +1);
00553 
00554             /*
00555              * Dereferencing the prev node may result in our next node
00556              * object being removed by another thread.  This could happen if
00557              * the container uses RW locks and the container was read
00558              * locked.
00559              */
00560             __ao2_ref(prev, -1);
00561             if (node->common.obj) {
00562                return node;
00563             }
00564             prev = node;
00565 
00566 hash_descending_resume:;
00567          }
00568       }
00569    } else {
00570       goto hash_ascending_resume;
00571 
00572       /* For each bucket */
00573       for (; bucket_cur < state->bucket_last; ++bucket_cur) {
00574          /* For each node in the bucket. */
00575          for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
00576             node;
00577             node = AST_DLLIST_NEXT(node, links)) {
00578             if (!node->common.obj) {
00579                /* Node is empty */
00580                continue;
00581             }
00582 
00583             if (state->sort_fn) {
00584                /* Filter node through the sort_fn */
00585                cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
00586                if (cmp < 0) {
00587                   continue;
00588                }
00589                if (cmp > 0) {
00590                   /* No more nodes in this bucket are possible to match. */
00591                   break;
00592                }
00593             }
00594 
00595             /* We have the next traversal node */
00596             __ao2_ref(node, +1);
00597 
00598             /*
00599              * Dereferencing the prev node may result in our next node
00600              * object being removed by another thread.  This could happen if
00601              * the container uses RW locks and the container was read
00602              * locked.
00603              */
00604             __ao2_ref(prev, -1);
00605             if (node->common.obj) {
00606                return node;
00607             }
00608             prev = node;
00609 
00610 hash_ascending_resume:;
00611          }
00612       }
00613    }
00614 
00615    /* No more nodes in the container left to traverse. */
00616    __ao2_ref(prev, -1);
00617    return NULL;
00618 }
00619 
00620 /*!
00621  * \internal
00622  * \brief Find the next non-empty iteration node in the container.
00623  * \since 12.0.0
00624  *
00625  * \param self Container to operate upon.
00626  * \param node Previous node returned by the iterator.
00627  * \param flags search_flags to control iterating the container.
00628  *   Only AO2_ITERATOR_DESCENDING is useful by the method.
00629  *
00630  * \note The container is already locked.
00631  *
00632  * \retval node on success.
00633  * \retval NULL on error or no more nodes in the container.
00634  */
00635 static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
00636 {
00637    int cur_bucket;
00638 
00639    if (flags & AO2_ITERATOR_DESCENDING) {
00640       if (node) {
00641          cur_bucket = node->my_bucket;
00642 
00643          /* Find next non-empty node. */
00644          for (;;) {
00645             node = AST_DLLIST_PREV(node, links);
00646             if (!node) {
00647                break;
00648             }
00649             if (node->common.obj) {
00650                /* Found a non-empty node. */
00651                return node;
00652             }
00653          }
00654       } else {
00655          /* Find first non-empty node. */
00656          cur_bucket = self->n_buckets;
00657       }
00658 
00659       /* Find a non-empty node in the remaining buckets */
00660       while (0 <= --cur_bucket) {
00661          node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list);
00662          while (node) {
00663             if (node->common.obj) {
00664                /* Found a non-empty node. */
00665                return node;
00666             }
00667             node = AST_DLLIST_PREV(node, links);
00668          }
00669       }
00670    } else {
00671       if (node) {
00672          cur_bucket = node->my_bucket;
00673 
00674          /* Find next non-empty node. */
00675          for (;;) {
00676             node = AST_DLLIST_NEXT(node, links);
00677             if (!node) {
00678                break;
00679             }
00680             if (node->common.obj) {
00681                /* Found a non-empty node. */
00682                return node;
00683             }
00684          }
00685       } else {
00686          /* Find first non-empty node. */
00687          cur_bucket = -1;
00688       }
00689 
00690       /* Find a non-empty node in the remaining buckets */
00691       while (++cur_bucket < self->n_buckets) {
00692          node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list);
00693          while (node) {
00694             if (node->common.obj) {
00695                /* Found a non-empty node. */
00696                return node;
00697             }
00698             node = AST_DLLIST_NEXT(node, links);
00699          }
00700       }
00701    }
00702 
00703    /* No more nodes to visit in the container. */
00704    return NULL;
00705 }
00706 
00707 #if defined(AO2_DEBUG)
00708 /*!
00709  * \internal
00710  * \brief Increment the hash container linked object statistic.
00711  * \since 12.0.0
00712  *
00713  * \param hash Container to operate upon.
00714  * \param hash_node Container node linking object to.
00715  *
00716  * \return Nothing
00717  */
00718 static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
00719 {
00720    struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
00721    struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
00722    int i = node->my_bucket;
00723 
00724    ++self->buckets[i].elements;
00725    if (self->buckets[i].max_elements < self->buckets[i].elements) {
00726       self->buckets[i].max_elements = self->buckets[i].elements;
00727    }
00728 }
00729 #endif   /* defined(AO2_DEBUG) */
00730 
00731 #if defined(AO2_DEBUG)
00732 /*!
00733  * \internal
00734  * \brief Decrement the hash container linked object statistic.
00735  * \since 12.0.0
00736  *
00737  * \param hash Container to operate upon.
00738  * \param hash_node Container node unlinking object from.
00739  *
00740  * \return Nothing
00741  */
00742 static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
00743 {
00744    struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
00745    struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
00746 
00747    --self->buckets[node->my_bucket].elements;
00748 }
00749 #endif   /* defined(AO2_DEBUG) */
00750 
00751 /*!
00752  * \internal
00753  *
00754  * \brief Destroy this container.
00755  * \since 12.0.0
00756  *
00757  * \param self Container to operate upon.
00758  *
00759  * \return Nothing
00760  */
00761 static void hash_ao2_destroy(struct ao2_container_hash *self)
00762 {
00763    int idx;
00764 
00765    /* Check that the container no longer has any nodes */
00766    for (idx = self->n_buckets; idx--;) {
00767       if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) {
00768          ast_log(LOG_ERROR, "Node ref leak.  Hash container still has nodes!\n");
00769          ast_assert(0);
00770          break;
00771       }
00772    }
00773 }
00774 
00775 #if defined(AO2_DEBUG)
00776 /*!
00777  * \internal
00778  * \brief Display contents of the specified container.
00779  * \since 12.0.0
00780  *
00781  * \param self Container to dump.
00782  * \param where User data needed by prnt to determine where to put output.
00783  * \param prnt Print output callback function to use.
00784  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
00785  *
00786  * \return Nothing
00787  */
00788 static void hash_ao2_dump(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
00789 {
00790 #define FORMAT  "%6s, %16s, %16s, %16s, %16s, %s\n"
00791 #define FORMAT2 "%6d, %16p, %16p, %16p, %16p, "
00792 
00793    int bucket;
00794    int suppressed_buckets = 0;
00795    struct hash_bucket_node *node;
00796 
00797    prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
00798 
00799    prnt(where, FORMAT, "Bucket", "Node", "Prev", "Next", "Obj", "Key");
00800    for (bucket = 0; bucket < self->n_buckets; ++bucket) {
00801       node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
00802       if (node) {
00803          suppressed_buckets = 0;
00804          do {
00805             prnt(where, FORMAT2,
00806                bucket,
00807                node,
00808                AST_DLLIST_PREV(node, links),
00809                AST_DLLIST_NEXT(node, links),
00810                node->common.obj);
00811             if (node->common.obj && prnt_obj) {
00812                prnt_obj(node->common.obj, where, prnt);
00813             }
00814             prnt(where, "\n");
00815 
00816             node = AST_DLLIST_NEXT(node, links);
00817          } while (node);
00818       } else if (!suppressed_buckets) {
00819          suppressed_buckets = 1;
00820          prnt(where, "...\n");
00821       }
00822    }
00823 
00824 #undef FORMAT
00825 #undef FORMAT2
00826 }
00827 #endif   /* defined(AO2_DEBUG) */
00828 
00829 #if defined(AO2_DEBUG)
00830 /*!
00831  * \internal
00832  * \brief Display statistics of the specified container.
00833  * \since 12.0.0
00834  *
00835  * \param self Container to display statistics.
00836  * \param where User data needed by prnt to determine where to put output.
00837  * \param prnt Print output callback function to use.
00838  *
00839  * \note The container is already locked for reading.
00840  *
00841  * \return Nothing
00842  */
00843 static void hash_ao2_stats(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt)
00844 {
00845 #define FORMAT  "%10.10s %10.10s %10.10s\n"
00846 #define FORMAT2 "%10d %10d %10d\n"
00847 
00848    int bucket;
00849    int suppressed_buckets = 0;
00850 
00851    prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
00852 
00853    prnt(where, FORMAT, "Bucket", "Objects", "Max");
00854    for (bucket = 0; bucket < self->n_buckets; ++bucket) {
00855       if (self->buckets[bucket].max_elements) {
00856          suppressed_buckets = 0;
00857          prnt(where, FORMAT2, bucket, self->buckets[bucket].elements,
00858             self->buckets[bucket].max_elements);
00859       } else if (!suppressed_buckets) {
00860          suppressed_buckets = 1;
00861          prnt(where, "...\n");
00862       }
00863    }
00864 
00865 #undef FORMAT
00866 #undef FORMAT2
00867 }
00868 #endif   /* defined(AO2_DEBUG) */
00869 
00870 #if defined(AO2_DEBUG)
00871 /*!
00872  * \internal
00873  * \brief Perform an integrity check on the specified container.
00874  * \since 12.0.0
00875  *
00876  * \param self Container to check integrity.
00877  *
00878  * \note The container is already locked for reading.
00879  *
00880  * \retval 0 on success.
00881  * \retval -1 on error.
00882  */
00883 static int hash_ao2_integrity(struct ao2_container_hash *self)
00884 {
00885    int bucket_exp;
00886    int bucket;
00887    int count_obj;
00888    int count_total_obj;
00889    int count_total_node;
00890    void *obj_last;
00891    struct hash_bucket_node *node;
00892    struct hash_bucket_node *prev;
00893    struct hash_bucket_node *next;
00894 
00895    count_total_obj = 0;
00896    count_total_node = 0;
00897 
00898    /* For each bucket in the container. */
00899    for (bucket = 0; bucket < self->n_buckets; ++bucket) {
00900       if (!AST_DLLIST_FIRST(&self->buckets[bucket].list)
00901          && !AST_DLLIST_LAST(&self->buckets[bucket].list)) {
00902          /* The bucket list is empty. */
00903          continue;
00904       }
00905 
00906       count_obj = 0;
00907       obj_last = NULL;
00908 
00909       /* Check bucket list links and nodes. */
00910       node = AST_DLLIST_LAST(&self->buckets[bucket].list);
00911       if (!node) {
00912          ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n",
00913             bucket);
00914          return -1;
00915       }
00916       if (AST_DLLIST_NEXT(node, links)) {
00917          ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n",
00918             bucket);
00919          return -1;
00920       }
00921       node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
00922       if (!node) {
00923          ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n",
00924             bucket);
00925          return -1;
00926       }
00927       if (AST_DLLIST_PREV(node, links)) {
00928          ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n",
00929             bucket);
00930          return -1;
00931       }
00932       for (; node; node = next) {
00933          /* Check backward link. */
00934          prev = AST_DLLIST_PREV(node, links);
00935          if (prev) {
00936             if (prev == node) {
00937                ast_log(LOG_ERROR, "Bucket %d list node's prev pointer points to itself!\n",
00938                   bucket);
00939                return -1;
00940             }
00941             if (node != AST_DLLIST_NEXT(prev, links)) {
00942                ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n",
00943                   bucket);
00944                return -1;
00945             }
00946          } else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) {
00947             ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n",
00948                bucket);
00949             return -1;
00950          }
00951 
00952          /* Check forward link. */
00953          next = AST_DLLIST_NEXT(node, links);
00954          if (next) {
00955             if (next == node) {
00956                ast_log(LOG_ERROR, "Bucket %d list node's next pointer points to itself!\n",
00957                   bucket);
00958                return -1;
00959             }
00960             if (node != AST_DLLIST_PREV(next, links)) {
00961                ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n",
00962                   bucket);
00963                return -1;
00964             }
00965          } else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) {
00966             ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n",
00967                bucket);
00968             return -1;
00969          }
00970 
00971          if (bucket != node->my_bucket) {
00972             ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n",
00973                bucket, node->my_bucket);
00974             return -1;
00975          }
00976 
00977          ++count_total_node;
00978          if (!node->common.obj) {
00979             /* Node is empty. */
00980             continue;
00981          }
00982          ++count_obj;
00983 
00984          /* Check container hash key for expected bucket. */
00985          bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_SEARCH_OBJECT));
00986          bucket_exp %= self->n_buckets;
00987          if (bucket != bucket_exp) {
00988             ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n",
00989                bucket, bucket_exp);
00990             return -1;
00991          }
00992 
00993          /* Check sort if configured. */
00994          if (self->common.sort_fn) {
00995             if (obj_last
00996                && self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
00997                ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n",
00998                   bucket);
00999                return -1;
01000             }
01001             obj_last = node->common.obj;
01002          }
01003       }
01004 
01005       /* Check bucket obj count statistic. */
01006       if (count_obj != self->buckets[bucket].elements) {
01007          ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n",
01008             bucket, count_obj, self->buckets[bucket].elements);
01009          return -1;
01010       }
01011 
01012       /* Accumulate found object counts. */
01013       count_total_obj += count_obj;
01014    }
01015 
01016    /* Check total obj count. */
01017    if (count_total_obj != ao2_container_count(&self->common)) {
01018       ast_log(LOG_ERROR,
01019          "Total object count of %d does not match ao2_container_count() of %d!\n",
01020          count_total_obj, ao2_container_count(&self->common));
01021       return -1;
01022    }
01023 
01024    /* Check total node count. */
01025    if (count_total_node != self->common.nodes) {
01026       ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
01027          count_total_node, self->common.nodes);
01028       return -1;
01029    }
01030 
01031    return 0;
01032 }
01033 #endif   /* defined(AO2_DEBUG) */
01034 
01035 /*! Hash container virtual method table. */
01036 static const struct ao2_container_methods v_table_hash = {
01037    .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone,
01038    .alloc_empty_clone_debug =
01039       (ao2_container_alloc_empty_clone_debug_fn) hash_ao2_alloc_empty_clone_debug,
01040    .new_node = (ao2_container_new_node_fn) hash_ao2_new_node,
01041    .insert = (ao2_container_insert_fn) hash_ao2_insert_node,
01042    .traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first,
01043    .traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next,
01044    .iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next,
01045    .destroy = (ao2_container_destroy_fn) hash_ao2_destroy,
01046 #if defined(AO2_DEBUG)
01047    .link_stat = hash_ao2_link_node_stat,
01048    .unlink_stat = hash_ao2_unlink_node_stat,
01049    .dump = (ao2_container_display) hash_ao2_dump,
01050    .stats = (ao2_container_statistics) hash_ao2_stats,
01051    .integrity = (ao2_container_integrity) hash_ao2_integrity,
01052 #endif   /* defined(AO2_DEBUG) */
01053 };
01054 
01055 /*!
01056  * \brief always zero hash function
01057  *
01058  * it is convenient to have a hash function that always returns 0.
01059  * This is basically used when we want to have a container that is
01060  * a simple linked list.
01061  *
01062  * \returns 0
01063  */
01064 static int hash_zero(const void *user_obj, const int flags)
01065 {
01066    return 0;
01067 }
01068 
01069 /*!
01070  * \brief Initialize a hash container with the desired number of buckets.
01071  *
01072  * \param self Container to initialize.
01073  * \param options Container behaviour options (See enum ao2_container_opts)
01074  * \param n_buckets Number of buckets for hash
01075  * \param hash_fn Pointer to a function computing a hash value.
01076  * \param sort_fn Pointer to a sort function.
01077  * \param cmp_fn Pointer to a compare function used by ao2_find.
01078  *
01079  * \return A pointer to a struct container.
01080  */
01081 static struct ao2_container *hash_ao2_container_init(
01082    struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets,
01083    ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
01084 {
01085    if (!self) {
01086       return NULL;
01087    }
01088 
01089    self->common.v_table = &v_table_hash;
01090    self->common.sort_fn = sort_fn;
01091    self->common.cmp_fn = cmp_fn;
01092    self->common.options = options;
01093    self->hash_fn = hash_fn ? hash_fn : hash_zero;
01094    self->n_buckets = n_buckets;
01095 
01096 #ifdef AO2_DEBUG
01097    ast_atomic_fetchadd_int(&ao2.total_containers, 1);
01098 #endif   /* defined(AO2_DEBUG) */
01099 
01100    return (struct ao2_container *) self;
01101 }
01102 
01103 struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options,
01104    unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
01105    ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
01106 {
01107    unsigned int num_buckets;
01108    size_t container_size;
01109    struct ao2_container_hash *self;
01110 
01111    num_buckets = hash_fn ? n_buckets : 1;
01112    container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
01113 
01114    self = ao2_t_alloc_options(container_size, container_destruct, ao2_options,
01115       "New hash container");
01116    return hash_ao2_container_init(self, container_options, num_buckets,
01117       hash_fn, sort_fn, cmp_fn);
01118 }
01119 
01120 struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options,
01121    unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
01122    ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
01123    const char *tag, const char *file, int line, const char *func, int ref_debug)
01124 {
01125    unsigned int num_buckets;
01126    size_t container_size;
01127    struct ao2_container_hash *self;
01128 
01129    num_buckets = hash_fn ? n_buckets : 1;
01130    container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
01131 
01132    self = __ao2_alloc_debug(container_size,
01133       ref_debug ? container_destruct_debug : container_destruct, ao2_options,
01134       tag, file, line, func, ref_debug);
01135    return hash_ao2_container_init(self, container_options, num_buckets, hash_fn,
01136       sort_fn, cmp_fn);
01137 }
01138 
01139 struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options,
01140    unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
01141 {
01142    return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_fn,
01143       cmp_fn);
01144 }
01145 
01146 struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options,
01147    unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
01148    const char *tag, const char *file, int line, const char *func, int ref_debug)
01149 {
01150    return __ao2_container_alloc_hash_debug(ao2_options, container_options, 1, NULL,
01151       sort_fn, cmp_fn, tag, file, line, func, ref_debug);
01152 }
01153 

Generated on Thu Apr 16 06:27:15 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6