astobj2_hash.c File Reference

Hash table functions implementing astobj2 containers. More...

#include "asterisk.h"
#include "asterisk/_private.h"
#include "asterisk/astobj2.h"
#include "astobj2_private.h"
#include "astobj2_container_private.h"
#include "asterisk/dlinkedlists.h"
#include "asterisk/utils.h"

Include dependency graph for astobj2_hash.c:

Go to the source code of this file.

Data Structures

struct  ao2_container_hash
struct  hash_bucket
struct  hash_bucket_node
struct  hash_traversal_state
struct  hash_traversal_state_check

Functions

struct ao2_container__ao2_container_alloc_hash (unsigned int ao2_options, unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
struct ao2_container__ao2_container_alloc_hash_debug (unsigned int ao2_options, unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func, int ref_debug)
struct ao2_container__ao2_container_alloc_list (unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
struct ao2_container__ao2_container_alloc_list_debug (unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func, int ref_debug)
static struct ao2_containerhash_ao2_alloc_empty_clone (struct ao2_container_hash *self)
static struct ao2_containerhash_ao2_alloc_empty_clone_debug (struct ao2_container_hash *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
static struct ao2_containerhash_ao2_container_init (struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
 Initialize a hash container with the desired number of buckets.
static void hash_ao2_destroy (struct ao2_container_hash *self)
static struct hash_bucket_nodehash_ao2_find_first (struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state)
static struct hash_bucket_nodehash_ao2_find_next (struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
static enum ao2_container_insert hash_ao2_insert_node (struct ao2_container_hash *self, struct hash_bucket_node *node)
static struct hash_bucket_nodehash_ao2_iterator_next (struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
static struct hash_bucket_nodehash_ao2_new_node (struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
static void hash_ao2_node_destructor (void *v_doomed)
static int hash_zero (const void *user_obj, const int flags)
 always zero hash function

Variables

static struct ao2_container_methods v_table_hash


Detailed Description

Hash table functions implementing astobj2 containers.

Author:
Richard Mudgett <rmudgett@digium.com>

Definition in file astobj2_hash.c.


Function Documentation

struct ao2_container* __ao2_container_alloc_hash ( unsigned int  ao2_options,
unsigned int  container_options,
unsigned int  n_buckets,
ao2_hash_fn hash_fn,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn 
) [read]

Definition at line 1103 of file astobj2_hash.c.

References ao2_t_alloc_options, container_destruct(), and hash_ao2_container_init().

Referenced by __ao2_container_alloc_list().

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 }

struct ao2_container* __ao2_container_alloc_hash_debug ( unsigned int  ao2_options,
unsigned int  container_options,
unsigned int  n_buckets,
ao2_hash_fn hash_fn,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn,
const char *  tag,
const char *  file,
int  line,
const char *  func,
int  ref_debug 
) [read]

Definition at line 1120 of file astobj2_hash.c.

References __ao2_alloc_debug(), container_destruct(), container_destruct_debug(), and hash_ao2_container_init().

Referenced by __ao2_container_alloc_list_debug(), and hash_ao2_alloc_empty_clone_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 }

struct ao2_container* __ao2_container_alloc_list ( unsigned int  ao2_options,
unsigned int  container_options,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn 
) [read]

Definition at line 1139 of file astobj2_hash.c.

References __ao2_container_alloc_hash(), and NULL.

01141 {
01142    return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_fn,
01143       cmp_fn);
01144 }

struct ao2_container* __ao2_container_alloc_list_debug ( unsigned int  ao2_options,
unsigned int  container_options,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn,
const char *  tag,
const char *  file,
int  line,
const char *  func,
int  ref_debug 
) [read]

Definition at line 1146 of file astobj2_hash.c.

References __ao2_container_alloc_hash_debug(), and NULL.

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 }

static struct ao2_container* hash_ao2_alloc_empty_clone ( struct ao2_container_hash self  )  [static, read]

Definition at line 114 of file astobj2_hash.c.

References ao2_options_get(), ao2_t_container_alloc_hash, is_ao2_object(), and NULL.

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 }

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 
) [static, read]

Definition at line 139 of file astobj2_hash.c.

References __ao2_container_alloc_hash_debug(), ao2_options_get(), is_ao2_object(), and NULL.

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 }

static struct ao2_container* hash_ao2_container_init ( struct ao2_container_hash self,
unsigned int  options,
unsigned int  n_buckets,
ao2_hash_fn hash_fn,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn 
) [static, read]

Initialize a hash container with the desired number of buckets.

Parameters:
self Container to initialize.
options Container behaviour options (See enum ao2_container_opts)
n_buckets Number of buckets for hash
hash_fn Pointer to a function computing a hash value.
sort_fn Pointer to a sort function.
cmp_fn Pointer to a compare function used by ao2_find.
Returns:
A pointer to a struct container.

Definition at line 1081 of file astobj2_hash.c.

References ast_atomic_fetchadd_int(), hash_zero(), NULL, and v_table_hash.

Referenced by __ao2_container_alloc_hash(), and __ao2_container_alloc_hash_debug().

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 }

static void hash_ao2_destroy ( struct ao2_container_hash self  )  [static]

Definition at line 761 of file astobj2_hash.c.

References ast_assert, AST_DLLIST_EMPTY, ast_log, and LOG_ERROR.

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 }

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 
) [static, read]

Definition at line 357 of file astobj2_hash.c.

References __ao2_ref(), abs, hash_traversal_state::arg, AST_DLLIST_FIRST, AST_DLLIST_LAST, AST_DLLIST_NEXT, AST_DLLIST_PREV, hash_traversal_state::bucket_last, hash_traversal_state::bucket_start, hash_bucket_node::common, hash_traversal_state::descending, hash_traversal_state::flags, NULL, ao2_container_node::obj, OBJ_ORDER_ASCENDING, OBJ_ORDER_DESCENDING, OBJ_ORDER_MASK, OBJ_ORDER_POST, OBJ_ORDER_PRE, OBJ_SEARCH_KEY, OBJ_SEARCH_MASK, OBJ_SEARCH_OBJECT, OBJ_SEARCH_PARTIAL_KEY, and hash_traversal_state::sort_fn.

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 }

static struct hash_bucket_node* hash_ao2_find_next ( struct ao2_container_hash self,
struct hash_traversal_state state,
struct hash_bucket_node prev 
) [static, read]

Definition at line 505 of file astobj2_hash.c.

References __ao2_ref(), hash_traversal_state::arg, AST_DLLIST_FIRST, AST_DLLIST_LAST, AST_DLLIST_NEXT, AST_DLLIST_PREV, hash_traversal_state::bucket_last, hash_bucket_node::common, hash_traversal_state::descending, hash_traversal_state::flags, hash_bucket_node::my_bucket, NULL, ao2_container_node::obj, OBJ_SEARCH_MASK, and hash_traversal_state::sort_fn.

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 }

static enum ao2_container_insert hash_ao2_insert_node ( struct ao2_container_hash self,
struct hash_bucket_node node 
) [static]

Definition at line 261 of file astobj2_hash.c.

References AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW, AO2_CONTAINER_ALLOC_OPT_DUPS_MASK, AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN, AO2_CONTAINER_INSERT_NODE_INSERTED, AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED, AO2_CONTAINER_INSERT_NODE_REJECTED, ao2_t_ref, AST_DLLIST_INSERT_AFTER_CURRENT, AST_DLLIST_INSERT_BEFORE_CURRENT, AST_DLLIST_INSERT_HEAD, AST_DLLIST_INSERT_TAIL, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END, AST_DLLIST_TRAVERSE_SAFE_BEGIN, AST_DLLIST_TRAVERSE_SAFE_END, hash_bucket_node::common, hash_bucket::list, hash_bucket_node::my_bucket, ao2_container_node::obj, OBJ_SEARCH_OBJECT, and SWAP.

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 }

static struct hash_bucket_node* hash_ao2_iterator_next ( struct ao2_container_hash self,
struct hash_bucket_node node,
enum ao2_iterator_flags  flags 
) [static, read]

Definition at line 635 of file astobj2_hash.c.

References AO2_ITERATOR_DESCENDING, AST_DLLIST_FIRST, AST_DLLIST_LAST, AST_DLLIST_NEXT, AST_DLLIST_PREV, hash_bucket_node::common, hash_bucket_node::my_bucket, NULL, and ao2_container_node::obj.

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 }

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 
) [static, read]

Definition at line 226 of file astobj2_hash.c.

References __ao2_alloc(), __ao2_ref_debug(), abs, AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_t_ref, hash_bucket_node::common, hash_ao2_node_destructor(), hash_bucket_node::my_bucket, ao2_container_node::my_container, NULL, ao2_container_node::obj, and OBJ_SEARCH_OBJECT.

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 }

static void hash_ao2_node_destructor ( void *  v_doomed  )  [static]

Definition at line 167 of file astobj2_hash.c.

References __adjust_lock(), __container_unlink_node, ao2_container_check(), AO2_DEVMODE_STAT, AO2_LOCK_REQ_WRLOCK, AO2_UNLINK_NODE_UNLINK_OBJECT, AST_DLLIST_REMOVE, ast_log, ao2_container_hash::buckets, ao2_container_hash::common, hash_bucket_node::common, ao2_container::destroying, ao2_container_node::is_linked, hash_bucket::list, LOG_ERROR, hash_bucket_node::my_bucket, ao2_container_node::my_container, ao2_container_node::obj, and OBJ_NOLOCK.

Referenced by hash_ao2_new_node().

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 }

static int hash_zero ( const void *  user_obj,
const int  flags 
) [static]

always zero hash function

it is convenient to have a hash function that always returns 0. This is basically used when we want to have a container that is a simple linked list.

Returns:
0

Definition at line 1064 of file astobj2_hash.c.

Referenced by hash_ao2_container_init().

01065 {
01066    return 0;
01067 }


Variable Documentation

Hash container virtual method table.

Definition at line 1036 of file astobj2_hash.c.

Referenced by hash_ao2_container_init().


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