/** BEGIN COPYRIGHT BLOCK * This Program is free software; you can redistribute it and/or modify it under * the terms of the GNU General Public License as published by the Free Software * Foundation; version 2 of the License. * * This Program is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. * * You should have received a copy of the GNU General Public License along with * this Program; if not, write to the Free Software Foundation, Inc., 59 Temple * Place, Suite 330, Boston, MA 02111-1307 USA. * * In addition, as a special exception, Red Hat, Inc. gives You the additional * right to link the code of this Program with code not covered under the GNU * General Public License ("Non-GPL Code") and to distribute linked combinations * including the two, subject to the limitations in this paragraph. Non-GPL Code * permitted under this exception must only link to the code of this Program * through those well defined interfaces identified in the file named EXCEPTION * found in the source code files (the "Approved Interfaces"). The files of * Non-GPL Code may instantiate templates or use macros or inline functions from * the Approved Interfaces without causing the resulting work to be covered by * the GNU General Public License. Only Red Hat, Inc. may make changes or * additions to the list of Approved Interfaces. You must obey the GNU General * Public License in all respects for all of the Program code and other code used * in conjunction with the Program except the Non-GPL Code covered by this * exception. If you modify this file, you may extend this exception to your * version of the file, but you are not obligated to do so. If you do not wish to * provide this exception without modification, you must delete this exception * statement from your version and license this file solely under the GPL without * exception. * * * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission. * Copyright (C) 2005 Red Hat, Inc. * All rights reserved. * END COPYRIGHT BLOCK **/ #ifdef HAVE_CONFIG_H # include #endif #include "slapi-plugin.h" #include "slapi-private.h" /* * The "wrapper" placed around objects in our object set. */ typedef struct objset_object { Object *obj; /* pointer to actual object */ struct objset_object *next; /* pointer to next object in list */ } objset_object; /* * The object set itself. */ typedef struct objset { objset_object *head; /* pointer to linked list of objects */ objset_object *tail; /* pointer to tail of linked list */ PRLock *lock; /* Lock - protects addition/deletion from list */ FNFree destructor; /* Destructor callback for objset itself */ } objset; /* Forward declarations */ static void unlinkObjsetObjectNoLock(Objset *o, objset_object *obj_to_unlink); /* * Create a new, empty object set. * Returns a pointer to the new object set, or NULL if an error occurred. */ Objset * objset_new(FNFree objset_destructor) { objset *set; set = (objset *)slapi_ch_malloc(sizeof(objset)); set->lock = PR_NewLock(); if (NULL == set->lock) { slapi_ch_free((void **)&set); } else { set->head = set->tail = NULL; set->destructor = objset_destructor; } return set; } /* * Delete an object set. All references to contained objects * are released, and the objset is deleted. */ void objset_delete(Objset **setp) { objset_object *o, *o_next; Objset *set; PR_ASSERT(NULL != setp); set = *setp; PR_ASSERT(NULL != set); PR_Lock(set->lock); o = set->head; while (NULL != o) { o_next = o->next; object_release(o->obj); /* release our reference */ slapi_ch_free((void **)&o); /* Free wrapper */ o = o_next; } PR_Unlock(set->lock); PR_DestroyLock(set->lock); if (NULL != set->destructor) { set->destructor((void **)setp); } slapi_ch_free((void **)setp); } /* * Add a new object to an object set. * Return values: * OBJSET_SUCCESS: the insertion was succesful. * OBJSET_ALREADY_EXISTS: the object already exists in the set. */ int objset_add_obj(Objset *set, Object *object) { objset_object *p; int exists = 0; int rc = OBJSET_SUCCESS; PR_ASSERT(NULL != set); PR_ASSERT(NULL != object); PR_Lock(set->lock); /* Make sure this object isn't already in the set */ p = set->head; while (NULL != p) { if (p->obj == object) { exists = 1; break; } p = p->next; } if (exists) { rc = OBJSET_ALREADY_EXISTS; } else { objset_object *new_node = (objset_object *)slapi_ch_malloc(sizeof(objset_object)); object_acquire(object); /* Record our reference */ new_node->obj = object; new_node->next = NULL; if (NULL == set->head) { set->head = set->tail = new_node; } else { set->tail->next = new_node; set->tail = new_node; } } PR_Unlock(set->lock); return rc; } /* * Locate an object in an object set. * * Arguments: * set: the object set to search * compare_fn: a caller-provided function used to compare the * name against an object. This function should return * a negtive value, zero, or a positive value if the * object's name is, respectively, less that, equal * to, or greater than the provided name. * name: the name (value) to find. * * The returned object, if any, is referenced. The caller must * call object_release() when finished with the object. * * Returns the object, if found. Otherwise, returns NULL. * Implementation note: since we store objects in an unordered * linked list, all that's really important is that the compare_fn * return 0 when a match is found, and non-zero otherwise. * Other types of implementations might try to optimize the * storage, e.g. binary search. */ Object * objset_find(Objset *set, CMPFn compare_fn, const void *name) { objset_object *found = NULL; PR_ASSERT(NULL != set); PR_ASSERT(NULL != name); PR_ASSERT(NULL != compare_fn); PR_Lock(set->lock); found = set->head; while (NULL != found) { if (compare_fn(found->obj, name) == 0) { break; } found = found->next; } if (NULL != found) { /* acquire object */ object_acquire(found->obj); } PR_Unlock(set->lock); return found == NULL ? NULL : found->obj; } /* * Remove an object from an objset. * Returns OBJSET_SUCCESS if the object was found and removed, or * OBJSET_NO_SUCH_OBJECT if the object was not found in the list. */ int objset_remove_obj(Objset *set, Object *object) { int rc = OBJSET_SUCCESS; objset_object *found; PR_ASSERT(NULL != set); PR_ASSERT(NULL != object); PR_Lock(set->lock); found = set->head; while (NULL != found) { if (found->obj == object) { break; } found = found->next; } if (NULL == found) { rc = OBJSET_NO_SUCH_OBJECT; } else { Object *saved = found->obj; /* Unlink from list */ unlinkObjsetObjectNoLock(set, found); /* Release reference on object */ object_release(saved); } PR_Unlock(set->lock); return rc; } /* * Prepare for iteration across an object set. Returns the first * object in the set. The returned object is referenced, therefore * the caller must either release the object, or * pass it to an objset_next_obj call, which will * implicitly release the object. * Returns the first object, or NULL if the objset contains no * objects. */ Object * objset_first_obj(Objset *set) { Object *return_object; /* Be tolerant (for the replication plugin) */ if (set == NULL) return NULL; PR_Lock(set->lock); if (NULL == set->head) { return_object = NULL; } else { object_acquire(set->head->obj); return_object = set->head->obj; } PR_Unlock(set->lock); return return_object; } /* * Return the next object in an object set, or NULL if there are * no more objects. * The returned object is referenced, therefore * the caller must either release the object, or * pass it to an objset_next_ob call, which will * implicitly release the object. */ Object * objset_next_obj(Objset *set, Object *previous) { Object *return_object = NULL; objset_object *p; PR_ASSERT(NULL != set); PR_Lock(set->lock); /* First, find the current object */ p = set->head; while (NULL != p && p->obj != previous) { p = p->next; } /* Find the next object */ if (NULL != p && NULL != p->next) { return_object = p->next->obj; object_acquire(return_object); } PR_Unlock(set->lock); object_release(previous); /* Release the previous object */ return return_object; } /* * Return a non-zero value if the object set is empty, or * zero if the object set is empty. */ int objset_is_empty(Objset *set) { int return_value; PR_ASSERT(NULL != set); PR_Lock(set->lock); return_value = (set->head == NULL); PR_Unlock(set->lock); return return_value; } /* * Return the count of objects in the object set. */ int objset_size(Objset *set) { int count = 0; objset_object *p; PR_ASSERT(NULL != set); PR_Lock(set->lock); for (p = set->head; p; p = p->next) count++; PR_Unlock(set->lock); return count; } /* * Utility function: remove object from list. * This needs to be called with the objset locked. */ static void unlinkObjsetObjectNoLock(Objset *o, objset_object *obj_to_unlink) { objset_object *p = o->head; PR_ASSERT(NULL != o->head); /* Unlink from list */ if (o->head == obj_to_unlink) { /* Object to unlink was at head of list */ p = o->head->next; o->head = obj_to_unlink->next; } else { while (NULL != p->next && p->next != obj_to_unlink) { p = p->next; } if (NULL != p->next) { /* p points to object prior to one being removed */ p->next = p->next->next; } } if (o->tail == obj_to_unlink) { o->tail = p; } /* Free the wrapper */ slapi_ch_free((void **)&obj_to_unlink); }